Eratosthenes的速度差異

爲什麼第一個比第二個快得多？我認爲將素數存儲爲1和0比較簡單，但速度增加是荒謬的。最後，它仍然會經歷一個200萬個項目的列表，那麼它在編譯時需要多長時間才能完成呢？Eratosthenes的速度差異

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

來源

2014-01-20 jabelk

這個問題似乎是脫離主題，因爲它屬於http://codereview.stackexchange.com – jonrsharpe

在兩個最外層的循環中添加一個'print i'併爲一些小輸入運行這兩個函數，比如'100'。看看在兩個功能中測試的數字！ –

代碼中存在錯誤（除了函數'sieve'內的明顯錯誤縮進）：從底部開始的第6行應該在與其上面的'if'相同的級別上縮進回去。 –

因爲當你刪除的東西，你不能再使用direct addressing。直接尋址是Eratosthenes篩選速度的關鍵（類似於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 - 數字低於它的素數。指數當然是近似的，他們的增量沒有被測量，但它們給我們一個總體的圖景。二次（或更差）算法肯定與線性算法有很大不同。

來源

2014-01-20 19:25:50

Eratosthenes的速度差異

回答

相關問題