カレーちゃんブログ

Kaggleや競技プログラミングなどのこと

KaggleNotebookでPyPy、Cythonの速度比較

Python Kaggle notebook

Kaggle NotebookでPyPyやCythonがどれぐらい使えるか試してみましたという記事です。
【競プロ】PythonとPyPyの速度比較 - Qiitaを参考にしています。
時間は１度の計測で測っており、コードの書き方も色々とあるので、大体こんな感じと捉えてもらえると良いんじゃないでしょうか。

PythonとPyPyは同じコードで実行。Cythonは型を指定しないと遅いので、指定する方法で実行しました。

この記事はKaggle Advent Calendar 2022の15日目の記事です。

NotebookでPyPyとCythonの使うための準備

PyPy

!apt-get install pypy -y

PyPyは、このコマンドでインストールした後、マジックコマンド%%pypyで使用することができます。

Cython

Cythonは、%load_ext Cythonでマジックコマンドを有効にした後、マジックコマンド%%cythonで使用することができます。

実際に動かしたnotebookを公開していますので、こちらを見てもらうと使い方がすぐにわかると思います。
https://www.kaggle.com/code/currypurin/python-pypy-cython-comparison-v2

ループ

for i in range(10**8):  # 10^8
    pass
Python PyPy Cython
4.13s 376ms 388ms

PyPy、Cythonにすることで早くなります

Cythonは型を指定する場合、例えば次のように書く。
以降は個別には書かないのでどのようなコードにしたかは、notebookを見てもらえれば。

cdef long i
for i in range(10**8):
    pass

代入文

ans = 0
for i in range(10**8):
    ans = i
Python PyPy Cython
8.21.s 603ms 405ms

単純なloopと比べて、PythonとPyPyはやや遅くなる。Cythonはほぼ変わりません。

四則演算（定数）

for i in range(10**8):
    1 + 1
    1 - 1
    1 * 1
    1 // 1
Python PyPy Cython
3.79s 377ms 370ms

四則演算しても、単純なloopと変わらないということなんでしょうか。

四則演算（変数）

for i in range(2, 10**8):
    i * (i % (i - 1)) + i
Python PyPy Cython
19.6s 1.78ms 356ms

変数の四則演算は、PythonとPyPyは定数の四則演算に比べて遅い。Cythonは変わらず。

大きい数の演算

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

print(len(str(prd)))
Python PyPy Cython
7.88s 5.67s -

大きい数（ここでは、最終的に50万桁）は、PythonとPyPyはあまり変わらす。 Cythonは大きい数を扱うことができず。逆に大きい数を扱うときはオーバーフローしないように注意する必要がある。Cythonを使うときは整数型のオーバーフローに気を付けよう: 笑い猫の科学技術の備忘録が参考になりました。

if文

for i in range(10**8):
    if i == 0:
        pass
Python PyPy Cython
8.74s 346ms 360ms

if文は単純はloopとほぼ変わらず。Pythonは単純なloopよりやや遅い。

ここからリストです

シーケンシャルアクセス

A = [i for i in range(10**7)]

for a in A:
    pass
Python(全体) Python(ループのみ) PyPy(全体) PyPy(ループのみ) Cython(全体)
1.1s 398ms 247ms 34ms 540ms

Cythonは次のようなコードで、全体でどれぐらいかかっているかという時間です。（以降同じ）

cdef long a
cdef long[10_000_000] A

for a in A:
    pass

ランダムアクセス(Read)

A = [i for i in range(10**7)]

for i in range(10**7):
    A[i]
Python(全体) Python(ループのみ) PyPy(全体) PyPy(ループのみ) Cython(全体)
1.79s 1020ms 278ms 31ms 554ms

シーケンシャルアクセスと比べ、やや遅くなる。CythonよりもPyPyの方がやや早い。

ランダムアクセス(Write)

A = [i for i in range(10**7)]

for i in range(10**7):
    A[i] = 0
Python(全体) Python(ループのみ) PyPy(全体) PyPy(ループのみ) Cython(全体)
1.75s 1070ms 238ms 32ms 586ms

書き込みしてもほぼ時間は変わらず。

ソート

from random import randint, seed
seed(0)
A = [randint(1, 1000000) for _ in range(10**6)]  # 10^6
Python(全体) Python(ソートのみ) PyPy(全体) PyPy(ソートのみ) Cython(全体)
1.85s 338ms 440ms 228ms 715ms

PyPYのソートは早いんでしょうか。

文字列結合 (+による結合）

ans = ''
for i in range(10**5):  # 10**5 or 10**6
    ans += 'a'
Python(105) Python(106) PyPy(105) Cython(105)
20.1ms 180ms 180ms 910ms

PyPyもCythonも文字列の結合は遅いので、Pythonを使うとよさそうです。

文字列結合 (joinによる結合）

A = [str(i) for i in range(10**7)]  # 10^7
ans = ''.join(A)
Python PyPy Cython
2.89s 1.73s 3.26s

joinによる結合は、PyPyがやや早いが、これもPythonで良さそう。

deque

from collections import deque

que = deque(range(10**7))

for i in range(10**7):  # 10^7
    que.append(que.popleft())
Python PyPy Cython
2.26s 1.26s 3.18s

優先度付きキュー

import heapq

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

for i in range(10**7):
    heapq.heappop(que)
Python PyPy Cython
11.2s 5.35s 9.77s

dequeも優先度付きキューもPyPyはPythonの半分の時間くらい。

組み込み関数呼び出し

for i in range(10**7):  # 10^7
    max(0, i)
Python PyPy Cython
2.63s 165ms 505ms

PyPyが早いです。

ユーザ関数呼び出し

def func():
    return 0

for _ in range(10**7):  # 10^7
    func()
Python PyPy Cython
1.38s 172ms 563ms 
cdef long i

cdef func():
    return 0

for i in range(10**7):  # 10^7
    func()

Cythonの場合は、このようにcdefと定義すると早い。
それでもPyPyの方が早かったです。

再帰関数

import sys
sys.setrecursionlimit(10**7)

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

print(dp(10**4))  # 10^4
Python PyPy Cython
16.1ms 153ms 656ms

再帰関数は10**5だとnotebookが落ちてしまう。なぜだろう。
再帰関数はPythonを使うのが良さそうです。

参考にしたページ

気になることがあれば、コメントかtwitterまでお願いします。

もらったコメント