python - Eratosthenes 筛法速度差异

Question

为什么第一个比第二个快那么多？我知道将素数存储为 1s 和 0s 更简单，但速度增加是荒谬的。最后，它仍然要遍历一个 200 万项长的列表，这怎么可能在 1 秒内完成编译呢？

def prime_sieve(limit):
    primes = [1 for x in xrange(limit)]
    primes[0] = 0
    primes[1] = 0
    imax = int(math.sqrt(limit) + 1)

    i = 2
    while (i < imax):
        j = i + i
        while j < limit:
            primes[j] = 0
            j += i
        while True:
            i += 1
            if primes[i] == 1:
                break
    return primes

s = prime_sieve(2000000)
print(sum(i for i in xrange(len(s)) if s[i] == 1))
-----------------------------------------------------------
def sieve(max):
    primes = range(2, max+1)
    for i in primes:
        j = 2
        while i * j <= primes[-1]:
            if i * j in primes:
                primes.remove(i*j)
                j += 1
    return primes

count = 0
for x in sieve(2000000):
    count += x
print count

Answer 1

因为当你删除你不能使用的东西时 direct addressing了。直接寻址是埃拉托色尼筛法速度的关键(类似于 integer sorting 相对于基于比较的排序的速度优势)。

在您的第一个代码中，primes[j] = 0是一个 O(1) 操作。但在第二个中，primes.remove(i*j)是一个 O(n) 操作(根据 this )。

您还开始枚举 i 的倍数在2*i而不是 i^2 .与上述相比，问题要小得多。

要正确比较算法速度，总是比较empirical orders of growth 。这里是the results :

# First code:
# --i+i--                                 # --i*i--
#   N       n    time-space   ~ n^        #    N     n     time-space   ~ n^
#  10k     1229  0.02s-7.9M               #
#  2mln  148933  1.13s-7.9M               #  2mln  148933  1.12s-7.9M  
#  4mln  283146  2.30s-7.9M  n^1.11       #  4mln  283146  2.25s-7.9M  n^1.09
#  8mln  539777  4.58s-7.9M  n^1.07       #  8mln  539777  4.38s-7.9M  n^1.03
# 16mln 1031130  9.12s-7.9M  n^1.06       # 16mln 1031130  8.82s-7.9M  n^1.08

# Second code:
# --j=2--                                 # --j=i--
#   5k      669  0.35s-7.9M               #   5k      669  0.28s-7.9M
#  10k     1229  1.37s-7.9M  n^2.24       #  10k     1229  1.16s-7.9M  n^2.34
#  20k     2262  5.21s-7.9M  n^2.19       #  20k     2262  4.66s-7.9M  n^2.28
#  30k     3245 11.76s-7.9M  n^2.26       #  30k     3245 11.24s-7.9M  n^2.44

N是上限，n - 它下面的素数。指数当然是近似值，它们的增量没有被测量，但它们确实给了我们一个大概的画面。二次(或更糟)算法肯定与线性算法有很大不同。