Archive for 1月 11th, 2011

実行速度(改)

Categories: python
1月 11th, 2011 by admin

先日、Python、PHP、JavaScriptの3つの言語で、プログラムの実行速度を比較したところ、JavaScript＞PHP＞Pythonの結果になったのですが、いくつか指摘をいただいたので追加検証してみました。先日の記事 ⇒ 実行速度

  1. 書き方が悪いからおそいんじゃ？
    普通にforループ使ったほうが速いよ。sum関数使うともっと速いよ。(by inamori@hatena)
  2. 長整数型になってるから遅いのでは？
    (by atsuoishimoto@twitter)

1. 記述方法の改善

最初に言い訳させてもらいます。range関数で、1000万個も変数を確保するとボトルネックになるんじゃないかと思っていたので、whileを使って記述してました。

whileループ

カッコ悪いのであまり掲載したくは無いのですが、元の遅いソースコードを添付しておきます。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
>>> def count(n):
...   i = 0
...   sum = 0
...   while i < n:
...     i = i + 1
...     sum = sum + i
...   return sum
...
>>> profile.run('count(10000000)')
         4 function calls in 1.632 CPU seconds

   Ordered by: standard name

   ncalls  tottime  percall  cumtime  percall filename:lineno(function)
        1    0.000    0.000    0.000    0.000 :0(setprofile)
        1    1.632    1.632    1.632    1.632 <stdin>:1(count)
        1    0.000    0.000    1.632    1.632 <string>:1(<module>)
        1    0.000    0.000    1.632    1.632 profile:0(count(10000000))
        0    0.000             0.000          profile:0(profiler)

forループで処理

forループに書き換えたところ、1.6秒⇒1.3秒程度まで高速化しました。測定回ごとに5%程度は結果はばらつきますが、明らかに高速化しています。しかも、読みやすくなりました。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
>>> def count1(n):
...   sum = 0
...   for i in range(1, n+1):
...     sum = sum + i
...
>>> profile.run('count1(10000001)')
         5 function calls in 1.305 CPU seconds

   Ordered by: standard name

   ncalls  tottime  percall  cumtime  percall filename:lineno(function)
        1    0.150    0.150    0.150    0.150 :0(range)
        1    0.000    0.000    0.000    0.000 :0(setprofile)
        1    1.155    1.155    1.305    1.305 <stdin>:1(count1)
        1    0.000    0.000    1.305    1.305 <string>:1(<module>)
        1    0.000    0.000    1.305    1.305 profile:0(count1(10000001))
        0    0.000             0.000          profile:0(profiler)

sum関数で処理

ループをやめて、sum関数を使ってみたところ、さらに早くなりました。1秒程度で処理できました！1行に収まるし、読みやすいです。

1
2
3
4
5
6
7
8
9
10
11
12
>>> profile.run('sum(range(1,10000001))')
        5 function calls in 1.005 CPU seconds

   Ordered by: standard name

   ncalls  tottime  percall  cumtime  percall filename:lineno(function)
        1    0.147    0.147    0.147    0.147 :0(range)
        1    0.000    0.000    0.000    0.000 :0(setprofile)
        1    0.762    0.762    0.762    0.762 :0(sum)
        1    0.095    0.095    1.004    1.004 <string>:1(<module>)
        0    0.000             0.000          profile:0(profiler)
        1    0.000    0.000    1.005    1.005 profile:0(sum(range(1,10000001)))

2. 長整数型による性能劣化

　Pythonでは、計算結果は長整数型になっておりその影響による性能劣化はあると思います。また、誤差こそでていませんが、PHPでの計算結果はfloat(50000005000000)となっています。おそらく、内部的には倍精度(64bit)の浮動小数点数となっているのだと思いますが、厳密には正しくありません。結果が正しくないのではいくら処理が早くても意味がないので、数値演算に関してはPythonのほうが優れているといえます。

まとめ

  • ループをまわすときは、特別な理由がない限り、for in が優れている。
  • sum関数など、特化した関数があれば、その関数を使ったほうが良い。
  • Pythonの整数演算は、intの範囲を超えても自動的に長整数型になるので誤差を心配しなくてよい。

2011年1月12日　0:05追記
　xrangeだともっと早くなるとの指摘をうけ、検証してみました。実際に2割程度高速化しました。⇒Xrangeで高速化

Tags:
2 Comments »