SOFTELメモ Developer's blog

会社概要 ブログ 調査依頼 採用情報 ...
技術者募集中

【php】計算量を減らして高速化する

問題

以下の2つの計算、結果はどちらも同じだけど、どちらが速いですか?

x * x * x * x + x * x * x + x * x …(1 掛け算がたくさん)
(x * x + x + 1) * x * x …(2 まとめてから掛け算)

どちらの計算が速い? 数式

答え

よくある、計算量を減らすひと工夫。

掛け算が6回と足し算が2回の式(1)と、掛け算が3回、足し算が2回の式(2)、どちらが高速か?

一般に後者が速いと言われるが、phpのコマンドライン版で試してみる。

時間の計測は linuxのtimeコマンドにお願いした。

計算が1回だけだと一瞬過ぎてよくわからないので、1億回ループさせて計った。

掛け算が6回と足し算が2回の式の場合

$ time php -r 'for ($i = 0; $i < 100000000; ++$i) {$x = rand(0, 10); $x * $x * $x * $x + $x * $x * $x + $x * $x; }'

real    0m44.564s
user    0m44.487s
sys     0m0.041s

掛け算が3回と足し算が2回の式

$ time php -r 'for ($i = 0; $i < 100000000; ++$i) {$x = rand(0, 10); ($x * $x + $x + 1) * $x * $x; }'

real    0m40.690s
user    0m40.560s
sys     0m0.044s

結果

あまり変わらなかった。

どっちが速いかというと、計算の回数を減らした方だけど。。。

1億回実行してこの程度の差なので、負荷対策等としては、もし実施するとしても最後の最後に、暇だったらやろうかというレベルの話ではある。

関連するメモ

コメント