pythonの速度で気にするところ(高速化メモ)

python

高速化に関して

  • 高速化はほんとに色々と罠が多い。意図した計測できていなかったり。(特に、python3はmapとかの返り値がジェネレータになっているので、その計測を間違っている例とかがウェブには多い。)
  • 高速化の前に計測が必須だが，計測に関しては別のまとめを参照。

リストは連結リストではなく配列

  • Pythonのリストはいわゆる連結リストではなく可変長配列(たぶん)。arrayというのがあるけどそっちは固定長配列。
  • よって、リストの先頭要素の挿入/削除(insert/pop)とかはしない。
  • また，順次appendしていくと容量オーバーのときに領域の拡張が発生し，コピーが発生し得る。それを避けるためには，サイズがわかっているなら，[None]*n_sizeなどで予め領域を確保しておく。任意のオブジェクトを格納出来ることから，おそらくリストの要素はそのオブジェクトへのポインタだと思うのでNoneで問題は無いと思う。

文字列の連結と代入(文字列に+は使わない)

  • これはPythonに限らず，よく見る観点。文字列はイミュータブルなので，毎回生成され得るという問題。
  • 文字列はイミュータブルなので，新しい文字列が生まれると新しくオブジェクトを割り当ててしまう。
  • もし，複数の文字列を連結したいような場合にはjoinを使えばそれを避けることができる。
# Bad
s = 'hoge'
s +=  'hoge'  # new memory allocation
s +=  'hoge'  # new memory allocation

# Good
t = ['hoge', 'hoge', 'hoge']
s = ''.join(t)
  • また，formatや'%'を使う方が速い
# Bad
msg = 'Error:' + error_no + 'is occured.'

# Faster
msg = 'Error: %s is occured.' % error_no

# Better
msg = 'Error: {} is occured.'.format(error_no)

whileよりfor

  • 倍くらい違う(らしい)forの方がiのインクリメントと条件比較が最適化されているのかな(Byteコードを見て)？
# Bad
i=0
sum=0
while(i<N):
    sumation += i
    i+=1
# Good
for i in range(N):
    sum+=i

リスト内包表記

  • pythonの(というよりインタプリタ言語の)for文はfor内部を逐次呼び出すので遅い(らしい)。確かに、言われてみればインタプリタだと最適化出来ないんだ。(JITだと遅くないのかも？)。
  • 下記の例だと毎回appendを参照するコストがかかる。この場合は内包表記でやる。
# Bad
x = []
for i in range(10):
    x.append(x)
# Good
x = [x for x in range(10)]
  • ここで覚えておくことは，'.'はメソッド呼び出しだが，その際にメソッドの検索が入ることと，そのコストが馬鹿にならないこと。よって，array.appendを予めmy_appendみたいにして変数に渡しておけば，その検索コストが不要になる。
# Bad
for d in dataset:
    arr.append(d*d)  # appendを毎回検索する。

# Good
my_append = arr.append
for d in dataset:
    my_append(d*d)   # appendを(間接的に)直接呼び出す。

for回すくらいならsetに変換

  • setとして扱えばfor回さなくても良い場合もある。こっちのほうが速い(らしい)
# Bad
for x in a:
  for y in b:
    if x == y:
      yield(x,y)
# Good
set(a)&set(b)

mainの中に書く(=グローバル変数を使わない)

  • スクリプトを書くときに，ファイルにフラットに(グローバル領域に)書く例が多い。例えば，if name == 'main':の中に書くみたいな。でも，Pythonではグローバル変数はアクセスが遅いので，この書き方は遅い。
  • それを避けるためには，main()関数などを定義して，ローカル変数化する。
# Bad
x = 0  # グローバル領域に書く。
y = x ** 2

# Good
def main():
  x = 0        # ローカル変数になる。
  y = x**2

main()  # 呼び出し。

Swap

  • 一時変数などは使わずに多値代入を使う。
# Good
x, y = y, x

# Bad
temp = x
x = y
y = temp

要素であるかの確認は配列じゃなくset

  • set(dictも)はハッシュで実装されている。よって，メンバであるか否かの判定がO(1)で済む。
# Good
dataset = set(['a', 'b', 'c'])
'c' in dataset

# bad
dataset = ['a', 'b', 'c']
'c' in dataset

文字列のマッチングに不必要に正規表現を使わない

  • pythonのStringはfindメソッド, inメソッドを持っている。find/inで十分なマッチングを正規表現でやると(当然)めっちゃ遅い。

不要なインポートは避ける

  • たまに関数の中でimportしていたりするけど、そのたびにimportされてしまうので注意。

その他のToBeWritten

  • Cython, JIT(NUMBA), multiprocessing, Scoop(分散)