あなたのPythonを爆速にする７つの方法

最近プロコン（プログラミング・コンテスト）をはじめました。
基本的にはアルゴリズム勝負なのですが、とにかく速度を競うプロコンです。
小手先の速度チューニングもバカにできません。

何が速くて何が遅いのかはっきりさせるため、ボトルネックになりそうな操作のベンチマークを取りました。

実行環境は下記のとおりです。

python2.7.5
OS: MacOSX 11
CPU: Core i7 2GHz (4core)
MEM: 16GB

その1. 配列の初期化を高速化する

まずはプロコンの基本中の基本、配列の初期化です。
下記７つの初期化方法を比較してみます。

空配列へappendして配列をつくる
for内包表記で配列をつくる
サイズ1(None)の配列を乗算してから値を代入する
サイズ1(None)の配列を乗算する
サイズ1(ゼロ)の配列を乗算する
すべてゼロのarrayをつくる
0〜nのarrayをつくる

サイズ1,000,000の配列を作成します。

start = time.clock()

"""
1. list append
1000000	0.156414
"""
xs = []
for i in xrange(n):
  xs.append(i)

"""
2. for
1000000	0.0876
"""
xs = [i for i in xrange(n)]

"""
3. [None]
1000000	0.099896
"""
xs = [None] * n
for i in xrange(n):
  xs[i]

"""
4. [None] only
1000000	0.005255
"""
xs = [None] * n

"""
5. [0]
1000000	0.005359
"""
xs = [0] * n

"""
6. array
1000000	0.108973
"""
xs = array('I', [ 0 for _ in xrange(n) ])

"""
7. array
1000000	0.149061
"""
xs = array('I', [ i for i in xrange(n) ])

end = time.clock()
print end - start

#	操作	time(sec)
1	空配列へappend	0.156414
2	for内包表記	0.0876
3	None配列を乗算＆代入	0.099896
4	None配列を乗算	0.005255
5	0配列を乗算	0.005359
6	すべてゼロのarrayをつくる	0.108973
7	0〜nのarrayをつくる	0.149061

※サイズはすべて1,000,000

とにかく配列の乗算([None]*nのやつ)が鬼速です。
for内包表記の方が速いと思っていたので意外でした。
固定長の配列をつくるときは[None]*nが(￣ー￣)ｂｸﾞｯ!

その2. 配列を高速にランダム・リードする

シーケンシャルにではなく、ランダムに配列から値を読み取る場合にどの構造体が速いか比較してみます。

list型
Integerのarray型
Byteのarray型

サイズ1,000,000の配列を作成し、読み取りを行います。

r = Random()
ix = [i for i in xrange(n)]
r.shuffle(ix)

nay = [i for i in xrange(n)]
iay = array('I', [ i for i in xrange(n) ])
bay = array('b', [ 1 for _ in xrange(n) ])

start = time.clock()

"""
1. list
10000000	0.367742
"""
tmp = 0
for i in ix:
  tmp = nay[i]

"""
2. array
10000000	0.263049
"""
tmp = 0
for i in ix:
  tmp = iay[i]

"""
3. 1byte array
10000000	0.232178
"""
tmp = 0
for i in ix:
  tmp = bay[i]

end = time.clock()
print end - start

#	操作	time(sec)
1	list型	0.367742
2	Integerのarray型	0.263049
3	Byteのarray型	0.232178

※サイズはすべて1,000,000

ランダム・リードではByte型のarrayが最速です。

その3. pop – うしろから削除 – 削除するならこれ！

配列の要素を削除します。
まずは計算量の少ない後ろから削除です。

list型
Integer型のarray

サイズ1,000,000の配列を作成し、popします。

nay = [i for i in xrange(n)]
iay = array('I', [i for i in xrange(n)])

start = time.clock()

"""
1. list
10000000	0.205749
"""
for i in xrange(n):
  nay.pop()

"""
2. array
10000000	0.302395
"""
for i in xrange(n):
  iay.pop()

end = time.clock()
print end - start

#	操作	time(sec)
1	list型	0.205749
2	array型	0.302395

※サイズはすべて1,000,000

後ろから削除はarrayよりlistの方が速いです。
どちらにしても1,000,000回の試行でこのくらいの処理速度ならまあ許容範囲でしょうか。

その4. pop – 先頭から削除 – やらない方がよい ※追記あり

配列の要素を先頭から削除します。
3.の後ろから削除に比べると計算量が激増します。

list型
Integer型のarray

サイズ1,000,000の配列を作成し、popします。

nay = [i for i in xrange(n)]
iay = array('I', [i for i in xrange(n)])

start = time.clock()

"""
1. list
10000000	182.47865
"""
for i in xrange(n):
  nay.pop(0)

"""
2. array
10000000	85.623589
"""
for i in xrange(n):
  iay.pop(0)

end = time.clock()
print end - start

#	操作	time(sec)
1	list型	182.47865
2	array型	85.623589

※サイズはすべて1,000,000

こちらはarrayの方が若干速いですが・・・速い方のarrayで1分以上かかっているので、先頭から削除はやったら即死の禁じ手です。
同じpopでも後ろから削除する場合と全然違います。

2015-05-25 追記:
続・あなたのPythonを爆速にする７つの方法に書かせて頂いたのですが、先頭から削除したい場合はdequeを使うと良いです。

その5. insert – 先頭に挿入 – 遅い代表 ※追記あり

popの次はinsert、先頭に挿入です。
これも先頭から削除と同様コストのかかる処理です。

list型
Integer型のarray

サイズ1,000,000の配列を作成し、insertします。

nay = []
iay = array('I', [])

start = time.clock()

"""
list
1000000	241.515497
"""
for i in xrange(n):
  nay.insert(0, i)

"""
array
1000000	86.058389
"""
for i in xrange(n):
  iay.insert(0, i)

end = time.clock()
print end - start

#	操作	time(sec)
1	list型	241.515497
2	array型	86.058389

※サイズはすべて1,000,000

popと同様arrayの方が若干速いですが、先頭挿入の繰り返しは極力避けたほうがよいです。
appendするか、最初に挿入すべきサイズを確保した配列を作成した方が速いです。

2015-05-25 追記:
popと同様続・あなたのPythonを爆速にする７つの方法に書かせて頂いたのですが、先頭挿入したい場合はdequeを使うと良いです。

その6. 文字列検索を高速化する

文字列検索もいくつかやり方があります。
下記の４つを比較しました。

findメソッド
in
reモジュール
事前コンパイルしたreモジュール

長さ1,000,000の文字列を作成し、検索します。

search = '_SEARCH_'

ix = [ i for i in xrange(n) ]
r = Random()
r.shuffle(ix)
sp = int(n * 4 / 5)

chs = list(string.ascii_letters)
t = ''
for i in ix[0:sp]:
  m = i % 52
  t += chs[m]

t += search
for i in ix[sp:]:
  m = i % 52
  t += chs[m]

start = time.clock()

"""
1. find
1000000	322.414854
"""
for i in xrange(n):
  idx = t.find(search)

"""
2. in
1000000	314.847081
"""
for i in xrange(n):
  idx = search in t

"""
3. re
1000000	674.792997
"""
for i in xrange(n):
  m = re.search(search, t)
  idx = m.start()

"""
4. re 事前にコンパイル
1000000	674.394229
"""
p = re.compile(search)
for i in xrange(n):
  m = p.search(t)
  idx = m.start()

end = time.clock()
print end - start

#	操作	time(sec)
1	find	322.414854
2	in	314.847081
3	re	674.792997
4	re 事前にコンパイル	674.394229

1,000,008byteの文字列から_SEARCH_という文字列を検索しています

正規表現モジュールreを使うより、in(またはfind)を使った方が圧倒的に速いです。
このあたりは多言語と同じですね。
正規表現を使わなくて実現できる検索であればinを使った方が高速です。

その7. 標準入力＆標準出力

これは完全にプロコン向けなのですが。
標準入力を受け取りながら、計算し、出力したほうが速いのか
標準入力をすべて受け取ってしまってから計算＆出力したほうが速いのかを検証しました。

raw_input で標準入力を受け取りながら出力
raw_input で標準入力を受け取りながら結果をバッファリング
raw_input で標準入力をすべて受け取ってから出力
raw_input で標準入力をすべて受け取りバッファリングした結果を出力

1,000,000個の標準入力を受け取り、1,000,000の出力を行います。

start = time.clock()
"""
1. raw_input で 標準入力を受け取りながら出力
1000000	3.504401
"""
for i in xrange(n):
  x = int(raw_input()) / 10
  print x

"""
2. 結果をバッファリング
1000000	3.268692
"""
res = []
for i in xrange(n):
  res.append( int(raw_input()) / 10 )
for i in res:
  print i

"""
3. raw_input で 標準入力をすべて受け取ってから出力
1000000	3.22516
"""
xs = [ int(raw_input()) for _ in xrange(n) ]
for i in xs:
  x = i / 10
  print x

"""
4. raw_input で 標準入力をすべて受け取りバッファリングした結果を出力
1000000	3.125762
"""
xs = [ int(raw_input()) / 10 for _ in xrange(n) ]
for i in xs:
  print i

end = time.clock()
print end - start

#	操作	time(sec)
1	標準入力を受け取りながら出力	3.504401
2	標準入力を受け取りながら結果をバッファリング	3.268692
3	標準入力をすべて受け取ってから出力	3.22516
4	標準入力をすべて受け取りバッファリングした結果を出力	3.125762

※1,000,000件の標準入力を受け取り1,000,000件の出力を行っています

標準入力をすべて受け取ってから計算を行ったほうが速いです。
体感的にはもっと速かったんだけどな(・・;)

まとめ

配列作成は[None]*nが高速
ランダム・リードはarrayが強い
配列の先頭削除は激遅※
配列の先頭挿入も激遅※
正規表現reは遅い
文字列検索はinが速い
標準入力は一旦バッファしてから処理すると良い

※配列の先頭削除、先頭挿入はdequeを使いましょう。
レッツ・プロコンv(￣Д￣)v ｲｴｲ

ここに掲載したソースコードは下記にあります。
~~https://github.com/x1-/codeforces/blob/0.0.1/time/bench.py~~

2015-05-14 追記:
@mathhunさんにプルリクエストを頂き、Benchmarkerを利用したコードに変更しました。

https://github.com/x1-/codeforces/blob/master/time/