Pythonの知っておくと良い細かい処理速度の違い8個

はじめに

最近、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種類があります。

100000
840
462
943
...

のように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)]

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

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

驚くべきことに、10倍以上異なります。AtCoderでは、実行時間制限が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

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

いずれも一次元のソートに比べ、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

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

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

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

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

10⁷ おそらく間に合う

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

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

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

	C++	Python
105		余裕を持って間に合う
106	余裕を持って間に合う	おそらく間に合う
107	おそらく間に合う	非常にシンプルな処理でない限り厳しい
108	非常にシンプルな処理でない限り厳しい

プログラミングコンテストチャレンジブック [第2版]　?問題解決のアルゴリズム活用力とコーディングテクニックを鍛える?

リスト

リストの初期化

リストの初期化には、単純に*演算子を使う方法や内包表記を用いる方法があります。

# [None] * N
[None] * N

# [None for _ in range(N)]
[None for _ in range(N)]

N = 10⁶ で計測した結果は以下になります。

	平均(ms)	標準偏差(ms)
[None] * N	5.15	0.41
[None for _ in range(N)]	41.17	2.05

以下は、N = 10⁵, 10⁷ を加えグラフにしたものです。

何からの処理をする場合は、内包表記は高速ですが、単に同じ値でリストの初期化する場合は、*演算子の方が8~9倍も速いです。

二次元配列の場合

二次元配列の初期化は、内包表記を使わなければなりませんが、すべての次元で内包表記を使うのではなく、最初の次元のみ内包表記を使う方が速くなります。N = 10³で実験した結果、10倍程度速くなりました。

# 速い
[[None] * N for _ in range(N)]

# 遅い
[[None for _ in range(N)] for _ in range(N)]

# NG
[[None] * N] * N

	平均(ms)	標準偏差(ms)
[[None] * N for _ in range(N)]	3.07	1.02
[[None for _ in range(N)] for _ in range(N)]	38.45	4.80

リストの値参照

rangeを使ってインデックスを作り、値を参照する方法と、そのままリストの値を参照する方法について、処理速度を比較しました。

# for i in range(len(A))
for i in range(len(A)):
    A[i]

# for a in A
for a in A:
    a

リストAの要素数が 10⁶ のときの結果は、以下の通りです。

	平均(ms)	標準偏差(ms)
for i in range(len(A))	41.14	0.56
for a in A	11.85	1.51

要素数を変化させたときの結果は、以下の通りです。

インデックスが必要でない場合、そのままfor a in Aのように参照した方が良いですね。

リストへの値追加

リストへの値を追加する処理の比較を行います。appendを使う方法、代入、内包表記の3種類です。

# append()
A = []
for i in range(N):
    A.append(i)

# A[i] = i, 代入
A = [None] * N
for i in range(N):
    A[i] = i

# [i for i in range(N)], 内包表記
A = [i for i in range(N)]

N = 10⁶ とし、連続する値をリストに追加したときの処理速度の比較結果です。

	平均(ms)	標準偏差(ms)
append()	103.99	2.62
A[i] = i	70.97	3.93
[i for i in range(N)]	65.83	3.20

これまで同様、Nを変化させたときの結果です。

そこまで大きな差はありませんが、要素数が予め分かっている場合は、代入や内包表記を使うと良いでしょう。

それぞれの処理速度

最後に、これまで比較を行ってきた8つの処理で、それぞれ最も速度が速いもののみを並べてみます。基本は N = 10⁶ となっています。（二次元配列の初期化は、N = 10³ * 2 = 10⁶）

二次元配列のソートがずば抜けて遅いので、除いてみます。（横軸が100ms刻みから20ms刻みになっています）

いかがでしょうか。個人的には、標準入力が意外と重い処理だなと思いました。

まとめ

標準入力、ソート、ループ、リストといった基本的な操作の処理速度を調べてみました。なかには10倍もの差が出る場合もあり、適切な選択をすることで処理速度を速くできそうです。

• 標準入力はinput()よりsys.stdin.readline()の方が10倍速い
• ソートは、sortedよりsortの方が1.4倍速く、keyの指定にはitemgetterを使うとlambdaに比べ1.2倍速くなる
• ループは、forの方がwhileより2倍程度速い
• 1秒で処理できる計算量は、シンプルな処理で N = 10⁷ まで
• リストの初期化は*演算子の方が、内包表記より8~9倍速い
• 二次元配列の初期化は、最初の次元のみ内包表記を使う
• リストの値の参照は、for a in Aのようにインデックスを作らないほうが、rangeを使う場合より4倍速い
• 要素の追加は内包表記を使うと、appendに比べ1.5倍速くなる

*1:Intel(R) Core(TM) i5-6267U CPU @ 2.90GHz

*2:標準入力はtimeitで計測できなかったので、個別に計測しています。