最近のキーワード

2006年06月19日

上限を決めずに素数を生成の高速化(Ruby版)

「上限を決めずに素数を生成」を高速化。(追記あり 6/21)
もともとは、「キミならどう書く 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
posted by ttate at 20:04| 🌁| Comment(0) | TrackBack(1) | Ruby | このブログの読者になる | 更新情報をチェックする
この記事へのコメント
コメントを書く
お名前:

メールアドレス:

ホームページアドレス:

コメント:

認証コード: [必須入力]


※画像の中の文字を半角で入力してください。

この記事へのトラックバック

[Squeak][Smalltalk][OOPL] エラトステネスのふるいをコンパクトにする方法
Excerpt: 素数を列挙するにあたって、エラトステネスのふるいは比較的高速で有効です。たとえば、404 Blog Not Found:LLR2006 - 1,000,000(番目|まで)の素数 で、いくつかの言語..
Weblog: sumim’s smalltalking-tos
Tracked: 2006-06-21 10:19
×

この広告は1年以上新しい記事の投稿がないブログに表示されております。