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

# 概要

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

https://atcoder.jp/contests/language-test-202301


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

https://qiita.com/y-oksaku/items/f0c5c4681bc30dddf7f4

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


# 測定方法
- 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回だけコードテストに提出（実行）した際の結果を評価している。つまり、提出ごとの実行速度のブレについては評価していない。

    ``` python
    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になったので、今後の指標にしたく調べました。

https://atcoder.jp/contests/abc317/tasks/abc317_c

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

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


# 各測定結果の詳細
## ループ

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

## ソート
```python
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系が速かったです。

### +で結合
```python
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で結合
```python
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|


## 再帰
```python
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)呼び出し
```python
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が圧倒的に早いです。




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