Help us understand the problem. What is going on with this article?

【競プロ】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

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

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を使うほうが良さそうですが,再帰関数によるDPなどを行う場合は,Pythonのほうが高速になるようです.

Why not register and get more from Qiita?
  1. We will deliver articles that match you
    By following users and tags, you can catch up information on technical fields that you are interested in as a whole
  2. you can read useful information later efficiently
    By "stocking" the articles you like, you can search right away
Comments
No comments
Sign up for free and join this conversation.
If you already have a Qiita account
Why do not you register as a user and use Qiita more conveniently?
You need to log in to use this function. Qiita can be used more conveniently after logging in.
You seem to be reading articles frequently this month. Qiita can be used more conveniently after logging in.
  1. We will deliver articles that match you
    By following users and tags, you can catch up information on technical fields that you are interested in as a whole
  2. you can read useful information later efficiently
    By "stocking" the articles you like, you can search right away
ユーザーは見つかりませんでした