Ruby の prime モジュールと自作のエラトステネスのふるいを benchmark で比較する

Ruby には prime モジュールが用意されています。prime モジュールを使うと簡単に素数を求めることができます。

ここでは、自作のエラトステネスのふるいのアルゴリズムを用いたプログラムと、prime モジュールでどれくらい速度に差がでるかを benchmark で計測してみたいと思います。

(追記) test_eratosthenes2 を追加しました。一番外側のループは sqrt(n) までで止める方法の場合、test_eratosthenes の n までループする方法よりかなり速くなりました。
zakuro9715 さん、ありがとうございます！

require 'prime'
require 'benchmark'

def test_prime(n)
  a = Prime.each(n).to_a
  a.size
end

def test_eratosthenes(n)
  primes = [2] # 素数リスト
  tab = [true] * n
  (3..n).step(2).each {|i|
    if tab[i]
      primes << i
      (i+i..n).step(i).each {|j|
        tab[j] = false
      }
    end
  }
  primes.size
end

def test_eratosthenes2(n) # test_eratosthenes より高速
  tab = [true] * n
  (3...(Math.sqrt(n).to_i)).step(2).each {|i|
    if tab[i]
      (i + i..n).step(i).each {|j|
        tab[j] = false
      }
    end
  }
  a = [2].concat (3..n).step(2).select {|i| tab[i] }
  a.size
end

N = 10_000_000
Benchmark.bm(12) do |x|
  x.report('prime') { test_prime(N) }
  x.report('eratosthenes')  { test_eratosthenes(N) }
  x.report('eratosthenes2') { test_eratosthenes2(N) }
end

実行結果です。

                   user     system      total        real
prime          1.330000   0.050000   1.380000 (  1.395049)
eratosthenes   2.730000   0.050000   2.780000 (  2.783461)
eratosthenes2  1.760000   0.030000   1.790000 (  1.803994)

環境

• OS X 10.10.2
• Ruby 2.2.2

参考

• Benchmarkモジュール