| 項番 | 分類 | 低レベルな書き方 | 高レベルな書き方 |
|---|---|---|---|
| 1 | 順次 | 速 リテラルの参照 | 遅 変数の参照 |
| 2 | 順次 | 速 変数の参照 | 遅 属性の参照 |
| 3 | 順次 | 速 ベタ書き | 遅 関数 |
| 4 | 反復 | 遅 while 文 | 速 for 文 |
| 5 | 反復 | 遅 for 文 | 速 list 内包表記 |
| 6 | 反復 | 速 リスト | 遅 イテレータ |
| 7 | 分岐 | 謎 if 文 | 謎 例外 |
表は、感覚的に把握するためのもので、ごく大雑把に記載しています。
実際のコードと合わせて、ふーんと読み流していただけると嬉しいです。
ここで取り扱うこと
• Python の構文を使った処理速度の比較
• 最初から入ってる組込モジュール、クラス、関数を使った処理速度の比較
ここで取り扱わないこと
• Numba など外部ライブラリの利用
• C など別言語への書き換え（例えば Cython を利用して C 言語に書き換え）
ここで利用するツール
• timeit モジュール(簡単に使い方を記載しました。)
請注意
ここで書かれていることを気にして、コーディングしない方が望ましいです。
ここで書かれていることは かなり重箱の隅をつつくようなことをしています。
ここで書かれていることは Python を高速化するための tips というよりも、
Python が内側でどんな動作をしているかに興味を持ってもらうためのきっかけになればと思いました。
• 実際の高速化に向けた流れ...
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 と tuple の比較
list と tuple のコストの比較すると tuple の方が速そうです。
◯ まとめ
リテラルの参照は、オブジェクトの生成→参照という２段階を踏んで、単純に変数の参照するよりも重くなるかなと思っていました。しかし実際には int, str, tuple については、変数よりもリテラルを参照した方が早いことがわかりました。
2. 変数の参照と属性の参照速度の比較
2.1. インスタンス変数の参照
# 変数の参照, 一旦変数に格納する。 # a = c.a a
# 属性の参照
c.a
２倍くらい速かったりする。
$ 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]
２次元リストを１次元で表現するのは、競技プログラミングのコードを見ていたらでてきたコードです。C などでは１次元リストで表現した方が速いそうです。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
考察
単純に 2 次元リストを使うよりも１次元リストを 2 次元のリストとして表現した方が 2 倍早い。
これはおそらく 2 次元リストは、リストの参照を 2 度しているからだろう..
>>> # 要素 element を取得するのに１度の参照で済む >>> element = lst1[1500*3000+1500] >>> >>> # 要素 element を取得するのに 2 度の参照しないといけない。 >>> col = list2[1500] >>> element = col[1500] >>>
2. 変数 row, col に代入
２次元リストの方が速い。なんと、１次元リストの時と結果が逆転しました。
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回のうち、もっとも早かった平均の１ループあたりの時間は 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
考察
なぜ、変数を使用した場合、２次元リストを１次元リストで表現すると、リテラルを使用した場合の結果と逆転してしまうほど、参照速度が遅くなってしまったのでしょうか？言い換えれば、なぜ 1500*3000+1500 は row*N+col よりも圧倒的に遅いのでしょうか？
Python は型変換が重いからかなと思ったのですが。dis で表示させて見たら、そもそもリテラル 1500*3000+1500 の場合は、Python のバイトコードでは BINARY_ADD をしていませんでした。また 1 + 1 は 1 つのリテラルとして扱っていました。
実は Python はコンパイルを行ない、バイトコードへ変換しています。CPython は、このバイトコード読み込んで処理を実行しています。バイトコードに変換される段階で、1 + 1 = 2 が実行されていたと言うことです。timeit では、複数回処理を実行してその平均値を返してくれますが、バイトコードへの変換は１度しか行っていません（詳細は後述）。
こういうのを 定数畳み込み と言うらしいです。ちなみに僕はバイトコードを、ほとんど理解していません。
>>> 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
>>>
バイトコードなんかあったっけ？って感じですが、たまに pyc 拡張子がついたファイルをたまに見かけると思います。
それが変換されたバイトコードになります。
As an important speed-up of the start-up time for short programs that use a lot of standard modules, if a file called ‘spam.pyc’ exists in the directory where ‘spam.py’ is found, this is assumed to contain an already-"byte-compiled" version of the module ‘spam’. The modification time of the version of ‘spam.py’ used to create ‘spam.pyc’ is recorded in ‘spam.pyc’, and the ‘.pyc’ file is ignored if these don't match.
6.1.2 "Compiled" Python files - An Introduction to Python by Guido van Rossum and Fred L. Drake, Jr.
timeit の中身を確認してみると for 文でひたすら stmt を繰り返してるので、
timeit はバイトコードへの変換は１度しか行なっていないことがわかります。
timeit には、わざわざ文字列にしたコードを引数に渡さないといけなかったのですが、こういう風に実装されていた訳ですね。
# 順番変えたり省略しています。 # 0 for 文で処理を繰り返す関数を作っています。 template = """ def inner(_it, _timer{init}): {setup} _t0 = _timer() for _i in _it: {stmt} _t1 = _timer() return _t1 - _t0 """ # 1 timeit.timeit が呼び出されると... def timeit(stmt="pass", setup="pass", timer=default_timer, number=default_number, globals=None): """Convenience function to create Timer object and call timeit method.""" return Timer(stmt, setup, timer, globals).timeit(number) class Timer: # 2 def __init__(self, stmt="pass", setup="pass", timer=default_timer, globals=None): ... 省略 ... src = template.format(stmt=stmt, setup=setup, init=init) self.src = src # Save for traceback display # 最適化フラグ -O を有効にしたのと同じ状態で # 関数 inner をバイトコードにコンパイルしています。 code = compile(src, dummy_src_name, "exec") # この exec は # 関数を実行しているのではなく # 関数を定義しています。 exec(code, global_ns, local_ns) # 定義した関数を属性に代入する。 self.inner = local_ns["inner"] # 3 def timeit(self, number=default_number): it = itertools.repeat(None, number) ... try: # 実際の計測は、こっちでやっています。 timing = self.inner(it, self.timer) ... return timing
compile(source, filename, mode, flags=0, dont_inherit=False, optimize=-1)
source を コードオブジェクト 、もしくは、 AST オブジェクトにコンパイルします。... 中略 ...
引数 optimize は、コンパイラの最適化レベルを指定します; デフォルトの値 -1 は、インタプリタの -O オプションで与えられるのと同じ最適化レベルを選びます。 明示的なレベルは、 0 (最適化なし、 __debug__ は真)、 1 (assert は取り除かれ、 __debug__ は偽)、 2 (docstring も取り除かれる) です。
2. 組み込み関数 - Python 標準ライブラリ
コードオブジェクト
コードオブジェクトはバイトコンパイルされた (byte-compiled) 実行可能な Python コード、別名 バイトコード (bytecode) を表現します。
内部型 - Python 言語リファレンス
なんだか文字列でコードを実行させたり、コンパイルしたり回りくどいですね。
正確に計測するための工夫らしいです。
このモジュールは、実行時間を計測するにあたって、いくつものよくある罠を回避しています。 オライリーから刊行されている Python Cookbook の中にある、 Tim Peter が書いたアルゴリズムの章の "はじめに" を参考にしてください。
This module avoids a number of common traps for measuring execution times. See also Tim Peters' introduction to the Algorithms chapter in the Python Cookbook, published by O'Reilly.
cpython/Lib/timeit.py
◯ まとめ
Python では属性参照も重いけど、四則演算の方がもっと重い気配がある。
| 二次元配列の参照速度 | < | 一次元配列の参照速度 |
| 属性参照 + 属性参照 | < | 属性参照 + 掛け算 + 足し算 |
| < | | |
| 属性参照 | < | 掛け算 + 足し算 |
3. ベタ書きと関数の速度の比較 max, math.ceil
Python は関数やメソッドの呼び出しコストが結構大きいので、内部で何度も呼び出されている関数を単純にベタ書きするだけで、処理速度が少し速くなったりします。cProfile で cumtime が大きかった時の対処法の１つです。
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 で割り算をするときの切り上げと切り捨て
3.3. 関数ではなく、ベタ書きと例外で終了を通知
Python のイテレータとは for 文そのものです。イテレータを理解すると for 文を、より深く理解できます。
Python では、ベタ書きして StopIteration という例外を投げてイテレータが終了したかどうかを判定します。
# Python ... 例外 StopIteration iterator = iter(sequence) while True: try: print(next(iterator)) except StopIteration: break
それに対して Java のイテレータパターンは、専用の関数 hasNext を実装してイテレータが終了したかどうかを判定します。
// Java ... 条件 hasNext Iterator it = sequence.iterator(); while (it.hasNext()) { System.out.println(it.next()); }
なぜ、Python では、このように実装しているのでしょうか？答えは、関数呼び出しが重いからです。
解決した問題 - 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 関数を呼び出すことは、１度のイテレーションで２度の呼び出しをしないといけない。２つの呼び出しは、例外の検査を含めた１度の呼び出しよりも重い処理である。特に実行速度が重要な 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.
比較したコード。
# 通常の for 文 def reverse(sequence): iterable = Reverse(sequence) # for statement lst = [] for element in iterable: lst.append(element) return lst
# 例外でベタ書き def reverse_exception(sequence): iterable = ReverseException(sequence) # for statement lst = [] iterator = iter(iterable) while True: try: element = next(iterator) except StopIteration: break lst.append(element) return lst
# 関数呼び出し def reverse_function(sequence): iterable = ReverseFunction(sequence) # for statement lst = [] iterator = iter(iterable) while has_next(iterator): element = next(iterator) lst.append(element) return lst
$ python 3_3_function_exception.py # reverse : 0.0000 reverse_exception : 0.0000 reverse_function : 0.0000 # reverse : 0.0001 reverse_exception : 0.0001 reverse_function : 0.0002 # reverse : 0.0008 reverse_exception : 0.0009 reverse_function : 0.0012 # reverse : 0.0070 reverse_exception : 0.0094 reverse_function : 0.0134 # reverse : 0.0720 reverse_exception : 0.0924 reverse_function : 0.1177 # reverse : 0.7840 reverse_exception : 0.9822 reverse_function : 1.2501 $
4. for 文と while 文の速度の比較
4.1. list の初期化
for 文が速い。
この節は以下の記事の劣化版です。
その1. 配列の初期化を高速化する | あなたのPythonを爆速にする７つの方法
要素数 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 より速い。
◯ 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 の方が遅くなっていますね。そこでさらにもう２つの工夫を加えます。
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. リストの要素の削除
リスト内包表記が速い。
実は Python ではリストの先頭に要素を挿入する操作 list.insert(0, value) が、とても遅いです。 CPython の実装をすこしだけ覗いて、簡単に説明させていただいています。
Python のコードの書き方で高速にすることは考える必要はないと思っています。 しかし、この list.insert(0, value) だけについては、 同等の操作をすることも多いですし、インパクトもかなり大きいので、押さえておいた方がいいかなと思ったりします。
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 : 0.0007 primes_while : 0.0006 # primes_for : 0.0096 primes_while : 0.0089 # primes_for : 0.1104 primes_while : 0.1124 # primes_for : 1.1346 primes_while : 1.3501 # primes_for : 15.7612 primes_while : 19.0832 $
◯ エラトステネスの篩
エラトステネスの篩は、速いアルゴリズムらしいです。
とりあえずエラトステネスのふるいの方が速いことを理解しておいてください。
エラトステネスのふるいとその計算量
エラトステネスの篩そのもののの高速化についてはこちらで検討しました。
Python でエラトステネスの篩
◯ なんで 4.1, 4.3 は、遅かったの？
4.1, 4.3 で while 文が遅かったのは index の更新 i = i + 1 という処理を自分で Python で書いてしまったからです。 for 文は C 言語で書かれた Python, CPython が i = i + 1 で計算を実行させています。
基本的には自分で Python で書くよりも、すでに C 言語で書かれた Python の機能を使った方が速くなります。 このあとリストの比較で list.remove メソッドを使う処理を紹介しますが、それも同じ考えです。
4.4. 素因数分解
while 文が速い。
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
import itertools def prime_decomposition_for_itertools(n): table = [] for i in itertools.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
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
$ python 4_4_prime_decomposition.py # prime_decomposition_for : 0.0001 prime_decomposition_for_itertools : 0.0001 prime_decomposition_while : 0.0001 # prime_decomposition_for : 0.0171 prime_decomposition_for_itertools : 0.0126 prime_decomposition_while : 0.0101 # prime_decomposition_for : 0.0436 prime_decomposition_for_itertools : 0.0324 prime_decomposition_while : 0.0297 # prime_decomposition_for : 0.0444 prime_decomposition_for_itertools : 0.0276 prime_decomposition_while : 0.0363 # prime_decomposition_for : 0.5400 prime_decomposition_for_itertools : 0.3824 prime_decomposition_while : 0.3909 # prime_decomposition_for : 0.7978 prime_decomposition_for_itertools : 0.5803 prime_decomposition_while : 0.5858 $
◯ 考察
4.1, 4.3 の結果を見ると 4.4 も for 文の方速いのだろうと思っていましたが、結果は違いました。 if 文を使って途中で break するようなケースでは for 文よりも while 文の方がたまに速かったりします。
じゃあ、どっちを選べばいいんだ？という話であります。 上の４つの結果 4.1, 4.2, 4.3, 4.4 を元に考えると、基本的には「きれいに書ける方で書く」と速くなると考えておけばいいかなと思います。
count の next と range の next
意地で for 文で速い書き方を探しました。itertools の count を使えば n が大きくなっても速度が遅くなりません。なぜ、このような結果の違いが生じたのでしょうか？
それは range がループする度に、終了の条件判定を行なっているからです。count はループする度に、終了の条件判定を行なっていません。
CPython の実装を覗いてみて確認しました。for 文がループする度に range は longrangeiter_next が count は count_nextlong が呼び出されています。
C の int 型, long 型などの操作に比べて PyObject に対する操作は、型を判定する処理が入るので、かなり重いはず です（後述）。longrangeiter_next は 4 回も PyObject に対する操作をしているのに count_nextlong は 1 回しか PyObject を操作していません。
どうやって、呼び出されてる箇所を調べたかについては、いつか解説したいと思います。 とりあえず、ここでは何度も count よりも range の方が PyObject が何度も操作されているということだけ、 なんとなく眺めておいてください。
// かなり省略しています。 // https://github.com/python/cpython/blob/master/Objects/rangeobject.c static PyObject * longrangeiter_next(longrangeiterobject *r) { // PyObject に対する操作は基本的に重いはず... PyObject *product, *new_index, *result; // 1. r->len < r->index なら終了 if (PyObject_RichCompareBool(r->index, r->len, Py_LT) != 1) return NULL; // 2. r->index = r->index + 1 new_index = PyNumber_Add(r->index, _PyLong_One); // 3. product = r->index * r->step product = PyNumber_Multiply(r->index, r->step); // 4. result = r->start + product result = PyNumber_Add(r->start, product); // r->index = new_index Py_SETREF(r->index, new_index); return result; }
// かなり省略しています // https://github.com/python/cpython/blob/master/Modules/itertoolsmodule.c static PyObject * count_nextlong(countobject *lz) { // PyObject に対する操作は基本的に重いはず... PyObject *long_cnt; PyObject *stepped_up; // 1. stepped_up = long_cnt + lz->long_step stepped_up = PyNumber_Add(long_cnt, lz->long_step); lz->long_cnt = stepped_up; return long_cnt; }
型を判定する処理が入るので、かなり重いはず
実は Python は、遅い言語だと言われます。遅い原因は、変数や属性に型を明示しないからだそうです。変数や属性に型が明示されていないため、型を判定する処理を付加する必要が生じます。
下記の記事では Cython を使って１つ１つ型定義をして徐々に高速化を計り、型に関わる処理がどれだけ重い処理であるかを示してくれています。型の有無でここまで処理速度に違いが生じるのは、驚きでした。
この中の
X*Yのような乗算処理では、次のような処理が行われる。
- X が乗算をサポートしているかチェックする
- X の乗算関数を取得する
- Y が被乗数として適切なデータかチェックする
- X の値と Y の値を取り出し、乗算する
- 乗算の結果から新しい浮動小数点数オブジェクトを作成する
実は Python には list に似た array というクラスがあります。
これは要素のクラスを明示することでリストの処理を高速にしてくれます。
以下のサイトで list と array の速度の比較をしています。
import array array.array('I', range(10)) # I は符号なしの int # array('I', [0, 1, 2, 3, 4, 5, 6, 7, 8, 9])
あなたのPythonを爆速にする７つの方法
続・あなたのPythonを爆速にする７つの方
8.7. array 効率のよい数値アレイ- Python 標準ライブラリ
◯ まとめ
上手く説明できていないのですが、基本的には、きれいに書ける方で書けば速くなります。 そのため、速度の面で for 文かな while 文かなと、そんなに気にすることはないかなと思います。
また、自分で Python で書いた時に、もし同じ機能を Python が提供してくれているならば そっちを使った方が速いです。
5. for 文と list 内包表記の速度の比較
上記 4.1 の結果でもそうでしたが、一般的に list 内包表記の方が速いそうです。ここで、ランダムな整数のリストを生成することを考えましょう。
[random() for i in range(10)]
random.randoint を使ってしまうと
funcscale
で通らなくなってしまうので、擬似乱数を生成するクロージャを用意しました。
これは 線形合同法 による擬似乱数生成器です。
昔、競プロの問題を解いていて、線形合同法を知らなくて、これの規則性を見つける問題と勘違いして、辛い思いをしました笑
def linear_congruential_generators(a, x, b, m): def _(): nonlocal x x = (a * x + b) % m return x return _ random = linear_congruential_generators(48271, 8, 0, 2**31 - 1) random() # 386168 random() # 1460846352 random() # 1741224500
比較した３つの書き方は、以下の通りです。
def for_statement(i): random = linear_congruential_generators(48271, 8, 0, 2**31 - 1) lst = [] for _ in range(10**i): lst.append(random()) return lst
def for_statement_speed_up(i): random = linear_congruential_generators(48271, 8, 0, 2**31 - 1) lst = [] append = lst.append for _ in range(10**i): append(random()) return lst
def for_statement_list_comprehension(i): random = linear_congruential_generators(48271, 8, 0, 2**31 - 1) return [random() for _ in range(10**i)]
実行結果は次の通りです。
$ python 5_1_statement_comprehension.py # for_statement : 0.0000 for_statement_speed_up : 0.0000 for_statement_list_comprehension : 0.0000 # for_statement : 0.0001 for_statement_speed_up : 0.0001 for_statement_list_comprehension : 0.0001 # for_statement : 0.0004 for_statement_speed_up : 0.0003 for_statement_list_comprehension : 0.0003 # for_statement : 0.0032 for_statement_speed_up : 0.0023 for_statement_list_comprehension : 0.0021 # for_statement : 0.0302 for_statement_speed_up : 0.0259 for_statement_list_comprehension : 0.0236 # for_statement : 0.3118 for_statement_speed_up : 0.2416 for_statement_list_comprehension : 0.2240 # for_statement : 2.9900 for_statement_speed_up : 2.4156 for_statement_list_comprehension : 2.1501 $
◯ なんで速いの？
メソッド呼び出しを避けることで、リスト内包表記に近づいています。リスト内包表記が速いことの要因の１つです。
実は、元のコードのオーバーヘッドの大半は、append 属性の参照にあったという事になります。
Pythonの内包表記はなぜ速い？ - DSAS開発者の部屋
なお上記のブログ「DSAS開発者の部屋」は、Python のコア開発者の一人である稲田直哉様が書かれています。上記の記事では、バイトコードを比較しながらリスト内包表記と for 文を比較、解説してくれている、大変ありがたい記事になります。
6. リストとイテレータの速度の比較
"もしメモリが気にならないなら" 専用のイテレータやらジェネレータやらは実装せずに、リストに素直に全部要素を叩き込んでしまってから for 文を回した方が速そう。
リストと木の２つのデータ構造について 1. リストに全ての要素を叩き込んだもの list_iterator, 2. イテレータ iterator, ジェネレータ generator の３つについて比較を行いました。
6.1. リスト
ジェネレータがイテレータよりも速い。
$ python 6_1_list.py # list_iterator : 0.0000 iterator : 0.0005 generator : 0.0002 # list_iterator : 0.0002 iterator : 0.0055 generator : 0.0022 # list_iterator : 0.0015 iterator : 0.0453 generator : 0.0178 # list_iterator : 0.0177 iterator : 0.4271 generator : 0.1786 $
このコードの説明は、ここで書きました。
6.2. 木（二分探索木）
木は、n が小さいうちはイテレータよりもジェネレータが速いけど n が大きくなるにつれて、イテレータとジェネレータは逆転します。
$ 6_2_binary_serach_tree.py # list_iterator : 0.0000 iterator : 0.0000 generator : 0.0000 # list_iterator : 0.0001 iterator : 0.0002 generator : 0.0001 # list_iterator : 0.0007 iterator : 0.0021 generator : 0.0014 # list_iterator : 0.0064 iterator : 0.0198 generator : 0.0150 # list_iterator : 0.0942 iterator : 0.2131 generator : 0.1922 # list_iterator : 1.2084 iterator : 2.4697 generator : 2.3491 # list_iterator : 16.5732 iterator : 24.2149 generator : 27.5993 $
もう少しよく見てみると n を大きくするにつれて iterator に比べて list_iterator, generator の速度が遅くなってきます。
これは再帰を使っているからだと思われます。
iterator も同じアルゴリズムを使っていますが、再帰のスタックは Python の list で自前で実装しています。
このコードの説明は、ここで書きました。
7. if 文と 例外の速度の比較
たまにしか False にならない場合 ... 例外
例外を使えば、条件分岐でかかる処理を Python ではなく CPython 側で実行させることができます。
さらに言えば Python が実行されているとき、裏側で CPython は、例外が発生するか条件判定を行なっています。
CPython のコードを読むと山のような条件判定のコードを読むことになります。 つまり例外というのは CPython が行なってくれた条件判定を利用することです。
もし、例外は生じてしまうと重いですが、例外が生じなければ 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.1. リストの比較
とりあえず、ここではリストを比較する処理を try-except, for-if, while-if の３つで比較しました。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_1_subtract_list.py # subtract_list_try_remove : 0.0024 subtract_list_for_if : 0.0061 subtract_list_while_if : 0.0130 # subtract_list_try_remove : 0.0011 subtract_list_for_if : 0.0029 subtract_list_while_if : 0.0068 # subtract_list_try_remove : 0.1789 subtract_list_for_if : 0.6620 subtract_list_while_if : 1.3739 $
なんで remove は速いの？
list.remove は C で実装されているから。
CPython のコードを覗いてみた - Python の list.remove メソッド
リストの走査→比較→削除の一貫した操作を C で実行して速くしてるような感じです。反対に for や while を使ってしまうと、比較するために Python 側に取り出すことになり、操作が重くなります。
もちろん要素が存在しないと例外発生してしまいますが、感覚的には if 文内で行われる条件判定のための型推論を伴う四則演算が例のごとく重くて、例外が、ちょっとやそっと発生したくらいでは問題にならないような感じかなと思っています。
簡単に言えば、最初から提供されている神々が書いてくれた組み込みの関数を使った方が速いということですね。
なるべく自分で Python のコードを書かずに CPython に処理をしてもらうようにするようなイメージです。
7.2. イテレータ
シーケンスを逆順するイテレータの __next__ メソッドを、条件分岐と例外でそれぞれ実装しました。 このようなケースでは例外の方が速そうです。
def next_condition(self): self._index -= 1 if self._index >= - len(self._sequence): return self._sequence[self._index] else: raise StopIteration
def next_exception(self): self._index -= 1 try: return self._sequence[self._index] except IndexError: raise StopIteration
$ python 7_2_condition_exception.py # next_condition : 0.0000 next_exception : 0.0000 # next_condition : 0.0000 next_exception : 0.0000 # next_condition : 0.0001 next_exception : 0.0001 # next_condition : 0.0007 next_exception : 0.0005 # next_condition : 0.0076 next_exception : 0.0046 # next_condition : 0.0683 next_exception : 0.0447 # next_condition : 0.7019 next_exception : 0.4431 $
C で書かれたモジュールと
Python で書かれたモジュールについて
上記のリストを比較するコードで C で組まれた remove を活用したように
C で組まれたモジュールを活用すると速い感じがします。
itertools などの C で書かれたモジュールは速い感じがします。
cpython/Modules/
copy などの Python で書かれたモジュールは遅い感じがします。
ただ、遅いとは言えども自分で０から組むよりはきっと、速いかなと。
cpython/Lib/
同じ機能を提供しているものがないので
両者を単純に比較することはできませんが...
また、同じモジュールであっても Python 側で実装されていたり、
C 側実装されていたりするそうです。
collections.OrderedDict は Python 側で実装された型であるのに対して、同じモジュールにある collections.defaultdict は C 言語側で実装されている型です。このことは実際に PyPy で相当数の問題を引き起こしています。これらの違いが目立たない類似の API を実現するため、できるだけオリジナルの型を模倣する必要があるからです。
Revenge of the Types: 型の復讐
請注意
ここで書かれていることを気にして、コーディングしない方が望ましいです。ここで書かれていることは Python を高速化するための tips というよりも Python の動作とか性質が、だいたいどんなものかを理解するためのものと捉えていただけると嬉しいです。
もし処理速度を本当に向上させたい場合は... 次のようなものが、基本的な流れかなと思います。
- cProfile などを使い遅い場所を特定する。
- より良いアルゴリズム、データ構造を検討、採用する。
- Numba など外部ライブラリの利用する。
- PyPy を使う。
- 処理を並列化する。
- Cython を使って CPython を拡張する（C 言語で書き直したりする）
- Go などの全く別言語に書き換える。
特に Python で書くときは、高速化よりも可読性を重視した方が望ましいと感じます。理由は２つあります。
１つ目は Python は、コードをささっと書き上げることを目的にしているから。実行時間を速くすることを目的にしていません。パフォーマンスよりも可読性を優先した例としては、型にとらわれず自由にプログラミングできるように静的型付けではなく動的型付けを採用したこと、自由にオブジェクトの属性を追加できるようにしたため属性参照のコストが重くなっていること。
私にとって重要なのは、どうすれば生産性の高い仕事ができるかなのです。 ”生産性”とは何か。私の場合、分析は1回しか行いません（異なるアイデアのテストやデバッギングは別です）。 ある特定のコードを24時間実行することもありません。私はエンドユーザのためのソフトウェアアプリを開発していません。
私は”生産性”を定量化する際、(1)アイデアをコードで書き出す時にかかった時間、(2)デバッギングにかかった時間、 (3)実行にかかった時間の合計時間を想定します。 私にとって”高い生産性”は”結果を出すまでにかかった時間”を意味します。長年の経験から、自分にはPythonが合っていることが分かりました。
「塩を取って」
「だからさ……」
「分かってる。どんな調味料でも渡せるシステムを開発してるんだ。」
「20分も待ってるんだけど。」
「長い目で見たら役に立つから。」
それに、ここで書かれていることを利用しても、部分的にはいくらか速くできますが、全体としてはそんなに速くなりません。Python はもともと遅い言語です。パフォーマンスよりも可読性を重視して設計されています。その遅い言語を、可読性を損なってまでして、ちょっと速くしても得られるものは多くはありません。例えば、メソッドを変数に代入して実行なんてしてたら可読性がひどく損なわれます。こうなってきたら一体、何のために Python を使っているのか、わからなくなってきます。
Python 2 から 3 にかけて、若干実行速度が遅くなったらしいです。それくらい可読性を優先しています。リンク先の例では int と long が統合されたことが影響しているかなと思っています。
しかし、以下の違いは Python 3 は 一般に Python 2 より遅くなるという事実からきています。
Python 2 と 3 の速度の違いについてのメモ - Python 2.7.x と 3.x の決定的な違いを例とともに
同じプログラムを別の C 言語などに書き換えれば何倍も早くなります。Python の高速化と書いてあっても、他のサイトや書籍 "ハイパフォーマンス Python" では、外部ライブラリや別言語への書き換えを書いてるのは、そのためだと思います。最初は、なんで Python の高速化なのに C 言語とか Fortran とか別言語の話をしてるんだろう？と疑問に思っていましたが（また髪の話してる... みたいな感じで）。
100万倍速いプログラムを書く - Qiita
２つ目は 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
高速化のためにC++を使うべきかは、サーバ代（ネットワークを除く）と人件費のどちらが高いかなだけで、大抵の会社は人件費の方が高いので（Goにすることさえ）高速化自体には価値がなく開発効率こそが重要なだけかと思う。開発者数に対するユーザ数が多いGoogleとかだとC++の効果は絶大。 https://t.co/pEs4XjxNG4
— いもす (@imos) October 25, 2017
一番需要あるのはDB設計とクエリ高速化で、ついでキャッシュ設計なので、バイナリに近いレベルの高速化にたどり着くプレーヤーが国内にほぼない…
— human eslint --fix (@mizchi) July 11, 2018
その他の速度の比較 list の扱い
いままで見てきた通り Python は思わぬ処理が重かったりします。以下の記事は Python の特徴、特に list の扱いについて勉強になります。
あなたのPythonを爆速にする７つの方法
続・あなたのPythonを爆速にする７つの方
この記事では CPython の list の実装を説明しています。なぜ、リストの処理が重いのか、軽いのかを調べるときに便利かなと思って見てます。まだ、ちゃんと読んではいません。
Python のソースを読んでみる - Qiita