kumilog.net

データ分析やプログラミングの話などを書いています。

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)]

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

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

f:id:xkumiyu:20180818183736p:plain

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

上記のように

import sys
input = sys.stdin.readline

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

ソート

sort と sorted

ソートには、リストのメソッドであるsort()と組み込み関数のsorted()があります。前者はリストそのものを変更する破壊的メソッドです。事前に、要素数が 106 で、ランダムな整数値が格納されているリスト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(次元は106 x 2)を用意しておき、以下のようにソートを実行したときの処理速度を計測します。keyの指定方法がlambdaitemgetterの2種類あり、ソートの方法がsortsortedの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の方が速いです。

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

ループ

for と while

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

# 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 = 106 としたときの結果は以下になります。

平均(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 = 106 だけでなく N = 105, 107についても調べてみました。

f:id:xkumiyu:20180819085801p:plain

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

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

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

106 余裕を持って間に合う

107 おそらく間に合う

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

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

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

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

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

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

リスト

リストの初期化

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

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

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

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

f:id:xkumiyu:20180819085829p:plain

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

f:id:xkumiyu:20180819085834p:plain

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

二次元配列の場合

二次元配列の初期化は、内包表記を使わなければなりませんが、すべての次元で内包表記を使うのではなく、最初の次元のみ内包表記を使う方が速くなります。N = 103で実験した結果、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

f:id:xkumiyu:20180819185119p:plain

リストの値参照

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の要素数が 106 のときの結果は、以下の通りです。

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

f:id:xkumiyu:20180819085848p:plain

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

f:id:xkumiyu:20180819085856p:plain

インデックスが必要でない場合、そのまま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 = 106 とし、連続する値をリストに追加したときの処理速度の比較結果です。

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

f:id:xkumiyu:20180819085911p:plain

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

f:id:xkumiyu:20180819085916p:plain

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

それぞれの処理速度

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

f:id:xkumiyu:20180819195443p:plain

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

f:id:xkumiyu:20180819195447p:plain

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

まとめ

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

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

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

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

*3:https://stackoverflow.com/questions/869229/why-is-looping-over-range-in-python-faster-than-using-a-while-loop