【競プロ】PythonとPyPyの速度比較

概要

競技プログラミングを行っているときに，PythonでTLEを出したコードをPyPyで出すとACになったり，逆にPyPyでは通らないコードがPythonでは通ったりして，やりづらかったので，どちらで出すべきかを考えるために，よく使う手法それぞれの実行時間を計測しました．

計測時間はすべてAtCoderのコードテストで測定しています．

新ジャッジシステム

新ジャッジでの結果に更新しました．Python，PyPy共に速度の改善が見られます．特にPyPyは相当早くなっています．

ループ

for i in range(100000000):  # 10^8
    pass

	Python	PyPy
最高	3029 ms	154 ms
最低	3111 ms	155 ms

Pythonではただのループがすでに遅いようです．

代入文

ans = 0
for i in range(100000000):  # 10^8
    ans = i

	Python	PyPy
最高	5467 ms	154 ms
最低	5715 ms	158 ms

代入文を追加するだけで数秒遅くなりました．ans = 1としても5秒弱ほどかかりました．

四則演算(定数)

for i in range(100000000):  # 10^8
    1 + 1
    1 - 1
    1 * 1
    1 // 1

	Python	PyPy
最高	3108 ms	149 ms
最低	3111 ms	151 ms

小さな定数の演算は共にコストが掛からないようです．

四則演算(変数)

for i in range(2, 10000000):  # 10^7
    i * (i % (i - 1)) + i

	Python	PyPy	PyPy (10^8)
最高	1508 ms	190 ms	1345 ms
最低	1655 ms	192 ms	1349 ms

定数の演算に比べるとかなりのコストが掛かります(特に除算・剰余)．

大きい数の演算

prd = 1
for a in range(1, 110_000):
    prd *= a

	Python	PyPy
最高	3044 ms	3417 ms
最低	3048 ms	3414 ms

大きい数字を扱う場合はPythonの方が速いことがあります．例えばABC151EでLCMをそのまま計算するとPythonではACなのにPyPyではTLEになりました．

if文

for i in range(100000000):  # 10^8
    if i == 0:
        pass

	Python	PyPy
最高	5179 ms	149 ms
最低	5191 ms	150 ms

Pythonでのif文はコストが掛かりますが，代入よりはコストが小さいようです．そのため次のコード#1より#2の方が早く動作することがあります．

a = min(a, new_value)  # 1

if a > new_value:  # 2
    a = new_value

配列アクセス

シーケンシャルアクセス

A = [i for i in range(10000000)]  # 10^7

for a in A:
    pass

	Python(全体)	Python(ループのみ)	PyPy(全体)	PyPy(ループのみ)
最高	776 ms	196 ms	592 ms	19 ms
最低	803 ms	201 ms	607 ms	19 ms

PyPyだと配列の生成が遅いようです．

ランダムアクセス(Read)

A = [i for i in range(10000000)]  # 10^7

for i in range(10000000):
    A[i]

	Python(全体)	Python(ループのみ)	PyPy(全体)	PyPy(ループのみ)
最高	1246 ms	625 ms	567 ms	14 ms
最低	1292 ms	679 ms	603 ms	14 ms

ランダムアクセス(Write)

A = [i for i in range(10000000)]  # 10^7

for i in range(10000000):
    A[i] = 0

	Python(全体)	Python(ループのみ)	PyPy(全体)	PyPy(ループのみ)
最高	1171 ms	695 ms	567 ms	189 ms
最低	1205 ms	725 ms	607 ms	195 ms

配列へのランダムアクセスは共にシーケンシャルアクセスよりコストが掛かりそうです．また書き込みの方が若干遅くなります．

ソート

from random import randint, seed
seed(0)

A = [randint(1, 1000000) for _ in range(1000000)]  # 10^6
A.sort()

	Python(全体)	Python(ソートのみ)	PyPy(全体)	PyPy(ソートのみ)
最高	994 ms	894 ms	447 ms	280 ms
最低	1013 ms	907 ms	457 ms	282 ms

PyPy早いですね．

文字列結合

+による結合

ans = ''
for i in range(100000):  # 10**5
    ans += 'a'

	Python(10^5)	Python(10^6)	PyPy(10^5)	PyPy(10^6)
最高	29 ms	156 ms	475 ms	エラー
最低	29 ms	199 ms	545 ms	エラー

PyPyの+による長い文字列の結合は遅いようです．

joinによる結合

A = [str(i) for i in range(10000000)]  # 10^7
ans = ''.join(A)

	Python(全体)	Python(joinのみ)	PyPy(全体)	PyPy(joinのみ)
最高	2386 ms	171 ms	1509 ms	125 ms
最低	2283 ms	174 ms	1541 ms	133 ms

意外にもPythonではjoinを用いたほうがやや遅くなるようです．
一方で，PyPyではjoinを使うと非常に高速に動くようになります．

• Pythonでは 'a' + 'b'
• PyPyでは ''.join(['a', 'b'])

と書くのが良さそうです．

モジュール

deque

from collections import deque

que = deque(range(10000000))

for i in range(10000000):  # 10^7
    que.append(que.popleft())

	Python	Python(pass)	PyPy	PyPy(pass)
最高	1501 ms	789 ms	892 ms	685 ms
最低	1571 ms	801 ms	927 ms	704 ms

ループ内の処理をpassに変えた場合の処理時間を考えると，PyPyの方が高速に動いてそうです．

優先度付きキュー

import heapq

que = [0]
for i in range(10000000):  # 10^7
    heapq.heappush(que, i)

for i in range(10000000):
    heapq.heappop(que)

	Python	Python(pass)	PyPy	PyPy(pass)
最高	6701 ms	639 ms	3248 ms	81 ms
最低	6669 ms	697 ms	3278 ms	82 ms

PyPyの方が2倍ほど早いです．

組み込み関数呼び出し

for i in range(10000000):  # 10^7
    max(0, i)

	Python	PyPy
最高	1765 ms	72 ms
最低	1831 ms	74 ms

Pythonだとそこそこコストが掛かります．

ユーザ関数呼び出し

def func():
    return 0

for _ in range(10000000):  # 10^7
    func()

	Python	PyPy
最高	786 ms	86 ms
最低	782 ms	74 ms

ユーザ関数とビルトイン関数の呼び出しのコストには差は無いようです．ただしあくまでも呼び出しのコストだけなので，基本的にはビルトイン関数のほうが早くなります．

再帰関数

import sys
sys.setrecursionlimit(10**7)

def dp(N):
    if N == 0:
        return 0
    else:
        return 1 + dp(N - 1)

print(dp(1000000))  # 10^6

	Python	PyPy
最高	660 ms	1114 ms
最低	683 ms	1297 ms

PyPyの再帰関数の処理速度がかなり改善されています．

まとめ

	Pyhon	PyPy
ループ	×	○
代入文	×	○
四則演算	×	○
大きい数の演算	△	△
if	×	○
シーケンシャルアクセス	×	○
ランダムアクセス	×	○
ソート	×	○
'a' + 'b'	△	×
join	△	○
deque	×	○
優先度付きキュー	×	○
組み込み関数	×	○
ユーザ関数	×	○
再帰関数	○	×

基本的にはPyPyを使うほうが良さそうですが，再帰関数を用いる場合は注意が必要です．