Performance Tip

このページはPythonプログラムの実行効率を改善するさまざまなTipsやトリックの紹介に特化しています。誰から得た情報であっても、その情報源を紹介するつもりです。

"fast python"ページをはじめて書いた1996年以降も、Pythonは著しく変化してきました。このことは、幾つかの規則も変化しているということを意味しています。そこで、他の誰かがこのページのメンテナンスを手伝ってくれるという期待をもって、ページをPython wikiに移動させました。

注意:これらのTipsはいつでも、読者のアプリケーションや、実際に使用するバージョンのPythonで盲目的に受け入れるだけでなく、実際に試してみることができます。

これらの新しく独自に書かれたパッケージ、例えば Pyrex 、 Psyco 、 Weave や PyInline のようなものは、実行効率を強く要求されるようなコードを、Cやマシン語へと容易に変換でき、アプリケーションの実行効率を劇的に向上させます。

ソート

Guido van Rossum より

Pythonの基本オブジェクトのソートは、とても効率が良い。リストのsortメソッドはオプションの比較関数を、ソートの振る舞いを変えるのに使われる引数として備えています。これはとても有用ですが、ソート処理を非常に遅くしています。

ソートの速度を向上させる代替案には、最初の要素をソートキーとしたタプルのリストを作成することがあります。これはデフォルトの比較を利用して厳密なソートを行ない、さらに2つ目の要素がオリジナルのリストの要素となります。これはいわゆる Schwartzian Transform 、DecorateSortUndecorate (DSU)として知られている手法です。

例をあげてみましょう。タプルのリストがあって、これをそれぞれのタプルのn番目のフィールドによってソートしたいとします。これは以下の関数で実現できます。

def sortby(somelist, n):
    nlist = [(x[n], x) for x in somelist]
    nlist.sort()
    return [val for (key, val) in nlist]

ここで話題となっている、リストのsortメソッド(代替ソート)による方法はすぐに分かるでしょう。

def sortby_inplace(somelist, n):
    somelist[:] = [(x[n], x) for x in somelist]
    somelist.sort()
    somelist[:] = [val for (key, val) in somelist]
    return

使用例は以下のようになります。

>>> somelist = [(1, 2, 'def'), (2, -4, 'ghi'), (3, 6, 'abc')]
>>> somelist.sort()
>>> somelist 
[(1, 2, 'def'), (2, -4, 'ghi'), (3, 6, 'abc')]
>>> nlist = sortby(somelist, 2)
>>> sortby_inplace(somelist, 2)
>>> nlist == somelist
True
>>> nlist = sortby(somelist, 1) 
>>> sortby_inplace(somelist, 1)
>>> nlist == somelist
True

Tim Delaney より

Python 2.3から、ソートは不変であることが保証されています。

(正確には、不変であるのはCPython 2.3からですが、不変であることを保証されているのはPython 2.4からです)

Python 2.4ではオプションのkeyパラメータが加わっており、それはより使いやすく変更されています。

import operator
sort(nlist, key=operator.itemgetter(n))

注意すべきなのは、オリジナルのitemはソートには利用されず、返されたkeyだけで、以下のようにするのと同等だということです。

nlist = [(x[n], i, x) for (i, x) in enumerate(nlist)]
nlist.sort()
nlist = [val for (key, index, val) in nlist]

文字列の連結

Pythonの文字列は不変です。この事実は駆け出しのPythonプログラマへ頻繁に忍び寄り、そのおしりにガブッと噛み付きます。この普遍性は長所と短所をもたらします。長所に関するコラムの中で、文字列は辞書のキーとして使われ、個別のコピーが複数の関数バインディングで共有されています(Pythonは1文字または2文字の文字列を自動的に共有します)。 短所に関するコラムでは、"与えられた文字列内のすべての'a'を'b'へ変更"、というようなことは難しいということを知るでしょう。その代わりに、必要なプロパティのために新たな文字列を作成しなくてはなりません。この継続的なコピーはPythonプログラムにかなりの非効率さをもたらすことができます。 -> ConcatenationTestCode へ

このようなコードは避けてください。

s = ""
for substring in list:
    s += substring

代わりに``s = "".join(list)``を使いましょう。前の例はとても一般的なものですが、大きな文字列を作成する場合には悲劇的な結果を招きます。同様に、細かな文字列を連続して生成する場合には、

s = ""
for x list:
    s += some_function(x)

の代わりに以下のコードを使ってください。

slist = [some_function(elt) for elt in somelist]
s = "".join(slist)

このようなコードは避け、

out = "<html>" + head + prologue + query + tail + "</html>"

以下のようなものを使いましょう。

out = "<html>%s%s%s%s</html>" % (head, prologue, query, tail)

さらに上を目指すなら、可読性のために(1プログラマにとって見れば、効率化には何の寄与もしませんが)、置換文字列に辞書を使いましょう。

out = "<html>%(head)s%(prologue)s%(query)s%(tail)s</html>" % locals()

この最後の2つの例は非常に速く動作するでしょう。特に幾つものCGIスクリプトが何度も実行されていて、さらに変更が簡単である場合には。また、遅い方の方法はPython 2.0で言語仕様に追加されたリッチな比較メソッドのため、さらに遅くなるでしょう。Pythonのバーチャルマシンは、どのように2つの文字列を連結するのかを判別するのにより多くの時間を必要とするようになっています(Pythonがすべてのメソッドのバインディングを実行時に行っていることを忘れないでください)。

ループ

Pyhonは2つのループ構文をサポートしています。 for 文が最も普通に使われます。 これはひと続きの構成要素を繰り返し、ループ変数にそれぞれを割り当てます。 ループ処理の内容が単純であれば、 インタープリタでの for ループによる オーバーヘッドは他のものへ代替可能です。例えば map 関数などが手軽です。 mapは for をCコードにするとみなすこともできるでしょう。 唯一の制限はmapを使うコードで、ループの実体は関数呼び出しでなくてはならない ことです。

単純なサンプルをあげてみます。単語のリストをループで操作し、各単語を大文字に 変換します。

newlist = []
for word in oldlist:
    newlist.append(word.upper())

map を使うことで、このループをインタープリタからコンパイル済みの Cのコードに押し込めることができます。

newlist = map(str.upper, oldlist)

リストの内包表記はPythonのバージョン2.0に追加されました。これにより上記の forループを、文法上さらに簡潔に記述できるようになります。

newlist = [s.upper() for s in oldlist]

ジェネレータ構文はPython2.4に追加されました。この関数はリストの内包表記や map のように見えますが、いったんリスト全体を生成するオーバーヘッドを 避けられます。代わりに、順々に繰り返しを行なうジェネレータオブジェクトを返します。

newlist = (s.upper() for s in oldlist)

どちらの手段がふさわしいかは、使用するPythonのバージョンや操作するデータの 特徴に依存します。

Guido van Rossumはさらに詳細な調査結果 loop optimization を書き残しています。(ただし)これは決定的に読み辛いです。

ドットを避ける

map やリストの内包表記が使えないとしたらどうでしょう。forループを 使い続けるのかもしれません。先ほどのforループの例は別の効率の悪さを持っています。 newlist.append と word.upper の2つは参照を行なう関数です。これは ループ処理が行なわれている間ずっと、そのつどごとに(関数が)評価されています。 元のループは次のように書き換えられるでしょう。

upper = str.upper
newlist = []
append = newlist.append
for word in list:
    append(upper(word))

ただし、このテクニックには使用上の注意点があります。ループが大きくなった時に メンテナンスが難しくなるという点です。このコードの詳細に精通するまで、 append や upper の定義をチェックしている自分に気づくでしょう。

ローカル変数

non- map バージョンのforループをスピードアップする最後のものは 可能な限りローカル変数を使うことです。上記のループが関数として キャストするのであれば、``append`` と upper はローカル変数になります。 Pythonのローカル変数へのアクセスはグローバル変数へのものよりも効率的です。

def func():
    upper = str.upper
    newlist = []
    append = newlist.append
    for word in words:
        append(upper(word))
    return newlist

最祖にこのコードを書いたときには、100MhzのPentium上でBSDIを動かしていました。/usr/share/dict/words にある単語のリスト(この時は38,470語ありました)を 大文字に変換すると、以下のような結果を得られました。

バージョン 時間(秒)

基本的なループ 3.47

ドットを取り除いたもの 2.45

ローカル変数&ドットなし 1.79

map関数をつかったもの 0.54

辞書の要素を初期化する

単語の頻出数の辞書を作成すると仮定してください、このときテキストはあらかじめ単語のリストに分解されています。実装はこんな風になるはずです。

wdict = {}
for word in words:
    if word not in wdict:
        wdict[word] = 0
    wdict[word] += 1

最初の時を除けば、それぞれの時に1つの単語は if 文のテストで偽となります。非常に沢山の単語を数える時、おそらく多くの処理が何度も繰り返されるでしょう。値の初期化が一回だけ繰り返され、その値の増加が何度も行なわれるような場合、tryステートメントを使うのが手軽でしょう。

wdict = {}
for word in words:
    try:
        wdict[word] += 1
    except KeyError:
        wdict[word] = 1

大切なのは例外KeyErrorを捕捉することで、デフォルトの except 節が存在しないため、try 節のステートメントで補足できない例外からも復帰しようとしてしまうのを避けられることです。

3つめの代替案はPython2.0のリリース後に使用できるようになりました。辞書が get() メソッドを持つようになりました。これは、辞書中に期待する値が見つからなかった場合にデフォルト値を返すでしょう。これにより、ループが簡潔になります。

wdict = {}
get = wdict.get
for word in words:
    wdict[word] = get(word, 0) + 1

もともとこの節を書いたとき、初めの2つのアプローチの一つがより早かったという明らかなシチュエーションがありました。この3つのアプローチすべてが、今では同様の実行効率を示すように見えます(それぞれ10%以内の違いです)、およそ単語のリストのプロパティは独立しています。

もちろん、辞書に入れられている値がオブジェクトや(変更可能な)リストなら、 dict.setdefault を使うこともできます。例は、

...
    wdict.setdefault(key, []).append(new_element)

これでキーを2度検索するのを避けられます。

import ステートメントのオーバーヘッド

import ステートメントはどこでも実行できます。閲覧性の低下ととも/ひきかえに初期の起動時間を短縮するため、それらを関数の中に置くのも有効です。Pythonのインタープリタは1つのモジュールを何度も読みこまないよう最適化されているにもかかわらず、importステートメントを繰り返し呼び出すのは実行効率に深刻な影響をおよぼします。

以下は2つのコード例です(元はGreg McFarlaneによる、comp.lang.pythonやpython-list@python.orgへの投稿に帰するものではなかったけれど、後日、別のソースによって、彼に帰属するものだということを知った)。

def doit1():
    import string             ###### import statement inside function
    string.lower('Python')

for num in range(100000):
    doit1()

あるいは、

import string             ###### import statement outside function
def doit2():
    string.lower('Python')

for num in range(100000):
    doit2()

doit2 は doit1 より早く動作します。たとえ doit2 がstringモジュールをグローバルに参照しているとしても。これがPython2.3と新しい timeit モジュールで使われるPythonインタプリタの動きです。これは2つ目が1つ目よりどれだけ早いかを示しています。

>>> def doit1():
...   import string
...   string.lower('Python')
... 
>>> import string
>>> def doit2():
...   string.lower('Python')
... 
>>> import timeit
>>> t = timeit.Timer(setup='from __main__ import doit1', stmt='doit1()')
>>> t.timeit()
11.479144930839539
>>> t = timeit.Timer(setup='from __main__ import doit2', stmt='doit2()')
>>> t.timeit()
4.6661689281463623

StringメソッドはPython 2.0の言語仕様で紹介されました。 これらは完全な import を避け、動作を軽くするバージョンを提供します。

def doit3():
    'Python'.lower()

for num in range(100000):
    doit3()

以下が``timeit``を使っての証明です。

>>> def doit3():
...   'Python'.lower()
... 
>>> t = timeit.Timer(setup='from __main__ import doit3', stmt='doit3()')
>>> t.timeit()
2.5606080293655396

上記の例はちょっと工夫されていますが、一般的な原理は守られています。

データの収集

Pythonにおける関数呼び出しのオーバーヘッドは、相対的には高く、特に組み込み関数の実効速度とは対照的です。この点は、関数がデータの収集を制御すべきなのか、どこで行なうのが適しているかを強く想起させます。以下がPythonで書かれた凡例です。

import time
x = 0
def doit1(i):
    global x
    x = x + i

list = range(100000)
t = time.time()
for i in list:
    doit1(i)

print "%.3f" % (time.time()-t)

これに対するは、

import time
x = 0
def doit2(list):
    global x
    for i in list:
        x = x + i

list = range(100000)
t = time.time()
doit2(list)
print "%.3f" % (time.time()-t)

以下が証明です。パディングの中が対話部分です。

>>> t = time.time()
>>> doit2(list)
>>> print "%.3f" % (time.time()-t)
0.204
>>> t = time.time()
>>> for i in list:
...     doit1(i)
... 
>>> print "%.3f" % (time.time()-t)
0.758

Pythonで書かれていても、2つ目の例は始めのものより4倍早く動作します。 doit がCで書かれていたなら、この違いはさらに大きくなるでしょう(Pythonの for ループを Cのループに交換するのは、ほとんどの関数呼び出しを取り除くのは同じようなものです)。

任意の動作の実効頻度を下げる

Pythonのインタープリタはある種の定期検査を行ないます。

明確に、この定期検査は別のスレッドが起動するかどうか、保留中の呼び出し(典型的なものとしてはシグナルハンドラによって定められた呼び出し)を起動するかどうかを決定します。

ほとんどの場合には何も行ないません、そのためこれらの検査をインタープリタの実行サイクルそれぞれの過程で行なうのは実行速度の低下を招きます。 sys モジュールに、 setcheckinterval という関数があります。この関数により、インタープリタにどんな頻度で定期検査を行なうのかを指定できます。Python 2.3以前のリリースで、頻度の既定値は10でした。2.3で、この値は100に引き上げられています。スレッドをまったく使用しておらず、さまざまなシグナルを受け取らなくても良いのであれば、この頻度を大きな値に設定することによって、多くの場合、インタープリタの実行効率を改善できます。

PythonはCじゃない

もちろんPerlやJava、C++でもHaskellでもありません。他の言語の挙動に関する知識をPythonに当てはめるには注意が必要です。デモンストレーションのため、シンプルな例をご提供しましょう。

% timeit.py -s 'x = 47' 'x * 2'
1000000 loops, best of 3: 0.574 usec per loop
% timeit.py -s 'x = 47' 'x << 1'
1000000 loops, best of 3: 0.524 usec per loop
% timeit.py -s 'x = 47' 'x + x'
1000000 loops, best of 3: 0.382 usec per loop

このCのプログラムと同じものと見なされます(加算のバージョンのみ示します)。

#include <stdio.h>

int main (int argc, char **argv) {
    int i = 47;
    int loop;
    for (loop=0; loop<500000000; loop++)
        i + i;
}

そして実行時間はこの通り。

% for prog in mult add shift ; do
< for i in 1 2 3 ; do
<   echo -n "$prog: "
<   /usr/bin/time ./$prog
< done
< echo
< done
mult:         6.12 real         5.64 user         0.01 sys
mult:         6.08 real         5.50 user         0.04 sys
mult:         6.10 real         5.45 user         0.03 sys

add:          6.07 real         5.54 user         0.00 sys
add:          6.08 real         5.60 user         0.00 sys
add:          6.07 real         5.58 user         0.01 sys

shift:        6.09 real         5.55 user         0.01 sys
shift:        6.10 real         5.62 user         0.01 sys
shift:        6.06 real         5.50 user         0.01 sys

注意すべきなのは、2倍したり、左に1ビットシフトしたりするコードを何度も書く代わりに、計算式そのものを(スクリプトに)追加する、Python版の長所は意義深いということです。

Cにおける現代的なコンピュータアーキテクチャの全てで、3つの算術演算子それぞれは、1サイクルのうちに実行される、ひとつの機械語の命令に翻訳されます。そのため、どれを選ぶかはほとんど重要ではないのです。

ありふれた"テスト"として、新人のPythonプログラマがしばしば行なう行動は、次のようなPerlの慣用句を

while (<>) {
    print;
}

Pythonのコードへとこんな風に翻訳します。

import fileinput

for line in fileinput.input():
    print line,

そしてこれを使ってみて、PythonはPerlより遅いに違いないと考えます。その他の人々が何度も指摘するように、Pythonはいくつかの点でPerlより遅く、それ以外の点で早く動作します。 関連する実行効率は、多くの場合この2つの言語に関する経験に依拠します。

Python 2.2からは、Perlの慣用句を同じように短いPythonのコードで置き換えられるようになりました。

import sys

for line in sys.stdin:
    print line,

コードをプロファイルする

あなたのプログラムを高速化する第一歩は、ボトルネックがどこに潜んでいるのかを知ることです。まだ実行されたことがない、あるいは既に高速に動作しているコードをきちんと最適化するのは厄介です。私はコードのホットスポットを特定したり、プロファイル、追跡する助けとして、2つのモジュールを使っています。この後の例で、私は timeit 、Python 2.3で追加されたモジュールを使っています。

Profileモジュール

profile module は、標準モジュールとして配布されているPythonに含まれています。このモジュールを使うことで、関数の集まりがどう動くかプロファイルするのが随分楽になります。メインの関数 main があるとします。引数は取らずに、この関数をprofileモジュールの管理下で実行したい場合には、以下の単純極まりない書式を使います。

import profile
profile.run('main()')

main() 関数から復帰すると、profileモジュールは関数呼び出しとその実行時間の表を表示します。この出力はモジュールに含まれているStatsクラスを使っていじって見ることができます。Python 2.4ではprofileモジュールはPythonの組み込み関数や拡張モジュールによって消費された時間も含めてうまくプロファイルできるようになるはずです。

Hotshotモジュール

Python 2.2の新機能、 hotshot package はprofiileモジュールの代替物として意図されたものです。モジュールの基盤はCで書かれており、そのためhotshotモジュールを利用することでより実行効率への影響が少なく、それ故にアプリケーションの挙動についてより正確な理解をもたらすでしょう。``hotshotmain.py`` プログラムも配布物の Tools/scripts ディレクトリにあり、これはコマンドラインから(あなたの)プログラムを簡単に hotshot モジュールの管理下に置けるようにします。

Traceモジュール

trace module はprofileモジュールからスピンオフしたモジュールで、もともとは筆者が粗削りなステートメントレベルのテスト範囲で動くよう書いたものです。私が最初の荒っぽいコードをリリースして後、沢山の人々により徹底的に改変されてきました。Python 2.0では、配布物のディレクトリ下Tools/scriptsにtrace.pyを見つけることができます。Python 2.3からは標準モジュール(Libディレクトリ)に含まれています。これをローカルのbinディレクトリにコピーして実行フラグを与えることもでき、直接実行できるようになります。

traceスクリプトをコマンドラインから実行するのは簡単です。

% trace.py -t spam.py eggs

他に用意されたドキュメントはありませんが、"pydoc trace"を実行することでコード内のドキュメントを読むことができます

Comments