CPythonとPyPyの比較

ABC341CでCPythonだとTLEする問題から処理系の特徴を把握すべきだろうと比較を行った記録

CPythonとPyPyの違い

こちらの記事がたぶん全てなので正直改めて検証する必要もないけどせっかくなのでやりました。

【AtCoder】Pythonで競プロをするときの注意点まとめ【競技プログラミング】 #Python - Qiita

雑にまとめるとモジュールのインポートや再帰関数を使う場合はCPythonのほうが良いらしい？

ので本記事では

・シンプルに計算量の多そうな問題

・再帰関数を使う問題

・外部モジュールを呼び出す問題（DFS）

で両処理系の比較をしてみます。

AtCoder Beginner Contest 338　C - Leftover Recipes

リンク：C - Leftover Recipes (atcoder.jp)

概要：種類の材料から料理と料理を作ります。作れる最大数を出力してね

いずれかの料理の数を固定してもう一方を作れる最大数を探索を繰り返すシンプルながら試行回数が多くなるケースがある全探索問題です。

計算量はです。

CPythonで公式解説の通りやると一部ケースでTLEしました。

（探索の途中で不可能がわかったらbreakする処理したらギリ通せた）

#ABC338 C - Leftover Recipes
N=int(input())
Q=list(map(int, input().split()))
A=list(map(int, input().split()))
B=list(map(int, input().split()))

ans=0
for a in range(10**6+1):
    b=10**8
    for i in range(N):
        if Q[i]-A[i]*a<0:
            b=-10**8
        elif B[i]>0:
            b=min(b,(Q[i]-A[i]*a)//B[i])
    ans=max(ans,a+b)
print(ans) 

結果

Cpython：AC12、TLE6

提出 #49744255 - AtCoder Beginner Contest 338

PyPy：AC（170ms）

提出 #50453575 - AtCoder Beginner Contest 338

想定通りPyPyのほうが格段に速くACできました。

AtCoder Beginner Contest 247 C - 1 2 1 3 1 2 1

リンク：C - 1 2 1 3 1 2 1 (atcoder.jp)

概要：の文字列を出力してね

再帰を使った問題です。

メモ化が必要なので外部モジュールも使って自動メモ化を行っています。

#ABC247 C - 1 2 1 3 1 2 1
from functools import cache
@cache
def f(N):
    if N == 1:
        return [1]
    else:
        return f(N-1) + [N] + f(N-1)
n = int(input())
ans = f(n)
print(*ans, sep = ' ')   

結果

CPython：AC（26ms）

提出 #50268949 - AtCoder Beginner Contest 247

PyPy：AC（84ms）

提出 #50453784 - AtCoder Beginner Contest 247

確かにPyPyのほうが遅いです。

AtCoder Beginner Contest 293 C - Make Takahashi Happy

リンク：C - Make Takahashi Happy (atcoder.jp)

概要：互いに異なる整数の書かれたマスだけ踏んでゴールできる組み合わせ数を出力してね

外部モジュールdequeを使ったDFSです。

#ABC293 C - Make Takahashi Happy
from collections import deque
H, W = map(int, input().split())
A = []
for x in range(H):
    a = list(map(int, input().split()))
    A.append(a)
#print(A)

q = deque([[0, 0]])
pre = [-1]*(H+W-1)
count = 0

while q:
    cnt = q.popleft()
    x, y = cnt
    pre[x+y] = A[x][y]
    if x == H-1 and y == W-1:
        if len(pre) == len(set(pre)):
            count += 1
#            print(pre)
    else:
        nx = [x+1, y]
        ny = [x, y+1]
        if x+1 < H:
            q.appendleft(nx)
        if y+1 < W:
            q.appendleft(ny)

#    print(q)
#    print(pre)
print(count)   

結果

CPython：AC（117ms）

自分の提出 - AtCoder Beginner Contest 293

PyPy：AC（99ms）

提出 #50453875 - AtCoder Beginner Contest 293

計算量の多い問題ではモジュールインポートのデメリットより計算量のメリットが勝つこともあるようです。

結果

基本はPyPyで問題無いように思います。

再帰や外部モジュールを使ったコードでTLEするときは解法自体を見直したほうが良い場合が多そうです。

今まで特に考えずCPythonでやっていましたが今後はPyPyを主に使っていきます。