TL;DR
- PHP 開発者向けに、計算量の考え方と測り方を紹介する発表。
- PHP や Laravel の組み込み関数にも計算量の大きいものがあるので、よく使う処理の計算量は把握しておく。ただし、データ量が少なければ可読性を優先する。
内容
時間計算量
時間計算量は、PHP のオペコードにおける JUMP の数で考えられ、ビッグオー記法で表す。負荷試験でデータ量と処理時間の相関を取れば、時間計算量を確かめられる。
空間計算量
空間計算量は、memory_get_usage や memory_get_peak_usage で確認できる。
計算量との付き合い方
Mackerel、New Relic、Datadog などのアラートで問題になるべく早く気づける環境を作り、該当箇所のオーダーを下げる。PHP や Laravel の組み込み関数の中にも O(n) 以上のものがあるので、よく使う処理の計算量は把握しておく。
ただし、常に改善すればよいわけではない。データ量が少なければどんなアルゴリズムでも計算量は小さいので、その場合は可読性を重視する。また、チューニングには限界があるので、複雑な仕様を単純にするよう提案することも大事である。