Photo by Marius Masalar

4.3. エラトステネスの篩

for 文が速い

エラトステネスの篩は、n 以下の素数を求めるアルゴリズムです。 エラトステネスの篩は、速いアルゴリズムらしいです。

とりあえずエラトステネスのふるいの方が速いことを理解しておいてください。
エラトステネスのふるいとその計算量 (opens new window)

エラトステネスの篩そのもののの高速化についてはこちらで検討しました。 ここでは純粋に for 文と while 文の比較を行います。

• Python でエラトステネスの篩 (opens new window)

4.3.1. 比較対象

比較対象は、次の通りです。

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]]

4.3.2. 測定結果

結果は以下の通りです。

# Case 0
# (10**0, )
primes_for                               :   0.0015 [msec]
primes_while                             :   0.0012 [msec]

# Case 1
# (10**1, )
primes_for                               :   0.0057 [msec]
primes_while                             :   0.0038 [msec]

# Case 2
# (10**2, )
primes_for                               :   0.0526 [msec]
primes_while                             :   0.0449 [msec]

# Case 3
# (10**3, )
primes_for                               :   0.7152 [msec]
primes_while                             :   0.7217 [msec]

# Case 4
# (10**4, )
primes_for                               :   8.6340 [msec]
primes_while                             :   9.7239 [msec]

# Case 5
# (10**5, )
primes_for                               : 100.9515 [msec]
primes_while                             : 121.3322 [msec]

# Case 6
# (10**6, )
primes_for                               : 1394.2373 [msec]
primes_while                             : 1741.9604 [msec]

4.3.3. 補足

なんで while 文は、遅かったのでしょうか？ while 文が遅かったのは index の更新 i = i + 1 という処理を自分で Python で書いてしまったからです。 for 文は C 言語で書かれた Python, CPython が i = i + 1 で計算を実行させています。

基本的には自分で Python で書くよりも、すでに C 言語で書かれた Python の機能を使った方が速くなります。 このあとリストの比較で list.remove メソッドを使う処理を紹介しますが、それも同じ考えです。