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

Question

为了好玩，我决定用ruby编写eratosthenes的筛子。只是为了好玩，因为我知道有一个库函数。此外，我认为它会很快。但我发现它不是，至少在我的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

prime库Prime.each(1_000_000).to_a生成1_000_000以下的所有质数。

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

Answer 2

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

b)更重要的是，MRI的库实现也是in Ruby的，而不是C。