AtcoderにおけるPython実行環境別の実行速度比較

概要

2023年にAtcoderのジャッジシステムにおける言語のアップデートが継続的に行われています

Pythonで提出していると環境ごとにTLEになったりならなかったりで困ったので、以下の記事を参考にPythonの実行環境ごとの実行速度の比較を行いました。

なお、大きな違いが表れていないものについては本記事では測定対象外にしています。
また、引用元の結果と比較できるよう、同様な操作について測定を行っています。

測定方法

• Atcoderのコードテスト上で測定対象の操作を実行し、その実行速度を測定する

• 測定対象の操作を5回実行し、平均、最大、最小値を求める

• 実行環境はAtcoder のジャッジシステムに実装されている以下の通り（2023年8月27日時点）

  • Cpython(3.11.4)
  • Mambaforge/Cpython 3.10.10
  • PyPy 3.10-v7,3,12
  • Cython 0.29

• 測定に用いたスクリプト

  • 操作自体の実行速度について着目するため、スクリプト内に操作を5回行うループを実装し測定を行うようにした。
  • このスクリプトを1回だけコードテストに提出（実行）した際の結果を評価している。つまり、提出ごとの実行速度のブレについては評価していない。

  import time
  import numpy as np
  import sys
  sys.setrecursionlimit(10**7)
  from random import randint, seed
  seed(0)
  
  def measure_function(func, iterations):
      run_times = []
      memory_usages = []
      
      for _ in range(iterations):
          start_time = time.time()
          func()  # 実行する関数
          end_time = time.time()
          
          run_time = end_time - start_time
          run_times.append(run_time)
  
      avg_run_time = np.mean(run_times)
      max_run_time = max(run_times)
      min_run_time = min(run_times)
      var_run_time = np.var(run_times)
  
      print("Average Run Time[ms]:", avg_run_time*10**3)
      print("Max Run Time[ms]:", max_run_time*10**3)
      print("Min Run Time[ms]:", min_run_time*10**3)
      print("Variance of Run Time[ms]:", var_run_time*10**3)
  
  # テストする関数
  def test_function():
      # something function
        
  # 関数のパフォーマンスを測定
  measure_function(test_function, iterations=5)
  

結果

×＜△＜〇＜★の順で相対的に評価しています。★は圧倒的に早い結果です。
基本的にCythonを選んでおけばよさそうです。

	Cpython	Mambaforge/Cpython	PyPy	Cython
ループ	×	×	〇	★
if文	×	×	〇	★
配列ランダムアクセス	△	△	★	〇
ソート	△	△	〇	△
文字結合(+)	〇	〇	×	△
文字結合(join)	△	×	〇	×
再帰	〇	△	△	★
組み込み関数	△	×	〇	★

留意点

ABC317 C問題がTLEだったのを実行環境を変えて提出したところACになったので、今後の指標にしたく調べました。

再帰を使って解く問題だったので今回の測定からしてCythonを使うと良いように思いますが、実際にはTLEになってしまい、逆にPyPyだとACになるんですよね。

なので、本測定結果を参考にする場合はコード中のどの操作が実行速度に効いてくるかに留意する必要があるかと思います。

各測定結果の詳細

ループ

def test_function():
    for i in range(10**8):
        pass

	Cpython	Mambaforge/Cpython	PyPy	Cython
平均[ms]	1491	1162	207	0.00033
最大[ms]	1587	1163	209	0.00072
最小[ms]	1361	1160	206	<0.00001

Cythonが圧倒的に早いです。
ループが入る場合はPyPyかCythonを使った方が無難です。

if文

def test_function():
  for i in range(10**7):
      if i == 0: pass

	Cpython	Mambaforge/Cpython	PyPy	Cython
平均[ms]	188	218	9	0.0002
最大[ms]	197	222	9	0.0005
最小[ms]	178	217	9	<0.0001

こちらもCythonが圧倒的に早いですね。
PyPyかCythonを使った方が無難です。

配列アクセス

ReadもWriteも傾向は同じでした。
PyPyが最も早く、Cythonが次点。

ランダムアクセス(Read)

def test_function():
  A = [i for i in range(10000000)]
  for i in range(10000000):
      A[i]

	Cpython	Mambaforge/Cpython	PyPy	Cython
平均[ms]	501	573	64	291
最大[ms]	502	576	67	292
最小[ms]	501	570	63	289

ランダムアクセス(Write)

def test_function():
  A = [i for i in range(10**7)] 
  for i in range(10**7):
    A[i] = 0

	Cpython	Mambaforge/Cpython	PyPy	Cython
平均[ms]	490	595	60	282
最大[ms]	492	596	63	282
最小[ms]	490	592	58	281

ソート

def test_function():
  A = [randint(1, 10**6) for _ in range(10**6)]
  A.sort()

	Cpython	Mambaforge/Cpython	PyPy	Cython
平均[ms]	606	745	151	593
最大[ms]	614	754	156	602
最小[ms]	598	736	149	589

PyPyを使っておけば安心かなと思います。

文字結合

演算子+で結合する方法とjoinで結合する方法がありますが、+で結合する方が早いです。
他の操作の傾向と異なり、文字列を+で結合する場合はCpython系が速かったです。

+で結合

def test_function():
  ans = ''
  for i in range(10**5):
      ans += 'a'

	Cpython	Mambaforge/Cpython	PyPy	Cython
平均[ms]	4	5	209	107
最大[ms]	4	5	211	107
最小[ms]	4	5	207	107

joinで結合

def test_function():
  A = [str(i) for i in range(10**7)]
  ans = ''.join(A)

	Cpython	Mambaforge/Cpython	PyPy	Cython
平均[ms]	1103	1301	606	1331
最大[ms]	1124	1304	751	1348
最小[ms]	1083	1299	508	1311

再帰

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

	Cpython	Mambaforge/Cpython	PyPy	Cython
平均[ms]	130	357	244	55
最大[ms]	130	465	685	73
最小[ms]	130	328	117	51
分散	0.00	2.91	49	0.06

Cythonが良さげです。
分散値も測定してみましたが、なぜかPyPyの測定値のばらつきが特に大きかったです。

組み込み関数(max)呼び出し

def test_function():
  for i in range(10**7):
      max(0, i)

	Cpython	Mambaforge/Cpython	PyPy	Cython
平均[ms]	1055	851	11	0.0002
最大[ms]	1067	853	12	0.0007
最小[ms]	1015	850	10	<0.0001

こちらもCythonが圧倒的に早いです。

以上です。
時間があればなぜこのような差が表れるか調査したいですね。