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

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

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

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

# ループ
```python
for i in range(100000000):  # 10^8
    pass
```

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

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

# 代入文

```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秒弱ほどかかりました．

# 四則演算(定数)

```python
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 |

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

# 四則演算(変数)

```python
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 |

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

# 大きい数の演算
```python
prd = 1
for a in range(1, 110_000):
    prd *= a
```

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

大きい数字を扱う場合はPythonの方が速いことがあります．例えば[ABC151E](https://atcoder.jp/contests/abc152/tasks/abc152_e)でLCMをそのまま計算するとPythonではACなのにPyPyではTLEになりました．

# ```if```文
```python
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```の方が早く動作することがあります．

```python
a = min(a, new_value)  # 1

if a > new_value:  # 2
    a = new_value
```

# 配列アクセス
## シーケンシャルアクセス
```python
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)

```python
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)

```python
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 |

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

# ソート
```python
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早いですね．

# 文字列結合
## ```+```による結合

```python
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```による結合

```python
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
```python
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の方が高速に動いてそうです．

## 優先度付きキュー

```python
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倍ほど早いです．

# 組み込み関数呼び出し

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

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

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

# ユーザ関数呼び出し

```python
def func():
    return 0

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

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

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

# 再帰関数

```python
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を使うほうが良さそうですが，再帰関数を用いる場合は注意が必要です．