Pythonの生みの親Guido van Rossum氏が残した高速化Tips #Python

概要

大量のデータを処理するようなプロジェクトなどにおいて、プログラムの高速化は重要です。しかしPythonはC++などの言語と比較して遅いことが知られています。

この問題について、Pythonの生みの親、Guido van Rossum氏が残した記事がありました。この記事を参考に高速化に関するTipsをまとめました。

Python Patterns - An Optimization Anecdote

ベンチマーク

今回のタスクは「0~255の数字をASCIIとして文字列に変換し、全ての文字を結合する」という処理です。

つまり入力は0~255の数字のイテレータ[0, 1, 2, ..., 255]で、出力は次のようになります。

¡¢£¤¥¦§¨
©ª«¬®¯°±²³´µ¶·¸¹º»¼½¾¿ÀÁÂÃÄÅÆÇÈÉÊËÌÍÎÏÐÑÒÓÔÕÖ×ØÙÚÛÜÝÞßàáâãäåæçèéêëìíîïðñòóôõö÷øùúûüýþÿ
f6
123456789:;<=>?@ABCDEFGHIJKLMNOPQRSTUVWXYZ[\]^_`abcdefghijklmnopqrstuvwxyz{|}~

ベンチマークとして次の関数f1を作ります。

def f1(list):
    string = ""
    for item in list:
        string = string + chr(item)
    return string

この関数f1を高速にする方法を探しながら、高速化に関するTipsをまとめていきます。

ローカル変数を用いる

Pythonのインタープリタは変数の定義をローカル変数から探しはじめ、もしなければグローバル変数、ビルトイン変数と探していきます。そのため同じオブジェクトを参照するのであればローカル変数に定義しておく方が高速です。

以下の関数f4はf1と殆ど同じですが、chr関数がローカル変数lchrとして再定義されています。これにより大幅に処理時間が短縮できました。

def f4(list):
        string = ""
        lchr = chr  # この行が追加されている
        for item in list:
            string = string + lchr(item)
        return string

速度

原文: f4の処理時間 = f1の処理時間 * 0.6
私の手元(3系): f4の処理時間 = f1の処理時間 * 0.8

ビルトイン関数を用いる & ループ内では関数を使わない

ビルトイン関数はC言語で実装されており、高速で動きます。以下の関数f3ではmapというビルトイン関数を使っています。そのためf3はf1より高速で動きます。

それだけでなく、f3はchr関数を参照する回数も大幅に異なります。f1ではループ内にchr関数を書いたことにより、chr関数を256回も呼び出していました。呼び出しの度にインタープリタはchr関数がどこに定義されているかを探し出さなくてはいけません。

その一方、f3がchr関数を呼び出したのはたったの一回、map関数に使うために呼び出しただけでした。

def f3(list):
    string = ""
    for character in map(chr, list):  # chrはこの一度しか呼び出されない
        string = string + character   # ループ内に関数を使っていない
    return string

速度

原文: f3の処理時間 = f1の処理時間 * 0.5
私の手元(3系): f3の処理時間 = f1の処理時間 * 0.75

ラムダ式とmap, filter, reduceの組み合わせを避ける

処理速度が速い順に並べると、以下のようになります。

ビルトイン関数とmap, filter, reduceの組み合わせ (f3)
for loop (f1)
ラムダ式とmap, filter, reduceの組み合わせ(f2)

今回の検証では、ラムダ式とmap, filter, reduceの組み合わせは最も遅くなりました。256回もラムダ式を呼び出すのにコストがかかってしまうからです。

def f2(list):
        return reduce(lambda string, item: string + chr(item), list, "")

速度

原文: f2の処理時間 = f1の処理時間 * 1.6
私の手元(3系): f2の処理時間 = f1の処理時間 * 1.8

計算量を意識する

計算量がO(n)なのか、O(n^2)なのかを意識します。他の関数はO(n^2)で動くのに対し、f6はその課題を克服しています。

原文ではf6よりも速いf7が登場するのですが、私の手元ではf6が最速でした。Python3系での最速はf6と言えます。

def f6(list):
    return "".join(map(chr, list))

速度

原文: f6の処理時間 = f1の処理時間 * 0.1
私の手元(3系): f6の処理時間 = f1の処理時間 * 0.4

上記以外の高速化Tips

ループの内側を高速化しようと考える

Pythonに限らず、ループの内側は呼び出される回数が多いので優先的に高速化を検討します。

短く書く

短い行数で書けないか検討しましょう。短く書くことで、Pythonインタプリタが高速に動きます。特にbytecode instructionとvariable look-upの処理が速くなります。

bytecode instructionとは、拡張子.pyのソースコードを、仮想マシンが読める.pycや.pyoに書き換える処理のことを指します。短い行数で処理を書けば、bytecode instructionに必要が時間が短縮されます。

variable look-upとは変数の定義を探す処理のことです。短い行数で書けば変数の数も少ないため、処理に必要な時間が短縮できます。

あとがき

本記事ではPython3系では原文から重要である箇所を抜き出し、一部内容は省いています。さらに興味を持たれた方は、原文をお読みください。原文は物語調で話が進んでいきます。

本記事ではPythonを高速に動かすことに焦点を当てています。そのため関数が読みづらい部分もあります。実際には高速にするべきところとそうでないところを分け、読みやすさと速度のバランスを取るべきだと思います。

また本記事に間違いなどございましたらコメントして頂けると助かります。

※ Guido van Rossum氏がこの記事を書いたのはPython1系の時代だと思われます。しかし私の手元で動かしてみたところ、Python3系でも充分その知識を活かすことができると分かりました。

※ 関数はPython3系で動くように若干変更を加えました。

※ 処理速度は原文に記載されたものと、私の手元のPython3系で計算されたものを併記します。