Pythonの高速化

はじめに

Python コードの高速化のアプローチ

Pythonの高速な書き方のことだと思って, うっかり見てしまったため, 気になって仕方がないのです. 競技プログラミングは知らないのですが, エレガントなアルゴリズムを考えて問題を解く競技だと思っていたのですが, 違うのですね.

アルゴリズムを改良して高速化することを考えます. そのためPythonはほとんど関係ないです, タイトル詐欺です. ほとんどの理由はまとめにあります.
多くの環境で速くならないと意味がないので環境は書きません.

ベースライン

import math

def is_prime(x : int) -> bool:
    if x <= 1:
        return False
    if x % 2 == 0:
        return x == 2
    upper = math.floor(math.sqrt(x)) + 1
    for i in range(3, upper, 2):
        if x % i == 0:
            return False
    return True

def minimum_prime_number(x : int):
    maxx = 10 ** 14 + 32
    for i in range(x, maxx):
        if is_prime(i):
            return i

if __name__ == '__main__':
    result = minimum_prime_number(100000000000000)
    print(result)

100000000000031
0.504 seconds

ミラー–ラビン素数判定法

確率的判定法を追加しますが, ほとんど変わらず.

def miller_rabin_test(n : int) -> bool:
    k = 50
    if n <= 1:
        return False
    if n % 2 == 0:
        return n == 2
    if n % 3 == 0:
        return n == 3
    if n % 5 == 0:
        return n == 5

    s, d = 0, n-1
    while d % 2 == 0:
        s, d = s+1, d>>1
    while 0<k:
        k = k-1
        a = random.randint(1, n-1)
        t, y = d, pow(a, d, n)
        while t != n-1 and y != 1 and y != n-1:
            y = pow(y, 2, n)
            t <<= 1
        if y != n-1 and t % 2 == 0:
            return False
    return True

def is_prime(x : int) -> bool:
    if False == miller_rabin_test(x):
        return False
    upper = math.floor(math.sqrt(x)) + 1
    for i in range(3, upper, 2):
        if x % i == 0:
            return False
    return True

100000000000031
0.501 seconds

3の倍数をスキップする

計算コストの方が上回ってしまった.

def is_prime(x : int) -> bool:
    if False == miller_rabin_test(x):
        return False
    upper = math.floor(math.sqrt(x))
    count = 5
    step = 4
    while count<=upper:
        if x % count == 0:
            return False
        step = 6 - step
        count += step
    return True

100000000000031
0.569 seconds

まとめ

そろそろ飽きてきたため終了です. C++を呼び出してしまったら, それはもうC++で書けということなのでやりません.
Pythonの試行錯誤について, 次の項以外では整数のサイズが可変なことが遅くなる一因なのかと推測しています.

試行錯誤 ループ

"インタープリタはループが遅い"は, 2021年でも有効な知見と思われます. MATLABなどもそうです. iteratorとgeneratorを試しています.

• iterator: 検索した例を基に作成しましたが, 1秒以上の計算時間で遅いです. 停止判定を例外で行うことが, 設計ミスだと思います. 参考にした例が悪いのかな.
• generator: 0.6秒程度でやはり遅いです. whileに比べて多くの処理が必要なのは仕方がないです. 利便性とのトレードオフです.