matsulibの日記

Ingredients as Code

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、JythonIronPython、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