在Ruby中提高Eratosthenes篩的效率？

以下是我的Eratosthenes篩的實現，以找到達到上限參數的素數。在Ruby中提高Eratosthenes篩的效率？

目前，當我的參數是2,000,000時，我的代碼在大約2秒內完成。通過將數字設置爲零，然後進行壓縮而不是僅僅一步刪除這些數字，我發現我正在做一個額外的步驟。

我該如何去實施這個？你是否還有其他建議來提高我的代碼速度？

def sieve(upper) 
    i = 0 
    list = (2..upper).to_a 

    (2..Math.sqrt(upper)).each do |mult| 
    init = mult + i 
    (init..upper-1).step(mult) do |index| 
     list[index] = nil 
    end 
    i += 1 
    end 
    list.compact 
end

來源

2013-09-24 jchi2241

命令式代碼更快（while循環），但可讀性更差。 –

請參閱[本答案]（http://stackoverflow.com/a/18349336/849891）關於使用[經驗增長順序]（http://en.wikipedia.org/wiki/Analysis_of_algorithms#Eiricalirical_orders_of_growth）來評估運行節目的時間效率。一點測量沒有說什麼。它是「〜n^2.0」嗎？ '〜n^1.1'？ –

你應該問一下[代碼評論]（http://codereview.stackexchange.com）而不是Stack Overflow。這是爲了修理破碎的東西。 CR是爲了改善工作的東西。 –

您可以跳過mult不是素數的循環。

def sieve(upper) 
    i = 0 
    list = (2..upper).to_a 
    (2..Math.sqrt(upper)).each do |mult| 
    if list[i] #proceed only when mult is prime 
     init = mult + i 
     (init..upper-1).step(mult) do |index| 
     list[index] = nil 
     end 
    end 
    i += 1 
    end 
    list.compact 
end

這會在我的機器上將運行時間從1.9秒縮短到0.7秒。不過，我相信還有很多事情可以做。

來源

2013-09-25 03:24:34

下一個改進（儘管可能影響較小）是從mult^2開始，而不是從2 * mult開始。 :) ...並且先驗地跳過這些平鋪。 –

在Ruby中提高Eratosthenes篩的效率？

回答

相關問題