はじめに

最近、PythonでAtCoderなどの競技プログラミングに挑戦しています。これまであまりに気にしなかったけど、ちょっとした書き方で処理速度が変わってくることに気づいたので、これを気に少し調べてみました。

目次にあるように、標準入力、ソート、ループ、リストについて、計8個の処理の速度比較を行いました。処理速度の計測方法は、Mac Book Pro*1を使い、timeitでそれぞれ100回計測*2し、平均と標準偏差を求めています。

結果だけ知りたい方は、まとめへどうぞ。

計測に用いたコードは以下にあります。

github.com

また、グラフ描画には、xkcdスタイルを使用しています。

www.kumilog.net

標準入力

input と sys.stdin.readline

競技プログラミング以外では使う機会は少ないかもしれませんが、Python3の標準入力には、input()とsys.stdin.readline()の2種類があります。

のように1行目にデータ数が書かれており、その後に数値データが書かれているテキストファイルを用意し、標準入力で読み込むことを考えます。input()とsys.stdin.readline()のそれぞれ、以下のようにすると、全データを読み込むことができます。

# input()
N = int(input())
A = [int(input()) for _ in range(N)]

# sys.stdin.readline()
import sys
input = sys.stdin.readline

N = int(input())
A = [int(input()) for _ in range(N)]

データ数を $10 ^ 6$ としたときの結果です。

	平均(ms)	標準偏差(ms)
input()	392.40	24.36
sys.stdin.readline()	37.09	1.88

f:id:xkumiyu:20180818183736p:plain

驚くべきことに、10倍以上異なります。競技プログラミングでは、実行時間制限が2 secの場合が多く、入力データ数が 10⁶ の場合だと、0.3~0.4 sec の差はかなり大きいものとなります。

上記のように

import sys
input = sys.stdin.readline

とするだけで、基本はinput()と同じように使えると思います。

ソート

sort と sorted

ソートには、リストのメソッドであるsort()と組み込み関数のsorted()があります。前者はリストそのものを変更する破壊的メソッドです。事前に、要素数が 10⁶ で、ランダムな整数値が格納されているリストAを用意しておき、以下のようにソートを実行したときの処理速度を計測します。

# sort()
A.sort()

# sorted()
A = sorted(A)

結果は、次のようになりました。

	平均(ms)	標準偏差(ms)
sort()	88.54	56.98
sorted()	127.03	7.51

f:id:xkumiyu:20180819085344p:plain

sort()のほうが高速ですが、標準偏差が大きいことがわかりました。ただ、リストの中身の値によってもソートの処理速度は変わることに注意が必要です。今回は、ランダムな整数値をもつリストを1回作成し、同じリストを用いて計測を行っていますが、別のランダムなリストや偏りのあるリストなどではまた違った結果になることでしょう。

ソートの key

次に、二次元配列や辞書などをソートするときのkeyについて調べてみます。通常は、無名関数 lambda で指定することが多いかもしれませんが、operator.itemgetterを用いることもできます。

先程と同じ要領で、事前にランダムな整数値が格納されている二次元リストA（次元は10⁶ x 2）を用意しておき、以下のようにソートを実行したときの処理速度を計測します。keyの指定方法がlambdaとitemgetterの2種類あり、ソートの方法がsortとsortedの2種類あるので、計4パターンで実験しています。

# sort, lambda
A.sort(key=lambda x: x[1])

# sort, itemgetter
from operator import itemgetter
A.sort(key=itemgetter(1))

# sorted, lambda
A = sorted(A, key=lambda x: x[1])

# sorted, itemgetter
from operator import itemgetter
A = sorted(A, key=itemgetter(1))

	平均(ms)	標準偏差(ms)
sort, lambda	641.17	29.69
sort, itemgetter	521.91	4.91
sorted, lambda	688.45	35.24
sorted, itemgetter	588.17	15.32

f:id:xkumiyu:20180819085549p:plain

いずれも一次元のソートに比べ、5~6倍の時間がかかっています。sort と sorted の結果と同じく、sortの方が速いです。

lambdaとitemgetterですが、itemgetterの方が速い結果となっています。可読性もitemgetterの方が良いので、複雑なkeyが必要でない場合は、itemgetterを用いるのが良さそうです。（ちなみに、リストだけでなく、itemgetter('key')のようにすれば辞書に対しても使うことができます。）

ループ

for と while

ループについては、forとwhileについて比べてみました。

# for _ in range(N)
for _ in range(N):
    pass

# for i in range(N)
for i in range(N):
    i

# while i < N
i = 0
while i < N:
    i += 1

N = 10⁶ としたときの結果は以下になります。

	平均(ms)	標準偏差(ms)
for _ in range(N)	20.63	0.89
for i in range(N)	25.66	0.93
while i < N	51.36	1.44

f:id:xkumiyu:20180819085755p:plain

また、 N = 10⁶ だけでなく N = 10⁵, 10⁷についても調べてみました。

f:id:xkumiyu:20180819085801p:plain

結果は、forの方が2倍速いようです。whileを使う必要がない場合は基本的にforを使うようにしましょう。

なお、rangeの内部はインクリメントを含めCで書かれていますが、whileの場合、Pythonでi += 1と書く必要があるため、その差でwhileの方が遅いようです*3。

競技プログラミングのバイブルとして有名な蟻本には、実行時間制限が 1sec の場合

10⁶ 余裕を持って間に合う

10⁷ おそらく間に合う

10⁸ 非常にシンプルな処理でない限り厳しい

と記載があり、こちらの記事では、蟻本の記述は8年前のものであり、最近のPCであれば一桁増えても大丈夫というような記載もあります。

しかし、いずれもC++での処理速度であり、Pythonの場合は1桁か2桁遅いです。表にすると以下のようなイメージでしょうか。

	C++	Python
10⁵		余裕を持って間に合う
10⁶	余裕を持って間に合う	おそらく間に合う
10⁷	おそらく間に合う	非常にシンプルな処理でない限り厳しい
10⁸	非常にシンプルな処理でない限り厳しい