メモ

• タイトル通り上限がありません。メモリが尽きるまでどこまででも求めます。
• 見つかった素数の個数に比例してメモリを消費。1,000,000個くらいは30MBほどでOK。
• mathn.rbより速い。数千個ほど生成すると、その差は歴然。
• 演算は、整数の加算のみを使用。
• 「上限を決めずに素数を生成(Ruby版)」と比べると、多少コードが冗長になる。
• 見た目はそんなに美しくない。
• Rubyじゃなくてもいいじゃん。(JavaScriptでも書いてみた)

samples$ time ruby -rprime -e 'g =
             Prime::PrimeGenerator.new();
             25.times{ g.next() };
             p g.primes.sort'
[2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53,
 59, 61, 67, 71, 73, 79, 83, 89, 97]
real    0m0.297s
user    0m0.062s
sys     0m0.155s

samples$ time ruby -rprime -e 'g =
             Prime::PrimeGenerator.new();
             999.times{ g.next() };
             puts(g.next())'
7919
real    0m0.265s
user    0m0.109s
sys     0m0.077s

samples$ time ruby -rprime -e 'g =
             Prime::PrimeGenerator.new();
             9999.times{ g.next() };
             puts(g.next())'
104729
real    0m0.531s
user    0m0.404s
sys     0m0.062s

samples$ time ruby -rprime -e 'g =
             Prime::PrimeGenerator.new();
             99999.times{ g.next() };
             puts(g.next())'
1299709
real    0m4.657s
user    0m4.421s
sys     0m0.125s

samples$ time ruby -rprime -e 'g =
             Prime::PrimeGenerator.new();
             999999.times{ g.next() };
             puts(g.next())'
15485863
real    2m2.594s
user    2m2.077s
sys     0m0.093s

module Prime
  extend Enumerable
  
  class PrimeGenerator
    def initialize()
      @h = {}
      @n = nil
    end

    def primes()
      @h.values().unshift(2)
    end

    def succ()
      if (@n.nil?)
        @n = 1
        return 2
      end
      n = @n
      while true
        m = n += 1
        if (b = @h[n])
          while(@h[m += b]); end
          @h[m] = b
          @h.delete(n)
        end
        m = n += 1
        if (b = @h[n])
          while(@h[m += b]); end
          @h[m] = b
          @h.delete(n)
        else
          while(@h[m += n]); end
          return @n = @h[m] = n
        end
      end
    end
    alias next succ
  end

  def self.each()
    g = PrimeGenerator.new()
    while (n = g.succ())
      yield(n)
    end
  end
end # module Prime

「エラトステネスのふるいをコンパクトにする方法」との比較

メソッド定義部分だけをprime_sumim.rbに保存して、"ruby -r prime_sumim.rb -e 'primes(15485863){|x| }'" として実行。1000000個目(15485863)までを求めると1m30sくらい。メモリ消費量も5MBほど。ちなみに、large_primesを使わない場合、60MBほどのメモリが必要だった。large_primesのアルゴリズムがかなり効いている。

「エラトステネスの篩の改良」との比較

ソースをそのままprime_nurse.rbへ保存して、"ruby -r prime_nurse.rb -e 'sieve(15485863)'" として実行。手元では1m20s-1m40sくらいで完了。消費メモリは約8MBほどだと思う。

YARVを使った場合

YARVを使うと次の通り。私のはあまり効果がないが、上記お二人のコードは劇的に速くなる。これは何が効いているのだろう？推測だけど、私のコードには最適化の余地が少なかったのかもしれない。

samples$ time ruby-yarv -r prime.rb -e '
                      g=Prime::PrimeGenerator.new();
                      1000000.times{ g.next() }'
real    1m28.703s
user    1m26.468s
sys     0m0.077s

samples$ time ruby-yarv -r prime_sumim.rb -e 'primes(15485863){|x|}'
real    0m34.437s
user    0m33.593s
sys     0m0.218s

samples$ time ruby-yarv -r prime_nurse.rb -e 'sieve(15485863){|x|}'
[:sieve, 1150739860.12438, 3, 7742930, 0]
real    0m34.844s
user    0m34.390s
sys     0m0.093s

そして、ruby-1.9とYARVを用いたmathn.rbとの比較。30000個の素数を生成して比較した。

samples$ ruby-1.9 prime_test.rb
Loaded suite prime_test
Started
..[:test_mathn, 17.422]
.[:test_mathn_each, 16.922]
.[:test_primes, 2.797]
.[:test_primes_each, 2.875]
.
Finished in 54.234 seconds.
6 tests, 30077 assertions, 0 failures, 0 errors

samples$ ruby-yarv prime_test.rb
Loaded suite prime_test
Started
..[:test_mathn, 7.718]
.[:test_mathn_each, 8.625]
.[:test_primes, 1.812]
.[:test_primes_each, 1.797]
.
Finished in 26.593 seconds.
6 tests, 30077 assertions, 0 failures, 0 errors