246
160

Delete article

Deleted articles cannot be recovered.

Draft of this article would be also deleted.

Are you sure you want to delete this article?

More than 3 years have passed since last update.

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

Last updated at Posted at 2019-08-06

概要

競技プログラミングを行っているときに,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を使うほうが良さそうですが,再帰関数を用いる場合は注意が必要です.

246
160
1

Register as a new user and use Qiita more conveniently

  1. You get articles that match your needs
  2. You can efficiently read back useful information
  3. You can use dark theme
What you can do with signing up
246
160

Delete article

Deleted articles cannot be recovered.

Draft of this article would be also deleted.

Are you sure you want to delete this article?