Photo by Simon Rae

4.4. 素因数分解

4.4. while 文の方が速い

4.4.1. 比較対象

ひたすら割り算をして、素因数分解を行います。

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


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):
    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

4.4.2. 測定結果

$ python3 4_2_list_deletion.py 

# Case 0
# (2**3 * 3**12 * 5**7, )
prime_decomposition_for                  :   0.0063 [msec]
prime_decomposition_for_itertools        :   0.0059 [msec]
prime_decomposition_while                :   0.0055 [msec]

# Case 1
# (3313**3 * 3323**3, )
prime_decomposition_for                  :   1.2006 [msec]
prime_decomposition_for_itertools        :   0.8567 [msec]
prime_decomposition_while                :   0.8782 [msec]

# Case 2
# (9973**5 * 9932**3 * 9901**2, )
prime_decomposition_for                  :   3.7044 [msec]
prime_decomposition_for_itertools        :   2.8366 [msec]
prime_decomposition_while                :   2.7728 [msec]

# Case 3
# (9973**5 * 9932**3 * 9901**2, )
prime_decomposition_for                  :   3.8798 [msec]
prime_decomposition_for_itertools        :   2.8413 [msec]
prime_decomposition_while                :   2.9867 [msec]

# Case 4
# (111869**3 * 128461**2, )
prime_decomposition_for                  :  46.1945 [msec]
prime_decomposition_for_itertools        :  35.9562 [msec]
prime_decomposition_while                :  34.8861 [msec]

# Case 5
# (111869**3 * 128461**2 * 188459**3, )
prime_decomposition_for                  :  72.6392 [msec]
prime_decomposition_for_itertools        :  51.8900 [msec]
prime_decomposition_while                :  51.4584 [msec]

4.4.3. 補足

4.1, 4.3 の結果を見ると 4.4 も for 文の方速いのだろうと思っていましたが、結果は違いました。 if 文を使って途中で break するようなケースでは for 文よりも while 文の方がたまに速かったりします。

じゃあ、どっちを選べばいいんだ？という話であります。 上の４つの結果 4.1, 4.2, 4.3, 4.4 を元に考えると、基本的には「きれいに書ける方で書く」と速くなると考えておけばいいかなと思います。

4.4.3.1. count の next と range の next

意地で for 文で速い書き方を探しました。itertools の count を使えば n が大きくなっても速度が遅くなりません。 なぜ、このような結果の違いが生じたのでしょうか？

それは range がループする度に、終了の条件判定を行なっているからです。count はループする度に、終了の条件判定を行なっていません。

例えば、極端な例では以下のようなケースでは、for 文の終了の条件判定で落とされてしまうようです。

Python / PyPyで2重ループするとき

for i in range(10**8):
for j in range(2):
pass

を

for j in range(2):
for i in range(10**8):
pass

に変えるだけで処理時間が3〜5倍ぐらい速くなるので、小さいループを外側にするのがいいよ。

（たまにこれで落ちる）

— きり (@kiri8128) April 27, 2019

CPython の実装を覗いてみて確認しました。for 文がループする度に range は longrangeiter_next が count は count_nextlong が呼び出されています。

C の int 型, long 型などの操作に比べて PyObject (opens new window) に対する操作は、 型を判定する処理が入るので、かなり重いはず です（後述）。 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;
}

4.4.3.2. 型を判定する処理が入るので、かなり重いはず

実は Python は、遅い言語だと言われます。 遅い原因は、変数や属性に型を明示しないからだそうです。 変数や属性に型が明示されていないため、型を判定する処理を付加する必要が生じます。

下記の記事では Cython を使って１つ１つ型定義をして徐々に高速化を計り、 型に関わる処理がどれだけ重い処理であるかを示してくれています。型の有無でここまで処理速度に違いが生じるのは、驚きでした。

この中の X*Y のような乗算処理では、次のような処理が行われる。

1. X が乗算をサポートしているかチェックする
2. X の乗算関数を取得する
3. Y が被乗数として適切なデータかチェックする
4. X の値と Y の値を取り出し、乗算する
5. 乗算の結果から新しい浮動小数点数オブジェクトを作成する

Python の for 文は遅い？ - atsuoishimoto's diary (opens new window)

実は 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を爆速にする７つの方法 (opens new window)
• 続・あなたのPythonを爆速にする７つの方 (opens new window)
• 8.7. array 効率のよい数値アレイ- Python 標準ライブラリ (opens new window)

4.4.4. まとめ

上手く説明できていないのですが、基本的には、きれいに書ける方で書けば速くなります。 そのため、速度の面で for 文かな while 文かなと、そんなに気にすることはないかなと思います。

また、自分で Python で書いた時に、もし同じ機能を Python が提供してくれているならば そっちを使った方が速いです。