爲什麼這個算法更糟？

Question

在Wikipedia這是給定一個算法來生成素數：

def eratosthenes_sieve(n): 
    # Create a candidate list within which non-primes will be 
    # marked as None; only candidates below sqrt(n) need be checked. 
    candidates = [i for i in range(n + 1)] 
    fin = int(n ** 0.5) 

    # Loop over the candidates, marking out each multiple. 
    for i in range(2, fin + 1): 
     if not candidates[i]: 
      continue 

     candidates[i + i::i] = [None] * (n // i - 1) 

    # Filter out non-primes and return the list. 
    return [i for i in candidates[2:] if i] 

我改變了算法略有下降。

def eratosthenes_sieve(n): 
    # Create a candidate list within which non-primes will be 
    # marked as None; only candidates below sqrt(n) need be checked. 
    candidates = [i for i in range(n + 1)] 
    fin = int(n ** 0.5) 

    # Loop over the candidates, marking out each multiple. 

    candidates[4::2] = [None] * (n // 2 - 1) 

    for i in range(3, fin + 1, 2): 
     if not candidates[i]: 
      continue 

     candidates[i + i::i] = [None] * (n // i - 1) 

    # Filter out non-primes and return the list. 
    return [i for i in candidates[2:] if i] 

我首先標出了2的所有倍數，然後我只考慮奇數。當我計算兩種算法（嘗試40.000.000）時，第一個算法總是更好（儘管非常輕微）。我不明白爲什麼。有人可以解釋一下嗎？

P.S .:當我嘗試100.000.000時，我的電腦死機。這是爲什麼？我有Core Duo E8500,4GB內存，Windows 7 Pro 64位。

更新1：這是Python 3的

更新2：這是我的計時：

start = time.time() 
a = eratosthenes_sieve(40000000) 
end = time.time() 
print(end - start) 

UPDATE：在寶貴的意見（特別是nightcracker和溫斯頓·尤爾特）我設法代碼我首先打算：

def eratosthenes_sieve(n): 
    # Create a candidate list within which non-primes will be 
    # marked as None; only c below sqrt(n) need be checked. 
    c = [i for i in range(3, n + 1, 2)] 
    fin = int(n ** 0.5) // 2 

    # Loop over the c, marking out each multiple. 

    for i in range(fin): 
     if not c[i]: 
      continue 

     c[c[i] + i::c[i]] = [None] * ((n // c[i]) - (n // (2 * c[i])) - 1) 

    # Filter out non-primes and return the list. 
    return [2] + [i for i in c if i] 

該算法改進了原來的算法（在頂部提到）由（通常）50％。 （當然，比自動提到的算法更糟糕）。

對Python大師的一個問題：是否有更多的Pythonic方法來以更「功能性」的方式表達最後一個代碼？

更新2：我仍然無法解碼由nightcracker提到的算法。我想我太傻了。

Answer 1

問題是，它爲什麼會更快？在這兩個例子中，你都過濾了兩個數的倍數，這很難。無論您是硬編碼candidates[4::2] = [None] * (n // 2 - 1)還是在for i in range(2, fin + 1):的第一個循環中執行它都無關緊要。

如果你有興趣的埃拉托色尼的優化篩，在這裏你去：

def primesbelow(N): 
    # https://stackoverflow.com/questions/2068372/fastest-way-to-list-all-primes-below-n-in-python/3035188#3035188 
    #""" Input N>=6, Returns a list of primes, 2 <= p < N """ 
    correction = N % 6 > 1 
    N = (N, N-1, N+4, N+3, N+2, N+1)[N%6] 
    sieve = [True] * (N // 3) 
    sieve[0] = False 
    for i in range(int(N ** .5) // 3 + 1): 
     if sieve[i]: 
      k = (3 * i + 1) | 1 
      sieve[k*k // 3::2*k] = [False] * ((N//6 - (k*k)//6 - 1)//k + 1) 
      sieve[(k*k + 4*k - 2*k*(i%2)) // 3::2*k] = [False] * ((N // 6 - (k*k + 4*k - 2*k*(i%2))//6 - 1) // k + 1) 
    return [2, 3] + [(3 * i + 1) | 1 for i in range(1, N//3 - correction) if sieve[i]] 

說明這裏：Porting optimized Sieve of Eratosthenes from Python to C++

最初來源是here，但沒有解釋。簡而言之，primesieve會跳過2和3的倍數，並使用一些黑客來利用快速的Python分配。

Answer 2

它可能會稍微慢一些，因爲您正在執行額外的設置以完成第一種情況下完成的任務（標記爲2的倍數）。設置時間可能是你看到的，如果它和你所說的一樣輕微

Answer 3

你的額外步驟是不必要的，並且實際上會遍歷整個集合n一旦這樣做'擺脫evens的操作，而不是僅僅在n^1/2。

Answer 4

您不會節省很多時間避免這些問題。大多數的算法中的計算時間花在了這一點：

candidates[i + i::i] = [None] * (n // i - 1) 

這行導致對計算機的部分很多動作。只要有問題的數字是偶數，就不會像循環保存if語句那樣運行。因此，爲偶數運行循環的時間非常小。因此，消除這些輪甚至不會對循環的時間產生重大變化。這就是爲什麼你的方法不是很快。

當python生成範圍數字時，它使用公式：start + index * step。與你的情況相比，乘以2會比原來的情況稍微貴一點。

有一個很長的功能也可能有一個小的開銷。

這些都不是真正重大的速度問題，但它們覆蓋了您的版本帶來的非常小的好處。