概要

AtCoder ABC151 に参加した。問題Dをこの問題にはおそらく最適ではない方法（ワーシャル-フロイド法）でC++/Python3/PyPy3で解いて実行時間を測定・比較してみた。

結果は問題サイズがある程度大きくなるとC++の方が安定して60倍-70倍程度高速だった。TLEの不安が少しでもある場合はPythonで~~実装する~~提出するのはやめたほうが良さそうである。

後日、コメントをいただいてPyPy3(2.4.0)で提出するとTLEが解消することがわかった。ただし実行時間は1191msecとC++の71msecにくらべるとかなり低速ではあった。

なのでTLEが不安なら、1. C++で実装提出 2.Pythonで実装PyPyで提出　とするのが良さそうである。

経緯

AtCode ABC151 に参加した。問題Dみたとき以下のように考えた。

「蟻本にのってた方法(ワーシャル-フロイド法)でとけるなぁ。でもノード（マス）は上下左右のとしかつながっていないし、隣り合うノード間の距離はいつも１だからもっと効率的な方法ありそう。

でもO(N^3)でN=400だから400^3 = 64,000,000かまぁいけるんじゃない？他の方法考えるのも面倒だしこれでやれば解けるのわかっているしワーシャル-フロイド法でいこう。」

とあまり深く考えずPythonで実装を実施。制限時間ぎりぎり(3分前)までしこしこデバッグして提出#9476488(20-01-12 22:37:01)したけど結果はTLE。悲しかった。

後日C++で実装して提出#9488496したところ実行時間は71msecと余裕。今後の参考にしたい。

1/15追記

コメントで「PyPy 3 で出したら TLE になりませんでしたよ. WA が3つ出ましたけど.」といただきました。
確かにPyPyで実施したところTLEはなくなりTLEでなくなったものからWAが出てくるようになりました。WAはINFを10**3に直したらACになりました。（提出#9513468）ただし実行時間は1191msecとTLEにはならないもののC++の71msecとは大きな差があった。

上記を受けて、自分のマシンでINF=10**3としたものでPython/PyPyで速度を再測定しました

速度比較結果

速度比率

(縦軸拡大)

上の図は

自宅のNUC(CentOS)上のubuntu KVMノードで実行する。
問題サイズを1から20まで変化させる。
C++/Python/PyPyで一つのサイズをそれぞれ5回繰り返し実行。
実行経過時間をtimeコマンドで測定する。
5回の実行の平均値を計算する。
縦軸を(Python or PyPyでの平均実行時間)/(C++での平均実行時間)、横軸を問題サイズ(H,W(H=W))としてプロットする。

して得られた結果である。

C++:PythonではPythonのコードはINF=100となっている。(このコードはPyPy3でAtCoderに提出するとWAがでる)
C++:Python(#2)、C++:PyPyではPythonのコードはINF=1000となっている。

INF=100とした時とINF=1000としたときで実行時間には大きな差がないのがわかる。
PythonとC++では問題サイズが大きい時、実行速度の比率は60倍以上になることがわかる。
PyPyとC++では問題サイズが大きい時、実行速度の比率は２倍程度であることがわかる。
AtCoderでの提出結果ではC++の実行時間が71msec、PyPy3の実行時間が1191msecと10倍以上の速度差があるのに、自分のサーバでは差が2倍程度しかないのは不思議である。もしかするとPyPyのバージョンがAtCoderは2.4.0であるのに対し、自宅サーバでは7.3.0 なのが関係しているのかもしれない。

myoden@ubuntu002:~/AtCoder/ABC151/D$ pypy3 -V 
Python 3.6.9 (1608da62bfc7, Dec 23 2019, 10:50:04)
[PyPy 7.3.0 with GCC 7.3.1 20180303 (Red Hat 7.3.1-5)]
myoden@ubuntu002:~/AtCoder/ABC151/D$`

使用した問題ケースについては後述。

実行経過時間
実行経過時間C++

実行経過時間Python(INF=100)

実行経過時間PyPy(INF=1000)

グラフでは5回実施したときの経過時間の最大値（MAX）、平均値（AV）、最小値（MIN）を示してある。

サンプルケース(参考)

問題サイズを変えた時のサンプルケースはH=WとしてH(=W)を1から20まで変化させて以下のような感じで作成した。

sampleSquare-10.in

myoden@ubuntu002:~/AtCoder/ABC151/D$ cat sampleSquare-10.in 
10 10
.#.#.#.#.#
..........
.#.#.#.#.#
..........
.#.#.#.#.#
..........
.#.#.#.#.#
..........
.#.#.#.#.#
..........

sampleSquare-20.in

myoden@ubuntu002:~/AtCoder/ABC151/D$ cat sampleSquare-20.in 
20 20
.#.#.#.#.#.#.#.#.#.#
....................
.#.#.#.#.#.#.#.#.#.#
....................
.#.#.#.#.#.#.#.#.#.#
....................
.#.#.#.#.#.#.#.#.#.#
....................
.#.#.#.#.#.#.#.#.#.#
....................
.#.#.#.#.#.#.#.#.#.#
....................
.#.#.#.#.#.#.#.#.#.#
....................
.#.#.#.#.#.#.#.#.#.#
....................
.#.#.#.#.#.#.#.#.#.#
....................
.#.#.#.#.#.#.#.#.#.#
....................
myoden@ubuntu002:~/AtCoder/ABC151/D$