Python を高速化したい


表. 比較したもの一覧
項番 分類 低レベルな書き方 高レベルな書き方
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. リテラルの参照と変数の参照


リテラルの参照の方が速い。ただし、list を除く。

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_1_access_comparison.py

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 次元リストと 2 次元リストを 1 次元リストで表現したものの参照速度を比較してみます。

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

2次元リストを1次元で表現するのは、競技プログラミングのコードを見ていたらでてきたコードです。C などでは1次元リストで表現した方が速いそうです。Python では、どうでしょうか。

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

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 次元リストを使うよりも1次元リストを 2 次元のリストとして表現した方が 2 倍早い。

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

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


2. 変数 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次元リストを1次元リストで表現すると、リテラルを使用した場合の結果と逆転してしまうほど、参照速度が遅くなってしまったのでしょうか?言い換えれば、なぜ 1500*3000+1500row*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 が大きかった時の対処法の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 文の速度の比較


基本的には for 文の方が速そう


4.1....list の初期化
4.2....素数のリスト
4.3....素因数分解

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 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 を使って1つ1つ型定義をして徐々に高速化を計り、型推論がどれだけ重い処理であるかを示してくれています。
Python の for 文は遅い?

言い換えれば、「for 文が遅いのではなく、Python が遅い言語だ。型推論が重いから。」と言い換えるとわかりやすいかもしれません。Python では、属性参照、関数呼び出しなんかも地味に重い処理ではありますが。

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


list 内包表記の方が速い。


上記 4.1 の結果でもそうでしたが、
一般的に list 内包表記の方が速いそうです。
Pythonのリスト内包表記の速度
Pythonの内包表記はなぜ速い?
Pythonのリスト内包表記をdisる



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


わからない

わからない。ただ、もしメモリが気にならないなら、専用のイテレータやらジェネレータやらは実装せずに、リストに素直に全部要素を叩き込んでしまってから for 文を回した方が速そう。

リストと木の2つのデータ構造について 1. リストに全ての要素を叩き込んだもの list_iterator, 2. イテレータ iterator, ジェネレータ generator の3つについて比較を行いました。

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 になる場合 ... if 文
たまにしか False にならない場合 ... 例外


例外は、処理が重いですが、もし例外が発生しなければ条件分岐でかかる計算を省略することができます。例外を使った方が速い例を2つ見てみたいと思います。


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 の動作とか性質が、だいたいどんなものかを理解するための記事と捉えていただけると嬉しいです。お前、今さらそれを言うのかよって感じですが...。

特に Python で書くときは、高速化よりも可読性を重視した方が望ましいと感じます。理由は2つあります。

1つ目は ここで書かれていることを利用しても、部分的には何倍も早くできますが、全体としてはそんなに速くなりません。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

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


もし、実行速度を優先する場合は、より良いアルゴリズム、データ構造の採用、あるいは、ここでは取り扱わない NumPy など外部ライブラリの利用、Cython を使って Python のモジュールを C 言語で書き直したりすることを検討してください。

その他の速度の比較 list の扱い

いままで見てきた通り Python は思わぬ処理が重かったりします。以下の記事は Python の特徴、特に list の扱いについて勉強になります。
あなたのPythonを爆速にする7つの方法 |
続・あなたのPythonを爆速にする7つの方 |

この記事では CPython の list の実装を説明しています。なぜ、リストの処理が重いのか、軽いのかを調べるときに便利かなと思って見てます。まだ、ちゃんと読んではいません。
Python のソースを読んでみる | Qiita