每個比在Ruby中都慢嗎？

以下兩個功能，這些功能檢查，如果一個數是素數：與測試時每個比在Ruby中都慢嗎？

def prime1?(prime_candidate) 
    return true if [1, 2].include? prime_candidate 
    range = 2.upto(Math.sqrt(prime_candidate).ceil).to_a 
    i = 0 
    while i < range.count 
    return false if prime_candidate % range[i] == 0 
    range = range.reject { |j| j % range[i] == 0 } 
    end 
    true 
end 

def prime2?(prime_candidate) 
    return true if [1, 2].include? prime_candidate 
    range = 2.upto(Math.sqrt(prime_candidate).ceil).to_a 
    range.each do |i| 
    return false if prime_candidate % i == 0 
    range = range.reject { |j| j % i == 0 } 
    end 
    true 
end

產生以下benchamrking結果非常大的素數（5915587277）：

   user  system  total  real 
prime1: 2.500000 0.010000 2.510000 ( 2.499585) 
prime2: 20.700000 0.030000 20.730000 (20.717267)

這是爲什麼？是否因爲第二個功能range未被reject修改，所以each正在迭代原始長range？

來源

2014-10-09 Alex Popov

是的 - 迭代範圍不會改變你的每種情況。變量指向新值，但這並不重要，因爲您已經在原始值上調用了每個值 – 2014-10-09 08:46:05

小數nit - 1不是質數 – rohit89 2014-10-09 09:03:03

您是絕對正確的。 – 2014-10-09 09:15:04

當你做range=range.reject {..}，你不要修改父範圍（你不應該這樣做，因爲它會弄亂迭代 - 你需要reject!來做到這一點），而是構建一個臨時數組，只獲得在迭代結束時分配給父範圍變量。

中的each迭代在整個原始範圍內運行，而不是在循環結束之前只在塊中存在的縮短。

while版本修改原始數組，因此更快（順便說一句，你意識到我仍然是零，它的range.count改變（減少），而條件和拒絕再次遍歷整個數組 - 即使是開始的地方不可能有更多的非優質的拒絕）。

如果您改進代碼的邏輯，您將會得到更快的結果。這個數組操作是昂貴的，爲此，你甚至不需要一個數組：

def prime3?(prime_candidate) 
    return false if prime_candidate==1 
    return true if prime_candidate==2 
    range = 2..(Math.sqrt(prime_candidate).ceil) 
    range.all? {|x| prime_candidate % x !=0 } 
end #about 300× times as fast for your example as prime1? on my PC

來源

2014-10-09 10:29:19 PSkocik

每個比在Ruby中都慢嗎？

回答

相關問題