为什么素数的 stdlib 实现如此缓慢？

Question

为了好玩，我决定用红宝石编码伊拉托西筛子。只是为了好玩，因为我知道有一个库函数。而且，我认为它会很快。但我发现它并不是，至少在我的ruby 1.9.3中，我的上网本速度快了好几倍，甚至在c中也没有。为什么会这样呢。

库实现：

require 'prime'
primes = Prime.each(1_000_000).to_a
print primes.size
puts

我在红宝石:

sieve = Array.new(1_000_000, true)
sieve[0..1] = [false, false]
for number in 2...Math.sqrt(sieve.size)
  if sieve[number]
    for multiple in (number ** 2...sieve.size).step(number)
      sieve[multiple] = false
    end
  end
end

primes = []
for number in 2...1_000_000
  if sieve[number]
    primes << number
  end
end
print primes.size
puts

图书馆非常慢。

Answer 1

a） 在我的计算机上，库的执行时间为0.230秒，而您的实现时间平均为0.270秒。编辑：我执行的是MRI 2.2.0，而不是1.9.3。

b)更重要的是，MRI的库实现也是用Ruby，而不是c，Ruby库中并不是所有的函数都是用原生代码编写的。

Answer 2

< code>prime库< code>Prime.each(1_000_000)。to_a生成小于< code>1_000_000的所有质数。

您的方法实际上只生成< code>1_000_000的平方根以下的所有素数，即< code>1000。