もともとは、「キミならどう書く 2.0 - ROUND 1 -」に対する解だったが、mathn.rbの素数生成が遅かったので、その代わりとなるように作ってみた。
特徴:
- タイトル通り上限がありません。メモリが尽きるまでどこまででも求めます。
- 見つかった素数の個数に比例してメモリを消費。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ちなみに、最後の1000000個目の素数を求めるものは30MBほどのメモリ消費。 皆さんの環境でも試して見て欲しい。また、最後に考察として他の実装とも比較してみたものを書いた
そして、ソース(prime.rb)と テストコード。 (追記 6/21) 他にも条件分岐を少なくしたもの(prime2.rb)や、 イテレータをメインにしたもの(prime3.rb)も置いてみた。
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