BETA

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

投稿日:2018-10-14
最終更新:2018-10-24
※この記事は外部サイト(https://www.kumilog.net/entry/python-speed...)からのクロス投稿です

はじめに

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

目次にあるように、標準入力、ソート、ループ、リストについて、計8個の処理の速度比較を行いました。処理速度の計測方法は、Mac Book Pro((Intel(R) Core(TM) i5-6267U CPU @ 2.90GHz))を使い、timeitでそれぞれ100回計測((標準入力はtimeitで計測できなかったので、個別に計測しています。))し、平均と標準偏差を求めています。

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

計測に用いたコードはこちらにあります。

また、グラフ描画には、xkcdスタイルを使用しています。xkcdスタイルについてはこちらの記事もどうぞ。

標準入力

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 としたときの結果です。

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

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

上記のように

import sys
input = sys.stdin.readline

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

ソート

sort と sorted

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

# sort()
A.sort()
# sorted()
A = sorted(A)

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

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

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

ソートの key

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

先程と同じ要領で、事前にランダムな整数値が格納されている二次元リストA(次元は10^6 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|

いずれも一次元のソートに比べ、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 = 10^6 としたときの結果は以下になります。

function 平均(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^6 だけでなく N = 10^5, 10^7についても調べてみました。

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

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

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

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

10^6 余裕を持って間に合う

10^7 おそらく間に合う

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

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

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

N C++ Python
10^5 |余裕を持って間に合う
10^6 余裕を持って間に合う おそらく間に合う
10^7 おそらく間に合う 非常にシンプルな処理でない限り厳しい
10^8 非常にシンプルな処理でない限り厳しい

リスト

リストの初期化

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

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

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

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

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

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

二次元配列の場合

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

function 平均(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^6 とし、連続する値をリストに追加したときの処理速度の比較結果です。

function 平均(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^6 となっています。(二次元配列の初期化は、N = 10^3 * 2 = 10^6)

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

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

まとめ

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

  • 標準入力はinput()よりsys.stdin.readline()の方が10倍速い
  • ソートは、sortedよりsortの方が1.4倍速く、keyの指定にはitemgetterを使うとlambdaに比べ1.2倍速くなる
  • ループは、forの方がwhileより2倍程度速い
  • 1秒で処理できる計算量は、シンプルな処理で N = 10^7 まで
  • リストの初期化は*演算子の方が、内包表記より8~9倍速い
  • 二次元配列の初期化は、最初の次元のみ内包表記を使う
  • リストの値の参照は、for a in Aのようにインデックスを作らないほうが、rangeを使う場合より4倍速い
  • 要素の追加は内包表記を使うと、appendに比べ1.5倍速くなる
技術ブログをはじめよう Qrunch(クランチ)は、プログラマの技術アプトプットに特化したブログサービスです
駆け出しエンジニアからエキスパートまで全ての方々のアウトプットを歓迎しております!
or 外部アカウントで 登録 / ログイン する
クランチについてもっと詳しく

この記事が掲載されているブログ

@xkumiyuの技術ブログ

よく一緒に読まれる記事

0件のコメント

ブログ開設 or ログイン してコメントを送ってみよう
目次をみる
技術ブログをはじめよう Qrunch(クランチ)は、プログラマの技術アプトプットに特化したブログサービスです
or 外部アカウントではじめる
10秒で技術ブログが作れます!