Supershipの名畑です。2023年春アニメは、新作であればスキップとローファーが今のところ見た中では最も好きです。OPもかなりセンスよすぎる。
AtCoderについて調べてみたシリーズの過去記事
はじめに
AtCoderでは問題毎に実行時間制限というものが決められています。この時間内でプログラムの実行を終わらせなければいけないという時間的な上限値です。
同じような処理をコードに落とし込んだとしても、プログラミング言語によって実施時間は異なるわけであり、つまりは競技プログラミングにおいてはどの言語を選ぶかというのは一つの重要ポイントになります。
人気言語であるPythonにはPyPyという処理系があります。実行速度の点で強みがあることからAtCoderではPythonではなくPyPyで提出する人が多くいます。
私もそれに倣いPyPyで提出しているのですが、実際に自分で速度を比べたことがあるわけではありません。
ですので比べてみたというのが今回の記事の内容です。
対象
どのような条件でどのようなコードで比較するべきかというのはかなり悩ましいものです。繰り返しや配列操作等の処理別に比較することもできますが、それはAtCoderにおける速さを比較することに果たしてなるのか。
考えた結果、今回についてはAtCoderでどちらのコードが速いかを知りたいという目的のため実際にAtCoderで提出されたコードでACだったものが何秒かかっているかを集計することにしてみました。
対象のコンテストは2023年4月1日に開催されたAtCoder Beginner Contest 296です。このコンテストを選んだ深い意味はありません。最近のコンテストを選んだというだけです。
このコンテストで開催時間である21:00-22:40の間にされた提出についてACのもののみに限定しPython (3.8.2)とPyPy3 (7.3.0)のそれぞれで中央値、平均値、最大値、最小値、それと提出数を表にしてみました。
G - Polygon and PointsついてはPython (3.8.2)でのACが、Ex - UniteについてはPython (3.8.2)とPyPy3 (7.3.0)の両方でのACがなかったため対象外としています。
ABC296での結果
A - Alternately
| Python (3.8.2) | PyPy3 (7.3.0) | |
|---|---|---|
| 中央値(ms) | 25 | 71 |
| 平均値(ms) | 25.82 | 108.62 |
| 最大値(ms) | 389 | 915 |
| 最小値(ms) | 18 | 60 |
| 提出数 | 838 | 963 |
単純な文字列操作の問題です。
どこを比べてもPythonがPyPyよりも速いという結果になりました。
B - Chessboard
| Python (3.8.2) | PyPy3 (7.3.0) | |
|---|---|---|
| 中央値(ms) | 25 | 71 |
| 平均値(ms) | 26.40 | 106.51 |
| 最大値(ms) | 373 | 1358 |
| 最小値(ms) | 18 | 60 |
| 提出数 | 780 | 932 |
文字列から該当の文字を見つけ出す問題です。
この問題もPythonがPyPyよりも速いという結果になりました。
C - Gap Existence
| Python (3.8.2) | PyPy3 (7.3.0) | |
|---|---|---|
| 中央値(ms) | 171 | 155 |
| 平均値(ms) | 569.02 | 183.33 |
| 最大値(ms) | 1932 | 994 |
| 最小値(ms) | 103 | 127 |
| 提出数 | 453 | 909 |
中央値や平均値ではPyPyに軍配が上がっていますが、最小値がPythonです。書き方に左右される部分がかなりあるってことですかね。
D - M<=ab
| Python (3.8.2) | PyPy3 (7.3.0) | |
|---|---|---|
| 中央値(ms) | 482 | 132 |
| 平均値(ms) | 569.02 | 258.73 |
| 最大値(ms) | 1744 | 1987 |
| 最小値(ms) | 122 | 62 |
| 提出数 | 62 | 406 |
ここから先の問題はすべて中央値、平均値、最小値においてPyPyの勝利です。
E - Transition Game
| Python (3.8.2) | PyPy3 (7.3.0) | |
|---|---|---|
| 中央値(ms) | 750 | 272.5 |
| 平均値(ms) | 844.00 | 424.95 |
| 最大値(ms) | 1853 | 1903 |
| 最小値(ms) | 135 | 117 |
| 提出数 | 29 | 236 |
F - Simultaneous Swap
| Python (3.8.2) | PyPy3 (7.3.0) | |
|---|---|---|
| 中央値(ms) | 634.5 | 384 |
| 平均値(ms) | 917.33 | 479.78 |
| 最大値(ms) | 1731 | 1632 |
| 最小値(ms) | 379 | 169 |
| 提出数 | 6 | 80 |
最後に
予想通りではありますが、実行速度は処理によるため、なんとも言いづらい結果となりました。
単純に今回の比較だけで判断するならば、問題が難しくなるほどにPyPyが速度面で優秀なため、ひとまずPyPyを選んでおけば無難であるとは言えますでしょうか。書き方によってはPythonでも実行時間制限を余裕で下回るという言い方もできますでしょうか。
言語の差よりも書き方の差の方が大きいと言える結果ではあります。
そのうち全プログラミング言語を対象とした速度調査もやってみたいと考えています。
宣伝
SupershipのQiita Organizationを合わせてご覧いただけますと嬉しいです。他のメンバーの記事も多数あります。
Supershipではプロダクト開発やサービス開発に関わる方を絶賛募集しております。
興味がある方はSupership株式会社 採用サイトよりご確認ください。