« Project Euler - Problem 57 | トップページ | Project Euler - Problem 58 »

2009年8月20日 (木)

"math_tool.rb" の改良

先日、以前から興味のあった「素因数分解と素数判定」という本をやっと手に入れました。

まだ読み始めたばかりなのですが、ちょうど「試し割による素因数分解」のアルゴリズムが出てきました。

そのアルゴリズムが「2, 3 以外の素数 p は

p % 6 == 1 または p % 6 == 5

という条件を必ず満たす」という事実をもとに書いてありました。

このことは以前から知っていたのですが、自分の作った素数を扱うメソッドではこの考え方を利用していませんでした。

今回この考え方を使って、自作の "math_tool.rb" のメソッドの一部 ("Integer#prime?", "Integer#factorize") を改良してみました。

さらに、"prime_list" もコードを見直して、無駄な処理を削ってみました。

ちょっとだけ速くなりました。

実際のコードはここにあります。


実際のスピードを添付ライブラリの "prime.rb" と比べてみるためのスクリプトを書いてみました。。

# test.rb require 'prime' t = Time.now (2 .. 10_0000).each{|x| x.prime?} prime1 = Time.now - t t = Time.now (2 .. 10_0000).each{|x| x.prime_division} prime_division = Time.now - t t = Time.now a = Prime.each(10_0000).to_a prime_each = Time.now - t require 'math_tool' t = Time.now (2 .. 10_0000).each{|x| x.prime?} prime2 = Time.now - t t = Time.now (2 .. 10_0000).each{|x| x.factorize} factorize = Time.now - t t = Time.now a = prime_list(10_0000) prime_list = Time.now - t print "prime.rb : prime? : #{prime1} sec\n" print "math_tool.rb : prime? : #{prime2} sec\n" print "\n" print "prime.rb : prime_division : #{prime_division} sec\n" print "math_tool.rb : factorize : #{factorize} sec\n" print "\n" print "prime.rb : Prme.each : #{prime_each} sec\n" print "math_tool.rb : prime_list : #{prime_list} sec\n"

結果はこの様になりました。(ちなみに測定条件は「Pentium M 1.5GHz, Ruby 1.91」でした)

$ ruby test.rb prime.rb : prime? : 2.730776398 sec math_tool.rb : prime? : 0.227278105 sec prime.rb : prime_division : 6.384688654 sec math_tool.rb : factorize : 1.022429391 sec prime.rb : Prme.each : 0.176912212 sec math_tool.rb : prime_list : 0.025297353 sec

"prime.rb" より数倍速いという結果が出ました。自作のメソッドのスピードが予想以上に速かったので、ビックリしつつも非常に喜ばしい結果でした。

« Project Euler - Problem 57 | トップページ | Project Euler - Problem 58 »

Project Euler」カテゴリの記事

Ruby」カテゴリの記事

コメント

コメントを書く

コメントは記事投稿者が公開するまで表示されません。

(ウェブ上には掲載しません)

トラックバック

この記事のトラックバックURL:
http://app.cocolog-nifty.com/t/trackback/112020/45978679

この記事へのトラックバック一覧です: "math_tool.rb" の改良:

« Project Euler - Problem 57 | トップページ | Project Euler - Problem 58 »

2016年7月
          1 2
3 4 5 6 7 8 9
10 11 12 13 14 15 16
17 18 19 20 21 22 23
24 25 26 27 28 29 30
31            
フォト

最近のトラックバック

無料ブログはココログ