項番 | 分類 | 低レベルな書き方 | 高レベルな書き方 |
---|---|---|---|
1 | 順次 | 速 リテラルの参照 | 遅 変数の参照 |
2 | 順次 | 速 変数の参照 | 遅 属性の参照 |
3 | 順次 | 速 ベタ書き | 遅 関数 |
4 | 反復 | while 文 | 速 for 文 |
5 | 反復 | 遅 for 文 | 速 list 内包表記 |
6 | 反復 | 速 iterator | 遅 generator |
7 | 分岐 | 謎 if 文 | 謎 例外 |
表は、感覚的に把握するためのもので、ごく大雑把に記載しています。
実際のコードと合わせて、ふーんと読み流していただけると嬉しいです。
◯ ポイント
必ずしも早くなるわけではなさそう
反復のカテゴリは低レベルに書いても、遅かったです。これは Python は 1 + 1 とかの四則演算が重すぎて Python レベルで低レベルなコードを書いても速くならない感じがします。
ここで取り扱うこと
• Python の構文を使った処理速度の比較
• 最初から入ってる組込関数、型、モジュールを使った処理速度の比較
ここで取り扱わないこと
• NumPy など外部ライブラリの利用
• C など別言語への書き換え(例えば Cython を利用して C 言語に書き換え)
ここで利用するツール
• timeit モジュール(簡単に使い方を記載しました。)
1. リテラルの参照と変数の参照
1.1. int
$ # リテラルの参照 $ python -m timeit "1" "1" "1" 100000000 loops, best of 3: 0.00875 usec per loop $ python -m timeit "1;1;1" 100000000 loops, best of 3: 0.0087 usec per loop
$ # 変数の参照 $ python -m timeit -s "a=1" "a;a;a" 10000000 loops, best of 3: 0.0231 usec per loop $ python -m timeit -s "a=1" "a" "a" "a" 10000000 loops, best of 3: 0.0236 usec per loop
1.2. str
$ # リテラルの参照 $ python -m timeit "'Hello'" "'Hello'" "'Hello'" 100000000 loops, best of 3: 0.0088 usec per loop $ python -m timeit "'Hello';'Hello';'Hello'" 100000000 loops, best of 3: 0.00872 usec per loop
$ # 変数の参照 $ python -m timeit -s "s='Hello'" "s" "s" "s" 10000000 loops, best of 3: 0.0226 usec per loop $ python -m timeit -s "s='Hello'" "s;s;s" 10000000 loops, best of 3: 0.0227 usec per loop
1.3. tuple
$ # リテラルの参照 $ python -m timeit "(1,2,3);(1,2,3);(1,2,3)" 10000000 loops, best of 3: 0.0222 usec per loop $ python -m timeit "(1,2,3)" "(1,2,3)" "(1,2,3)" 10000000 loops, best of 3: 0.0219 usec per loop
$ # 変数の参照 $ python -m timeit -s "a=(1,2,3)" "a" "a" "a" 10000000 loops, best of 3: 0.0237 usec per loop $ python -m timeit -s "a=(1,2,3)" "a;a;a" 10000000 loops, best of 3: 0.0238 usec per loop
1.4. list
list だけ変数を参照した方が速い。
$ # リテラルの参照 $ python -m timeit "[1,2,3]" "[1,2,3]" "[1,2,3]" 10000000 loops, best of 3: 0.185 usec per loop $ python -m timeit "[1,2,3];[1,2,3];[1,2,3]" 10000000 loops, best of 3: 0.186 usec per loop
$ # 変数の参照 $ python -m timeit -s "a=[1,2,3]" "a" "a" "a" 10000000 loops, best of 3: 0.0228 usec per loop $ python -m timeit -s "a=[1,2,3]" "a;a;a" 10000000 loops, best of 3: 0.0222 usec per loop
理由はよくわかりません。list はリテラルで参照されると、その都度、オブジェクトをインスタンス化する処理が走ってることが原因かなと思ったのですが、リストは変数に代入しない限りオブジェクトを生成しませんでした。
>>> id([1,2,3]), id([1,2,3]), id([1,2,3]) (4356275400, 4356275400, 4356275400) >>> >>> id([1,2,3]) 4356275400 >>> >>> a = [1,2,3] >>> id(a) 4356275400 >>> >>> # 新しい identity が生成された >>> id([1,2,3]) 4356275528 >>>
immutable なオブジェクトはインスタンス化される際、値が同じなら(== が True)ならインスタンスを生成せずに、値が同じ identity のオブジェクトを返します。ただし、なぜか tuple だけは one liner で書いた時に複数のオブジェクトを生成します。
>>> id((1,2,3)), id((1,2,3)), id((1,2,3)) (4356281112, 4356031328, 4356268680) >>>
◯ list と tuple の比較
list と tuple のコストの比較する。変数に代入して list にオブジェクトを生成させるようにする。
$ python -m timeit "a=[1,2,3]" "b=[1,2,3]" "c=[1,2,3]" 10000000 loops, best of 3: 0.197 usec per loop $ python -m timeit "a=(1,2,3)" "b=(1,2,3)" "c=(1,2,3)" 10000000 loops, best of 3: 0.0398 usec per loop
2. 変数の参照と属性の参照速度の比較
2.1. インスタンス変数の参照
# 変数の参照, 一旦変数に格納する。 # a = c.a a
# 属性の参照
c.a
2倍くらい速かったりする。
$ access_comparison.py 0.04434641800071404 0.014238083000236657
2.2. メソッドの参照
メソッドを変数に代入すると速くなる。
# メソッドの参照 lst.pop()
# 変数の参照, 一旦変数に格納する。 # pop = lst.pop() pop()
メソッドを参照すると、属性の参照だけではなく、関数からメソッドに変換するという処理も合わせて走っています。変数に代入することで、その処理もなくすことができます。
Python の関数とメソッドの違いって何?
メソッドを変数に代入したときの動作はこんな感じです。
>>> 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 -m timeit -s "pop=[i for i in range(10000000)].pop" "pop()" 10000000 loops, best of 3: 0.0792 usec per loop $ $ # メソッドの参照 $ python -m timeit -s "lst=[i for i in range(10000000)]" "lst.pop()" 10000000 loops, best of 3: 0.115 usec per loop $
1 次元リストと 2 次元リストの参照速度の比較
(1, 2 の複合問題)
2 次元リストと 2 次元リストを 1 次元リストで表現したものの参照速度を比較してみます。
# 2 次元リストを 1 次元リストで表現したもの
lst1[n*row + col]
# 2 次元リスト
lst2[row][col]
2次元リストを1次元で表現するのは、競技プログラミングのコードを見ていたらでてきたコードです。C などでは1次元リストで表現した方が速いそうです。Python では、どうでしょうか。
◯ 直接リテラル(数字)を代入
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)]" "lst[1500][1500]" 10000000 loops, best of 3: 0.068 usec per loop
◯ 考察 その1
単純に 2 次元リストを使うよりも1次元リストを 2 次元のリストとして表現した方が 2 倍早い。
これはおそらく 2 次元リストは、リストの参照を 2 度しているからだろう..
>>> # 要素 element を取得するのに1度の参照で済む >>> element = lst1[1500*3000+1500] >>> >>> # 要素 element を取得するのに 2 度の参照しないといけない。 >>> col = list2[1500] >>> element = col[1500] >>>
◯ 変数 row, col に代入
2次元リストの方が速い。なんと、1次元リストの時と結果が逆転しました。
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
◯ 考察 その2
なぜ、変数を使用した場合、2次元リストを1次元リストで表現すると、リテラルを使用した場合の結果と逆転してしまうほど、参照速度が遅くなってしまったのでしょうか?言い換えれば、なぜ 1500*3000+1500
は row*N+col
よりも圧倒的に遅いのでしょうか?
Python は型変換が重いからかなと思ったのですが。dis で表示させて見たら、そもそもリテラル 1500*3000+1500
の場合は、Python のバイトコードレベルでは BINARY_ADD をしていませんでした。また 1 + 1 は 1 つのリテラルとして扱っていました。
>>> import dis >>> def f(): return 1 + 1 ... >>> dis.dis(f) 1 0 LOAD_CONST 2 (2) 2 RETURN_VALUE >>>
>>> import dis >>> b = 1 >>> def g(): return b + b ... >>> dis.dis(g) 1 0 LOAD_GLOBAL 0 (b) 2 LOAD_GLOBAL 0 (b) 4 BINARY_ADD 6 RETURN_VALUE >>>
◯ 考察 その3
属性参照よりも四則演算の方が重い。
3. ベタ書きと関数の速度の比較 max, math.ceil
Python は関数やメソッドの呼び出しコストが結構大きいので、内部で何度も呼び出されている関数を単純にベタ書きするだけで、処理速度が少し速くなったりします。cProfile で cumtime が大きかった時の対処法の1つです。
3.1. max 関数の書き換え
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
3.2. math.ceil 関数の書き換え
10 倍速くなる。
Python で割り算をするときの切り上げと切り捨て
4. for 文と while 文の速度の比較
4.1. list の初期化
for 文が速い。
この節は以下の記事の劣化版です。
その1. 配列の初期化を高速化する | あなたのPythonを爆速にする7つの方法
要素数 3,000 * 3,000 のリストを初期化するときの速度を比較してみます。
# 1. multiplicative list lst = [None] * 3000 * 3000
# 2. for statement lst = [] for i in range(3000 * 3000): lst.append(None)
# 3. for statement list comprihention lst = [None for i in range(3000 * 3000)]
# 4. while statemetn lst = [] i = 0 while i < 3000 * 3000: lst.append(None) i += 1
# 5. while statement with iterator lst = [] iterator = iter(range(3000 * 3000)) while True: try: next(iterator) except StopIteration: break lst.append(None)
# 6. while statement with iterator 2 lst = [] iterator = iter(range(3000 * 3000)) n = iterator.__next__ a = lst.append while True: try: n() except StopIteration: break a(None)
$ python 4_1_list_initialization_comparison.py multiplicative list: 0.5668 for statement: 10.0157 for statement list comprihention: 4.6668 while statemetn: 15.5053 while statement with iterator: 22.6594 while statement with iterator 2: 12.3348
単純に初期化したいだけなら、掛け算 [None] * n
が一番速い。
2, 3. for statement は 4, 5, 6. while statement より速い。
3. list comprehension は 2. for statement より速い。
Pythonのリスト内包表記の速度
◯ 6. while statement with iterator (optimized) について
頑張って while 文を速くしようしました。それでも、どうあがいても for 文よりも while 文を速くできませんでした。適当に読み飛ばしてください。
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.2. 素因数分解
for 文が速い。
def prime_decomposition_while(n): # 素数と仲良しになる3つのプログラム # http://cocodrips.hateblo.jp/entry/2014/02/02/011119 i = 2 table = [] while i * i <= n: while n % i == 0: n //= i table.append(i) i += 1 if n > 1: table.append(n) return table
def prime_decomposition_for(n): table = [] for i in range(2, n): if i * i > n: break while n % i == 0: n //= i table.append(i) if n > 1: table.append(n) return table
from itertools import count def prime_decomposition_for_itertools(n): table = [] for i in count(2, 1): if i * i > n: break while n % i == 0: n //= i table.append(i) if n > 1: table.append(n) return table
$ python 4_2_prime_decomposition.py ------ n = 991325085943 size of range = 48 prime_decomposition_while : 2.5365 prime_decomposition_for : 2.5661 prime_decomposition_for_itertools : 2.5816 ------ n = 980360499696375077594137 size of range = 48 prime_decomposition_while : 2.6468 prime_decomposition_for : 4.0854 prime_decomposition_for_itertools : 2.8494 ------ n = 9637970362374241428864537729537742085603 size of range = 48 prime_decomposition_while : 3.1064 prime_decomposition_for : 4.2044 prime_decomposition_for_itertools : 3.0990 ------ n = 94751341710292423468751439925175147782394341451444769457 size of range = 48 prime_decomposition_while : 3.3410 prime_decomposition_for : 4.4326 prime_decomposition_for_itertools : 3.3103 $
◯ 考察
相当数 n が大きければ while 文が速くなる。ただ、そこまで大きな n を扱うことはないかなと...。
range オブジェクトのサイズを求めているのは何故か n が大きくなると for 文の動作が遅くなるので、range が悪さをして大量のメモリを確保してるのかなと思ったから。実際には Python3 では range は Python2 の xrange とほぼ同じ動作をするので、そのようなことはなさそう。
xrange | Python 2.7.x と 3.x の決定的な違いを例とともに
Why is there no xrange function in Python3?
ただ itertools の count を使うと n が大きくなっても速度が遅くならない。ちなみに itertools 自体は C で実装されている様子。
cpython/Modules/itertoolsmodule.c
itertools の count と range は、ほぼ同じことをしていると思ったけど、なぜ結果が違うんだろう... CPython の実装か、dis したらわかるんだろうか。
4.3. 素数のリスト(エラトステネスの篩)
for 文が速い。
def primes_for(n): is_prime = [True] * (n + 1) is_prime[0] = False is_prime[1] = False for i in range(2, n + 1): for j in range(i * 2, n + 1, i): is_prime[j] = False return [i for i in range(n + 1) if is_prime[i]]
def primes_while(n): is_prime = [True] * (n + 1) is_prime[0] = False is_prime[1] = False i = 2 while i <= n: j = i + i while j <= n: is_prime[j] = False j += i i += 1 return [i for i in range(n + 1) if is_prime[i]]
$ python 4_3_sieve_of_eratosthenes.py primes_for : 1.0813 primes_while : 1.2748 $
◯ 考察
4.1 のように n を大きくして実行時間を確認していないが、おそらく同じようにかなり大きくすると while 文の方が速くなるかもしれない。range の動作が、気になる。
エラトステネスの篩自体は速いアルゴリズムらしい。
とりあえずエラトステネスのふるいの方が速いことを理解しておいてください。
エラトステネスのふるいとその計算量
またエラトステネスの篩の高速化についてはこちらで検討した。
Python でエラトステネスの篩
◯ 思ったこと
for 文は速い
NumPy などの数値計算を行う人たちにとって、一般に Python の for 文は遅いとされます。代わりに NumPy が提供するベクター演算を使用するように書かれます。だから 「for 文は遅い」と言われます。
そのため、自分は for 文よりも while 文の方が速いのかなと思っていたのですが、実際にはより低レベルに記述した while 文よりも for 文の方が速いことがわかりました。
理由は for 文そのものが遅いというよりも、四則演算の、さらに四則演算そのものではなく、型推論がコストを食っているらしいです。
Python の for 文は遅い?
言い換えれば、「for 文が遅いのではなく、Python が遅い言語だ。型推論が重いから。」と言い換えるとわかりやすいかもしれません。
5. for 文と list 内包表記の速度の比較
上記 4.1 の結果でもそうでしたが、
一般的に list 内包表記の方が速いそうです。
Pythonのリスト内包表記の速度
Pythonの内包表記はなぜ速い?
Pythonのリスト内包表記をdisる
6. イテレータとジェネレータの速度の比較
2分木を iterable にして、for 文で実行した時の速度を比較しました。ジェネレータは若干速度が落ちるようです。可読性は良くなるものの。ファイルを取り扱うなどの大量のメモリを消費する場合は、ジェネレータの方が速くなるのかもしれないけど、検証はしてない。
Python のイテレータとは
# iterator: list の iterator を計測 for element in tree.generate_sorted_list(): element
# generator: __iter__ を generator で実装して計測 for element in tree: element
$ python 6_0_binary_serach_tree.py iterator: 3.342884984000193 generator: 4.266608483001619
7. if 文と 例外の速度の比較
7.1. リストの比較
とりあえず、ここではリストを比較する処理を try-except, for-if, while-if の3つで比較しました。list を比較する処理は try-except を使ったものが最も速かったです。
Python でリストを比較する。
def subtract_list_try_remove(lst1, lst2): lst = lst1.copy() for element in lst2: try: lst.remove(element) except ValueError: continue return lst
def subtract_list_for_if(lst1, lst2): lst = lst1.copy() for e2 in lst2: for i, e1 in enumerate(lst): if e1 == e2: del lst[i] break return lst
def subtract_list_while_if(lst1, lst2): lst = lst1.copy() for e2 in lst2: n = len(lst) i = 0 while i < n: # e1 = lst[i] if lst[i] == e2: del lst[i] break i += 1 return lst
$ python 7_0_subtract_list.py lst1, lst2 try_remove:0.023619660999884218 for_if: 0.059453995999774634 while_if: 0.1252107430000251 lst3, lst4 try_remove:0.0096084689998861 for_if: 0.028350236999813205 while_if: 0.06406809700001759 lst5, lst6 try_remove:1.7117234370002734 for_if: 6.321766858000046 while_if: 12.80545006400007 $
◯ なんで remove は速いの?
list.remove は C で実装されているから。
CPython のコードを覗いてみた | Python の list.remove メソッド
リストの走査→比較→削除の一貫した操作を C で実行して速くしてるような感じです。反対に for や while を使ってしまうと、比較するために Python 側に取り出すことになり、操作が重くなります。
もちろん要素が存在しないと例外発生してしまいますが、感覚的には if 文内で行われる条件判定のための型推論を伴う四則演算が例のごとく重くて、例外が、ちょっとやそっと発生したくらいでは問題にならないような感じかなと思っています。
try/except ブロックは、例外が発生しなければ極めて効率的です。実際には例外を捉えることは、とても重い処理です。
A try/except block is extremely efficient if no exceptions are raised. Actually catching an exception is expensive.
How fast are exceptions?
簡単に言えば、最初から提供されている神々が書いてくれた組み込みの関数を使った方が速いということですね。
7.2. iterator
例えば Python では iterator が最後まで行ったかどうかを判定するのに、条件式ではなく StopIteration という例外で実装しています。 これについては、速度の比較を実施していません。いつか時間ができたら、したいと思います。
# Python ... 例外 StopIteration iterator = iter(sequence) while True: try: print(next(iterator)) except StopIteration: break
// Java ... 条件 hasNext Iterator it = sequence.iterator(); while (it.hasNext()) { System.out.println(it.next()); }
解決した問題 - PEP 234 Iterators
Resolved Issues - PEP 234 Iteratorsイテレーションの終端であることを示すシグナルに対して、例外を使うことがあまりにも処理が重すぎないか、疑問であった。
It has been questioned whether an exception to signal the end of the iteration isn't too expensive.end 関数を呼び出すことは、1度のイテレーションで2度の呼び出しをしないといけない。2つの呼び出しは、例外の検査を含めた1度の呼び出しよりも重い処理である。特に実行速度が重要な for ループに対して、例外のための検査をとても軽い処理で行える。
Calling an end() function would require two calls per iteration. Two calls is much more expensive than one call plus a test for an exception. Especially the time-critical for loop can test very cheaply for an exception.
C で書かれたモジュールと
Python で書かれたモジュールについて
上記のリストを比較するコードで C で組まれた remove を活用したように
C で組まれたモジュールを活用すると速い感じがします。
itertools などの C で書かれたモジュールは速い感じがします。
cpython/Modules/
copy などの Python で書かれたモジュールは遅い感じがします。
ただ、遅いとは言えども自分で0から組むよりはきっと、速いかなと。
cpython/Lib/
同じ機能を提供しているものがないので
両者を単純に比較することはできませんが...
また、同じモジュールであっても Python 側で実装されていたり、
C 側実装されていたりするそうです。
collections.OrderedDict は Python 側で実装された型であるのに対して、同じモジュールにある collections.defaultdict は C 言語側で実装されている型です。このことは実際に PyPy で相当数の問題を引き起こしています。これらの違いが目立たない類似の API を実現するため、できるだけオリジナルの型を模倣する必要があるからです。
Revenge of the Types: 型の復讐
請注意
ここで書かれていることを気にして、コーディングしない方が望ましいです。Python を高速化するための tips というよりも Python の動作とか性質が、だいたいどんなものかを理解するための記事と捉えていただけると嬉しいです。お前、今さらそれを言うのかよって感じですが...。
ここで書いていることは、基本的には競技プログラミングなどの限定された世界での tips です。もし、実行速度を優先する場合は、より良いアルゴリズム、データ構造の採用、あるいは、ここでは取り扱わない NumPy など外部ライブラリの利用、Cython を使って Python のモジュールを C 言語で書き直したりすることを検討してください。
特に Python で書くときは、高速化よりも可読性を重視した方が望ましいと感じます。理由は2つあります。
1つ目は ここで書かれていることを利用しても、部分的には何倍も早くできますが、全体としてはそんなに速くなりません。Python はもともと遅い言語です。その遅い言語を、可読性を損なってまでして、ちょっと速くしても得られるものは多くはありません。例えば、メソッドを変数に代入して実行なんてしてたら可読性がひどく損なわれます。
同じプログラムを別の C 言語などに書き換えれば何倍も早くなります。Python の高速化と書いてあっても、他のサイトや書籍 "ハイパフォーマンス Python" では、外部ライブラリや別言語への書き換えを書いてるのは、そのためだと思います。最初は、なんで Python の高速化なのに C 言語とか Fortran とか別言語の話をしてるんだろう?と疑問に思っていましたが。
100万倍速いプログラムを書く | Qiita
2つ目は Python は、適切に抽象化具合をあげて短く簡潔に書くことを前提にしていると思われるので。このことは、Python がそういった機能を提供しているし、PEP 8 - Style Guide for Python Code でも 1 行最大 79 文字とごく短く制限されていることから推測しています。
1 行を最大 79 文字以内に抑える方法と 1 行が 79 文字以内である理由
低レベルに書き込むことは、PEP 20 - The Zen of Python の言う、たったひとつだけあるはずのストレートなやり方ではないと思われるからです。
何かをやるには、ストレートなやり方がひとつ、
たったひとつだけあるはず
There should be one-- and preferably only one --obvious way to do it.
Python にまつわるアイデア: PEP 20 | Life with Python
その他の速度の比較 list の扱い
いままで見てきた通り Python は思わぬ処理が重かったりします。以下の記事は Python の特徴、特に list の扱いについて勉強になります。
あなたのPythonを爆速にする7つの方法 |
続・あなたのPythonを爆速にする7つの方 |
この記事では CPython の list の実装を説明しています。なぜ、リストの処理が重いのか、軽いのかを調べるときに便利かなと思って見てます。まだ、ちゃんと読んではいません。
Python のソースを読んでみる | Qiita