Python を高速化したい

表. 比較したもの一覧
項番 低レベルな書き方 高レベルな書き方 > 速い書き方
1 変数の参照 属性の参照 > 変数の参照
2 ベタ書き 関数 > ベタ書き
3 while 文 for 文 > for 文
4 for 文 list 内包表記 > list 内包表記
5 1次元リスト 2次元リスト > 2次元リスト
6 iterator generator > iterator
7 if 文 例外 > -


この表だけ書かれても「何を言ってんだ?」みたいになると思います。具体例は次の通りです。

なお速度の比較には、 Python に最初からくっついてくる timeit モジュール を使って速度の計測をしています。

ここでは触れないこと
• Cython など別言語への書き換え、あるいは利用

1. 変数の参照と属性の参照速度の比較

答え: 変数を参照する方が速い。

# 変数の参照, 一旦変数に格納する。
a = c.a
a

# 属性の参照
c.a


2倍くらい速かったりする。

$ sample.py
0.04434641800071404
0.014238083000236657
import timeit

setup = """\
class C:
    def __init__(self, a):
        self.a = a
c = C(0)
"""

stmt = """\
c.a
"""

print(timeit.timeit(stmt, setup, number=1_000_000))


setup = """\
class C:
    def __init__(self, a):
        self.a = a
c = C(0)
a = c.a
"""

stmt = """\
a
"""

print(timeit.timeit(stmt, setup, number=1_000_000))


同様にして、よく使うメソッドなども変数に代入すると速くなったりする。

>>> lst = [0, 1, 2, 3, 4]
>>> pop = lst.pop
>>> pop()
4
>>> pop()
3
>>> pop()
2
>>> pop()
1
>>> pop()
0
>>> pop()
IndexError: pop from empty list
>>>
>>> # lst は空っぽに
>>> lst
[]
>>>

メソッドを参照すると、インスタンスメソッドオブジェクトを生成するという処理が走っています。変数に代入することで、その処理もなくすことができます。
Python のクラスオブジェクトとインスタンスオブジェクトって何?

2. ベタ書きと関数の速度の比較 max, math.ceil

答え: ベタ書きの方が速い。


Python は関数やメソッドの呼び出しコストが結構大きいので、内部で何度も呼び出されている関数を単純にベタ書きするだけで、処理速度が少し速くなったりします。cProfile で cumtime が大きかった時の対処法の1つです。

◯ max 関数の書き換え

以下の例では 10 倍速くなる。実際に関数をベタがきしただけで 10 倍速くなるなんてことはあんまりありませんが。

$ # ベタ書きのコード
$ python -m timeit -n 1000 "max(2, 1)"
1000 loops, best of 3: 0.234 usec per loop
$ # 関数を使ったコード
$ python -m timeit -n 1000 "2 if 2 > 1 else 1"
1000 loops, best of 3: 0.0379 usec per loop

◯ もう少し込み入ったコードで比較してみる。

この例では、実行時間が 25% 速くなる。

$ # 関数を使ったコード 3.53 usec
$ python -m timeit -s "from rectangle import *" "Rectangle(0, 0, 10, 10) & Rectangle(5, 5, 15, 15)" 
100000 loops, best of 3: 3.53 usec per loop
$ # ベタ書きのコード 2.67 usec
$ python -m timeit -s "from rectangle import *" "union(Rectangle(0, 0, 10, 10), Rectangle(5, 5, 15, 15))"
100000 loops, best of 3: 2.67 usec per loop
""""rectangle.py"""

class Rectangle(object):
    def __init__(self, x1, y1, x2, y2):
        if not (x1 <= x2 and y1 <= y2):
            raise ValueError(
              "Coordinates are invalid.\n" +
              "Rectangle" + str((x1, y1, x2, y2)))
        self.x1 = x1
        self.y1 = y1
        self.x2 = x2
        self.y2 = y2

    # 書き方1 max, min 関数だと重い...
    def __and__(self, other):
        """Return intersection region."""
        a, b = self, other
        x1 = max(a.x1, b.x1)
        y1 = max(a.y1, b.y1)
        x2 = min(a.x2, b.x2)
        y2 = min(a.y2, b.y2)
        if x1 < x2 and y1 < y2:
            return type(self)(x1, y1, x2, y2)


# 書き方2 if 文でベタ書きにすると少し速くなる。
def union(self, other):
    """Return intersection region."""
    a, b = self, other
    x1 = a.x1 if a.x1 > b.x1 else b.x1
    y1 = a.y1 if a.y1 > b.y1 else b.y1
    x2 = a.x2 if a.x2 < b.x2 else b.x2
    y2 = a.y2 if a.y2 < b.y2 else b.y2
    if x1 <= x2 and y1 <= y2:
        return Rectangle(x1, y1, x2, y2)

◯ math.ceil 関数の書き換え

これは 10 倍くらい速度に違いがる。
Python で割り算をするときの切り上げと切り捨て



3. for 文と while 文の速度の比較

答え: for 文が速い。

この節は以下の記事の劣化版です。
その1. 配列の初期化を高速化する | あなたのPythonを爆速にする7つの方法


素数 3,000 * 3,000 のリストを初期化するときの速度を比較してみます。

$ python -m timeit "lst = [None]*3000*3000"
10 loops, best of 3: 49.6 msec per loop


2. for statemnet

$ python -m timeit "lst = []" "for i in range(3000*3000): lst.append(None)"
10 loops, best of 3: 934 msec per loop


3. for statemnet - list comprehension

$ python -m timeit "lst = [None for i in range(3000*3000)]"
10 loops, best of 3: 411 msec per loop


4. while statement

$ python -m timeit "lst = []" "i = 0" "while i < 3000*3000: lst.append(None); i += 1"
10 loops, best of 3: 1.49 sec per loop


5. while statement with iterator

$ python -m timeit "lst = []" "iterator=iter(range(3000*3000))" "while True:" "  try: next(iterator)" "  except StopIteration: break" " 
 lst.append(None)"
10 loops, best of 3: 2.17 sec per loop


6. while statement with iterator (optimized)

$ python -m timeit "lst = []" "n=iter(range(3000*3000)).__next__" "a=lst.append" "while True:" "  try: n()" "  except StopIteration: break" "  a(None)"
10 loops, best of 3: 1.13 sec per loop


全てコマンドで書きましたが、読みづらいと思います。実はスクリプト内で文字列にして timeit 関数に渡す方法もあります。
list_initialization_comparison.py | GitHubGist

考察:

単純に初期化したいだけなら、掛け算 [None] * n が一番速い。

3. list comprehension は 2. for statement より速い。
Pythonのリスト内包表記の速度

2, 3. for statement は 4, 5, 6. while statement より速い。

例1 の loops が 10,000,000 回, 例2 の loops が 10 回で回数が異なっていることに留意してください。勝手に値が設定されるようです。-n オプションで値を指定できます。

Python の for 文は遅い?

Numpy などの数値計算を行う人たちにとって、一般に Python の for 文は遅いとされます。代わりに Numpy が提供するベクター演算を使用するように書かれることが多いです。

そのため、自分は for 文よりも while 文の方が速いのかなと思っていたのですが、実際にはより低レベルに記述した while 文よりも for 文の方が速いことがわかりました。

for 文そのものよりも四則演算時の型変換が、コストを食っているようです。 Python の for 文は遅い?

この後にみる2次元リストと1次元リストの参照速度の比較でも、四則演算に伴う型変換によって、処理速度が遅くなっている例が確認できます。

◯ 6. while statement with iterator (optimized) について

適当に読み飛ばしてください。

6. while statement with iterator (optimized) は 4. while statement に 3 つの工夫を加えています。

1 つ目は while statement による条件の判定を無くしました。while i < 3000*3000: は都度、条件を判定しているので、これを iterator を使った例外処理に置き換えています。置き換えたものが 5. while statement with iterator になります。しかし、 4 よりも 5 の方が遅くなっていますね。そこでさらに 3 つの工夫を加えます。

2 つ目の工夫は、関数呼び出しのコストを削っています。通常 iterator は 5. while statement with iterator にあるように next(iterator) として使います。しかし、ここでは next 関数は iterator.__next__ メソッドを呼び出しているだけです。そこで直接 iterator.__next__ メソッドを呼び出して next 関数を呼び出しのコストを削っています。

3 つ目の工夫は、属性の参照のコストを削っています。通常メソッドの呼び出しは obj.method(parameters) です。これを method=obj.method として method(parameters) で呼び出せるようにします。

4. for 文と list 内包表記の速度の比較

答え: list 内包表記の方が速い。

上記 3 を参考にしてください。

6. 1 次元リストと 2 次元リストの参照速度の比較

答え: 一般に2次元リストの方が速い。


2 次元リストと 2 次元リストを 1 次元リストで表現したものの参照速度を比較してみます。

# 2 次元リストを 1 次元リストで表現したもの
lst1[n*row + col]

# 2 次元リスト
lst2[row][col]

◯ 直接リテラル(数字)を代入

1次元リストの方が速い。

1. 2 次元リストを 1 次元リストで表現したもの

$ python -m timeit -s "lst=[None]*3000*3000" "lst[1500*3000+1500]"
10000000 loops, best of 3: 0.0335 usec per loop

2. 2 次元リスト

$ python -m timeit -s "lst=[[None]*3000 for i in range(3000)];row=1500;col=1500" "lst[row][col]"
10000000 loops, best of 3: 0.0676 usec per loop
考察

単純に 2 次元リストを使うよりも1次元リストを 2 次元のリストとして表現した方が 2 倍早い。

これはおそらく 2 次元リストは、リストの参照を 2 度しているからだろう..

>>> # 要素 element を取得するのに1度の参照で済む
>>> element = lst1[1500*3000+1500]
>>>
>>> # 要素 element を取得するのに 2 度の参照しないといけない。
>>> col = list2[1500]
>>> element = col[1500]
>>>



◯ 変数 row, col に代入

2次元リストの方が速い。

3. 2 次元リストを 1 次元リストで表現したもの

$ python -m timeit -s "lst=[None]*3000*3000;row=1500;col=1500;N=3000" "lst[row*N+col]"
10000000 loops, best of 3: 0.115 usec per loop

10000000 loops, best of 3: 0.0318 usec per loop
3回、1000万回ループを実行して、その3回のうち、もっとも早かった平均の1ループあたりの時間は 0.115 マイクロセカンド


4. 2 次元リスト

$ python -m timeit -s "lst=[[None]*3000 for i in range(3000)];row=1500;col=1500" "lst[row][col]"
10000000 loops, best of 3: 0.0676 usec per loop
考察

おそらく row*N+col という計算が、遅くしている気配がある。この計算に型推論の処理がはいってしまっている。反対に 1500*3000+1500 には型推論がはいっていないものと思われる。

変数代入して計算するよりも、代入しないで計算し方が速いということだが、そんなことをするシーンは滅多にないので、この記事では節を設けなかった。

最初は純粋に変数を参照するコストかなと思ったが、3 と 4 の実行時間の値がほとんど一緒だったので、変数を参照するコストではないと判断した。しかし、ここまで型推論のコストが大きいとは...

一般にリストを参照するときに直接リテラルで参照する機会は少ないので、2次元リストの方が一般には速いと考えるのが妥当だと思う。



7. イテレータとジェネレータの速度の比較

答え: イテレータの方が速い

2分木を iterable にして、for 文で実行した時の速度を比較しました。ジェネレータは若干速度が落ちるようです。可読性は良くなるものの。
Python のイテレータとは

$ python measure_time.py 
iterator:   3.342884984000193
generator:  4.266608483001619
# measure_time.py
import timeit

setup = """\
# https://gist.github.com/domodomodomo/1e124f2a58bff682c973dc46e8ab76b1
from binary_search_tree import BinarySearchTree
tree = BinarySearchTree()
tree.insert_list([6, 4, 3, 2, 7, 8])
"""


stmt_iter = """\
for element in tree.generate_sorted_list(): element
"""
print('iterator:  ', timeit.timeit(stmt_iter, setup))

stmt_yield = """\
for element in tree: element
"""
print('generator: ', timeit.timeit(stmt_yield, setup))

8. if 文と 例外の速度の比較(書きかけ)

答え: 時と場合による。

例外の場合は、条件式の処理がはいりません。そのため、もし条件の判定がほとんど真のみである場合は、例外を使った方が速い気がします。
Python でリストを比較する。

その他の速度の比較

いままで見てきた通り Python は思わぬ処理が重かったりします。以下の記事は Python の特徴、特に list の扱いについて勉強になります。

あなたのPythonを爆速にする7つの方法 |
続・あなたのPythonを爆速にする7つの方 |