PyPyを速くする（1） sort

PyPyは同じソースを動かしてもPythonよりたいてい速いのですが、遅くなることもあります。その対処法がいくつかあるので紹介していきます。

今回はリストのソートです。こんなコードを動かしてみます。

from itertools import *
import time

def gen_S():
	S = 290797
	while True:
		S = S * S % 50515093
		yield S

def sort_long(N):
	a = list(islice(gen_S(), N))
	t0 = time.clock()
	a.sort()
	print time.clock() - t0

N = 10 ** 7
sort_long(N)

これを動かすと、Pythonで9秒、PyPyで25秒でした。
これがなぜ遅いかというと、リストに多倍長整数が混じっているからのようです。この要素は大きさとしては32ビットの範囲に収まるのですが、掛け算の段階で多倍長整数になって、それがそのまま残ってしまっているのです。次のように変更してみましょう。

def sort_int(N):
	a = map(int, islice(gen_S(), N))
	t0 = time.clock()
	a.sort()
	print time.clock() - t0

リストの要素を全て32ビット整数に直してからソートします。そうすると、Pythonで7秒、PyPyで2.3秒でした。まとめると、

	Python	PyPy
long	9秒	25秒
int	7秒	2.3秒

【結論】
できることならリストはソートする前に要素をintにしましょう。