Python Speed

多くの人々が頻繁にPythonプログラムの実行速度を心配しています。でもPythonを使わないと、堪らないくらいパフォーマンスのロスがありますよね? 中には「なんだ、インタプリタのスクリプト言語か、まるっきり遅いや」なんて結論づける人もいます。その一方で、Pythonを実際に試してみて、十分な実行効率をもっていることに気づいた人もいます。もちろん、時にはとっても遅いプログラムができあがることもあります。

なぜ素のスピードが重要か? あるいは重要でないか?

多くの人が必要以上に速度に取りつかれていて、この種の問題ではCが優れた実績を示していることから、(Cが)全ての面で優れた言語であると考えています。他の人々は「開発の速度」がより重要で、Pythonを選ぶのはそのような時に限り、まあそれなりの速度だろうと考えています。そして頻繁に、Pythonのコードが期待以上の速度で動いていることに彼らは驚かされています。場合によっては、開発に同じ時間を費やしたC/C++のコードより速いことさえあります。 一般的に重要とされてるのは絶対的な速度ではありません。これは実行可能ファイルへのアクセス速度について考えてみば分かると思います。このアクセス速度をもたらしている機構を超えた最適化は、リソース(普通はあなたの時間、つまりお金)の無駄でしょう。

速度と拡張性を改善するテクニック

ここに示すのは、アプリケーションに最も良い実行効率をもたらすコーディングのガイドラインです。

最良のアルゴリズムと最速のツールを使う

  • setsや辞書を使った要素の検証(O(1))は、配列の検索(O(n))よりも高速です。 a in b を調べるとき、bはリストやタプルではなくsetsや辞書であるべきです。
  • 文字列連結は ''.join(seq) を使うのがベストです。この計算量はO(n)です。対照的に、演算子'+' や '+='を使った計算量はO(n**2)となります。演算の途中で新たな文字列が生成されるためです。CPython 2.4のインタプリタはこの制限をいくらか緩和していすまが、 ''.join(seq) が最善策であることに変わりありません。
  • 多くのツール(rangeやxrange、mapやitertools.imap、リスト内包表記とジェネレータ、dict.itemsとdict.iteritems)でリストとイテレータの両方が提供されています。一般的に、イテレータはより省メモリでスケーラビリティに優れています。これらは、リストそのものが必要とされない場合によく使われています。
  • (CPythonの)コアとなる構成要素のいくつかは、最適化されたCのコードで書かれています。このアドバンテージを利用するアプリケーションは、実質的な実行効率の向上を得ることができます。この組み込みの構成要素にはすべての組み込み型(リスト、タプル、sets、辞書)と、array、itertools、collection.dequeのような拡張モジュールを含みます。
  • 同様に、組み込み関数は手で書かれたコードより速く動作します。例えばmap(operator.add, v1, v2)はmap(lambda x,y: x+y, v1, v2)より速いです。
  • リストは固定長の配列と可変長のスタックより速く動作します。しかし、pop(0)またはinsert(0,v)、collection.deque()を使うアプリケーションはO(1)という高い効率を発揮します。これはそれぞれの追加、削除するごとO(n)回におよぶ、リストの再構築を避けられるからです。
  • カスタムの順序ソートでは、Python2.4のkey=オプションあるいは伝統的なdecorate-sort-undecorateテクニックを使うと、もっとも良い効率が得られます。両者のアプローチとも、要素ごとに1度だけkey関数を呼びます。対照的にソートのcmp=オプションは、ソートを行う間に要素ごと何度も呼ばれます。例えば、sort(key=str.lower)はsort(cmp=lambda a,b: cmp(a.lower(), b.lower())) より速いのです。

TimeComplexityも参照。

インタープリタの最適化による長所を活かす

  • 関数の中で、ローカル変数へのアクセスはグローバル変数、組込み定数、属性の参照より高速です。そのため、内部ループの中ではローカル変数へのアクセスに局所化すると良い場合があります。例えば、random.shuffle()というコードを random=self.random という1文で局所化します。これによってshuffleのループがself.ramdomを何度も参照するのを防ぎます。ループの外側での向上率は非常に小さいため、その対価を得ることはめったにありません。
  • 前の方法は、定数を表す式をループの外側に置くという規則を一般化します。同様に、組み合わせによる定数をあらかじめ計算しておくこと大切です。ループの中では"x=1+2"と書く代わりに"x=3"としましょう。
  • 関数呼び出しのオーバーヘッドはその他の命令に比べて大きくなります。そのため、実行速度必要なループ内でのインライン構文には価値があることがあります。
  • リストの内包表記は(計算結果を捨ててしまうのでなければ)同様のforループに比べて僅かに早く動作します。
  • Py2.3以降を使えば、コンパイラが"while 1"を単一のジャンプに最適化します。対照的に"while True"にはもう何ステップか必要とします。後者が明快に動作するのであれば、速度の必要なコードにはひとつめの形式を用いると良いでしょう。
  • 複数の代入は単一の代入より遅くなります。つまり "x,y=a,b" は "x=a; y=b"より遅くなります。一方で、複数ターゲットへの代入は変数の交換より早く動作します。つまり "x,y=y,x" は"t=x; x=y; y=t" より早く動作します。
  • 連続した比較文は "and" 演算子より早く動作します。"x < y and y < z"と書く代わりに"x < y < z"としましょう。
  • 連続する比較式はand演算子より高速です。"x < y and y < z"と書く代わりに"x < y < z"と書きましょう。
  • さらに幾つかのアプローチがハックとされ、要求の多いアプリケーションのためにのみ残されています。例を挙げると not not x は bool(x) とするより速く動作します。

診断ツールの長所を活かす

  • hotshotとprofileモジュールは実行効率上のボトルネックを特定するのに役立ちます。profileはピュアPythonコードとCコードそれぞれが費やす時間を区別できます。
  • timeitモジュールはコード内の独立した1行とその代替手段との実行効率の比較を、迅速に行なう機能を提供します。

実行効率が全体の方針を決定できる

  • XMLの処理においてSAXは一般的にDOMを使うより速く、メモリ効率も良くなります。
  • 繰り返し使われるものには、Cバージョンのモジュールを使いましょう。e.g. pickleの代わりにcPickleモジュール、StringIOの代わりにcStringIOを。重要な注意点は、Cバージョンのモジュールは柔軟性が低いという点です。そのため何か見逃していないかモジュールのドキュメントを確かめましょう。
  • スレッドの利用はI/Oの待機によって時間を浪費するようなアプリケーションの応答時間を改善できるでしょう。
  • selectモジュールは複数のソケットをプーリングすることによるオーバーへッドを最小化する助けとなるでしょう。

実行効率を高める標準外のツールを検討する

  • Numpy はとても豊富な数値計算に必須のツールです。
  • Psycoとpyrexはネイティブコードの速度に迫る助けになるでしょう。しかし、その制限事項にも留意しておきましょう。これらのいずれもPythonの構成要素すべてをサポートしている訳ではありません。
  • 異なったツールとの実行結果をともなった比較に興味があるなら、SciPy関連のドキュメント A beginners guide to using Python for performance computing を参照してください。

A beginners guide to using Python for performance computing : http://scipy.org/PerformancePython

さらなる実行効率のTips

さらなる実行効率に関するTipsと例をPythonSpeed/PerformanceTips で見つけられます。


翻訳について

この文書は http://www.python.org/cgi-bin/moinmoin/PythonSpeed で公開されているPythonの実行効率に関するエッセイ“PythonSpeed”の翻訳です。元々はIrmen De Jong氏が自身のmoinmoinで公開した文章でしたが、Daily Python URLで紹介されて評判になったのか、その後Python.orgのWikiに転載されています。

追記(2005-05-21)

PyCon2005の終了後にPython.orgのWiki全体に大きく手が入れられ、それに伴いこの文書も改訂されました。翻訳の方もようやく改訂に追従できましたが、訳には怪しい場所もあると思いますので、お気づきの点はご連絡いただけるとうれしいです。 -- turky

さらに追記(2006-09-25)

元々、このページは編集不可にしていたのだけれど、このところSPAMコメントが多いので、WikiからReSTのページに移動することにしました--turky

さらにさらに追記(2007-09-20)

誤訳の指摘に今さら気づいたため、訳文を少しだけ修正しました。西尾さん、ありがとうございます。

Comments