| 項番 | 分類 | 低レベルな書き方 | 高レベルな書き方 |
|---|---|---|---|
| 1 | 順次 | 速 リテラルの参照 | 遅 変数の参照 |
| 2 | 順次 | 速 変数の参照 | 遅 属性の参照 |
| 3 | 順次 | 速 ベタ書き | 遅 関数 |
| 4 | 反復 | 遅 while 文 | 速 for 文 |
| 5 | 反復 | 遅 for 文 | 速 list 内包表記 |
| 6 | 反復 | 謎 iterator | 謎 generator |
| 7 | 分岐 | 謎 if 文 | 謎 例外 |
表は、感覚的に把握するためのもので、ごく大雑把に記載しています。
実際のコードと合わせて、ふーんと読み流していただけると嬉しいです。
◯ ポイント
必ずしも早くなるわけではなさそう
反復のカテゴリは低レベルに書いても、遅かったです。これは Python は 1 + 1 とかの四則演算が重すぎて Python レベルで低レベルなコードを書いても速くならない感じがします。
ここで取り扱うこと
• Python の構文を使った処理速度の比較
• 最初から入ってる組込関数、型、モジュールを使った処理速度の比較
ここで取り扱わないこと
• NumPy, Numba など外部ライブラリの利用
• 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
２倍くらい速かったりする。
$ 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 つのリテラルとして扱っていました。
こういうのを 定数畳み込み と言うらしいです。
>>> 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
>>>
◯ まとめ
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 で割り算をするときの切り上げと切り捨て
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 より速い。
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 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_2_sieve_of_eratosthenes.py primes_for : 1.0813 primes_while : 1.2748 $
◯ 考察
エラトステネスの篩自体は速いアルゴリズムらしいです。
とりあえずエラトステネスのふるいの方が速いことを理解しておいてください。
エラトステネスのふるいとその計算量
エラトステネスの篩そのもののの高速化についてはこちらで検討しました。
Python でエラトステネスの篩
4.3. 素因数分解
while 文が速い。
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_3_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 $
◯ 考察
4.1, 4.2 の結果を見ると 4.3 も for 文の方速いのだろうと思っていましたが、結果は違いました。if 文を使って途中で break するようなケースでは for 文よりも while 文の方がたまに速かったりします。
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; }
xrange と range
range オブジェクトのメモリサイズを表示させているのは、何故か n が大きくなると for 文の動作が遅くなるので、range が悪さをして大量のメモリを確保してるのかなと思ったからです。
しかし、実際には Python 3 では range は Python 2 の xrange とほぼ同じ動作をするので、大量にメモリを使って動作が遅くなってみるみたいなことはなさそうでした。
xrange - Python 2.7.x と 3.x の決定的な違いを例とともに
Why is there no xrange function in Python3?
4.4. 思ったこと
for 文は思いのほか速い
NumPy などの数値計算を行う人たちにとって、一般に Python の for 文は遅いとされます。代わりに NumPy が提供するベクター演算を使用するように書かれます。だから 「for 文は遅い」と言われます。
そのため、自分は for 文よりも while 文の方が速いのかなと思っていたのですが、実際にはより低レベルに記述した while 文よりも for 文の方が速いことがわかりました。
理由は for 文そのものが遅いというよりも、四則演算の、さらに四則演算そのものではなく、型推論が尋常ないコストを食っています。リンク先では Cython を使って１つ１つ型定義をして徐々に高速化を計り、型推論がどれだけ重い処理であるかを示してくれています。
Python の for 文は遅い？
言い換えれば、「for 文が遅いのではなく、Python が遅い言語だ。型推論が重いから。」と言い換えるとわかりやすいかもしれません。Python では、属性参照、関数呼び出しなんかも地味に重い処理ではありますが。
5. for 文と list 内包表記の速度の比較
上記 4.1 の結果でもそうでしたが、
一般的に list 内包表記の方が速いそうです。
Pythonのリスト内包表記の速度
Pythonの内包表記はなぜ速い？
Pythonのリスト内包表記をdisる
6. イテレータとジェネレータの速度の比較
わからない。ただ、もしメモリが気にならないなら、専用のイテレータやらジェネレータやらは実装せずに、リストに素直に全部要素を叩き込んでしまってから for 文を回した方が速そう。
リストと木の２つのデータ構造について 1. リストに全ての要素を叩き込んだもの list_iterator, 2. イテレータ iterator, ジェネレータ generator の３つについて比較を行いました。
6.1. リスト
リストのイテレータは、ほとんど違いがない。
$ python 6_1_list.py ---- n = 1000 list_iterator : 0.0002 iterator : 0.0002 generator : 0.0002 ---- n = 10000 list_iterator : 0.0016 iterator : 0.0017 generator : 0.0016 ---- n = 100000 list_iterator : 0.0193 iterator : 0.0229 generator : 0.0216 ---- n = 1000000 list_iterator : 0.4573 iterator : 0.4228 generator : 0.4360 $
6.2. 木（二分探索木）
木は、n が小さいうちはイテレータよりもジェネレータが速いけど n が大きくなるにつれて、イテレータとジェネレータは逆転する。イテレータを使うようよりも、深さ優先探索で一度全ての要素を取り出した方が速い（list_iterator）。メモリが気にならないなら、一度全てリストに取り出してしまうのがいいかもしれない。
$ 6_2_binary_serach_tree.py ---- n = 1000 list_iterator : 0.0062 iterator : 0.0197 generator : 0.0125 ---- n = 10000 list_iterator : 0.0629 iterator : 0.1815 generator : 0.1410 ---- n = 100000 list_iterator : 1.0066 iterator : 2.1797 generator : 1.9408 ---- n = 1000000 list_iterator : 12.1457 iterator : 21.7287 generator : 22.2123 ---- n = 10000000 list_iterator : 161.6515 iterator : 232.5278 generator : 282.1596 $
ここのコードの詳細はこちらに書きました。
Python のイテレータとは
7. if 文と 例外の速度の比較
たまにしか False にならない場合 ... 例外
例外は、処理が重いですが、もし例外が発生しなければ条件分岐でかかる計算を省略することができます。例外を使った方が速い例を２つ見てみたいと思います。
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_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 関数を呼び出すことは、１度のイテレーションで２度の呼び出しをしないといけない。２つの呼び出しは、例外の検査を含めた１度の呼び出しよりも重い処理である。特に実行速度が重要な 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 で書かれたモジュールは遅い感じがします。
ただ、遅いとは言えども自分で０から組むよりはきっと、速いかなと。
cpython/Lib/
同じ機能を提供しているものがないので
両者を単純に比較することはできませんが...
また、同じモジュールであっても Python 側で実装されていたり、
C 側実装されていたりするそうです。
collections.OrderedDict は Python 側で実装された型であるのに対して、同じモジュールにある collections.defaultdict は C 言語側で実装されている型です。このことは実際に PyPy で相当数の問題を引き起こしています。これらの違いが目立たない類似の API を実現するため、できるだけオリジナルの型を模倣する必要があるからです。
Revenge of the Types: 型の復讐
請注意
ここで書かれていることを気にして、コーディングしない方が望ましいです。Python を高速化するための tips というよりも Python の動作とか性質が、だいたいどんなものかを理解するための記事と捉えていただけると嬉しいです。お前、今さらそれを言うのかよって感じですが...。
特に 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
もし、実行速度を優先する場合は、より良いアルゴリズム、データ構造の採用、あるいは、ここでは取り扱わない NumPy など外部ライブラリの利用、Cython を使って Python のモジュールを C 言語で書き直したりすることを検討してください。
高速化のためにC++を使うべきかは、サーバ代（ネットワークを除く）と人件費のどちらが高いかなだけで、大抵の会社は人件費の方が高いので（Goにすることさえ）高速化自体には価値がなく開発効率こそが重要なだけかと思う。開発者数に対するユーザ数が多いGoogleとかだとC++の効果は絶大。 https://t.co/pEs4XjxNG4
— いもす (@imos) October 25, 2017
その他の速度の比較 list の扱い
いままで見てきた通り Python は思わぬ処理が重かったりします。以下の記事は Python の特徴、特に list の扱いについて勉強になります。
あなたのPythonを爆速にする７つの方法 |
続・あなたのPythonを爆速にする７つの方 |
この記事では CPython の list の実装を説明しています。なぜ、リストの処理が重いのか、軽いのかを調べるときに便利かなと思って見てます。まだ、ちゃんと読んではいません。
Python のソースを読んでみる | Qiita