每个比在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中都慢吗？

回答

相关问题