PyPyがCPythonより遅くなるとき @ Project Euler Problem 40
仰々しいタイトルだけど、よくある話。
「文字列の結合はjoin()を使おう」で分かる人は、これを読んでも新たに得ることはないと思う。
結論から言うと、join()を使えば例によってPyPyの方が断然速いのでご心配なく。
実験環境:Win7, C2D P8400(2.26GHz), RAM 4GB
Problem 40
数列 01234567891011121314... の、第 1, 10, 100, 1000, 10000, 100000, 1000000 項の総乗を求める問題(ただし第 0 項から始める)。
まずは何も考えずに次のようなコードを書いた。
digits = '0' i = 0 while len(digits) < 1000001: i += 1 digits += str(i) product = 1 for j in [10**i for i in range(7)]: product *= int(digits[j]) print product
これでもCPython(2.7)での計算時間は0.23秒くらいなので何の問題もない。
しかし、これをPyPy(1.9)で実行すると100秒かかる。なぜだ…?
解決編
問題は、文字列の結合に+演算子を使っいるところだった。
少し冗長になるけど、リストに追加していき、最後にjoin()で結合する。
digits = ['0'] i = 0 len_digits = 1 while len_digits < 1000001: i += 1 i_str = str(i) digits.append(i_str) len_digits += len(i_str) digits = ''.join(digits) product = 1 for j in [10**i for i in range(7)]: product *= int(digits[j]) print product
結果は、CPython:約0.47秒,PyPy:約0.05秒!
もう少し詳しい比較
CPythonとPyPyで文字列の結合を比較する。
・文字列の結合 - ひきメモ
http://d.hatena.ne.jp/yumimue/20071226/1198670253
↑を参考に、文字列の結合をaddとjoinで、それぞれ100回ずつ実行して比較する。
stopを大きくすると、結合する回数・文字列の長さが大きくなる。
from timeit import Timer add_stmt = """ x = '' for i in xrange(stop): x += str(i) """ join_stmt = """ x = [] for i in xrange(stop): x.append(str(i)) "".join(x) """ print ' add:', Timer(add_stmt).timeit(number=100) print 'join:', Timer(join_stmt).timeit(number=100)
結果
stop = 1000 のとき
CPython add: 0.0734560174198 join: 0.0449884423221 PyPy add: 0.129551967885 join: 0.0149099479361
stop = 10000 のとき
CPython add: 1.59279474796 join: 1.30976071259 PyPy add: 16.4056196944 ← 既にけっこうヤバい join: 0.106286706497
stop = 100000 のとき
CPython add: 12.2056071042 join: 9.95530729293 PyPy add: 2778.15044501 ← 超遅い join: 1.95737834548 ← 超速い
結論
文字列を結合するときは、─ CPythonでは大して変わらないけど ─ とにかくjoin()を使おう。
PEP 8 -- Style Guide for Python Code
ソースコードは Python の実装(PyPy、Jython、IronPython、Pyrex、Psyco など)ごとの欠点を引き出さないように書くべきである。たとえば、CPython が a+=b や a=a+b などの文字列連結をインプレイス処理して、効率よく動作する実装に依存してはならない。これでは Jython での動作が遅く
なってしまう。パフォーマンスに敏感な部分では、''.join() を使うべきである。こう書いておけば、様々な実装において、連結処理は線形時間で処理できる。
参考になった記事
・文字列の結合 - ひきメモ
http://d.hatena.ne.jp/yumimue/20071226/1198670253
・文字列結合のベンチマークをいろんな処理系でやってみた
http://www.slideshare.net/kwatch/ss-8933694