Rubyで素数判定してみた改

前回の日記：http://d.hatena.ne.jp/oropon/20111206/
コメントが付いていたのに気付きませんでした。すみません。誰も読んでないと思ってました。すみません。
いくつかコメントを頂いたので、自分なりに考えなおしてみたいと思います。

前回のコード。

class PrimePredicater
  def initialize
    @cache = [2]
  end
  
  def prime?(x)
    extend_cache x if @cache.empty? || x > @cache.last
    @cache.include? x
  end

private
  def _prime?(x)
    @cache.each do |i|
      return false if x % i == 0
    end
    true
  end

  def extend_cache(x)
    (@cache.last + 1 .. x).each do |i|
      @cache.push i if _prime? x
    end
  end
end

prime = PrimePredicater.new
1.upto(100) do |i|
  puts "#{i} is prime? : #{prime.prime? i}"
end

はてなのスーパーpre記法って行番号振れないんですね。あんまりスーパーじゃないですね。

前回のお悩み

#これを
return false if x % i == 0
#こうしても
break if x % i == 0
#戻り値はx % i == 0の値にならない

if式やbreak, イテレータあたりが返す値についてもうちょっと知識つける必要があるなあ。

せっかくx % i == 0 を評価してtrue/falseを返してるんだから、それをそのままメソッドの返り値に突っ込んだほうが書き方としてスマートっぽい（気がする）

x % i == 0 ならイテレータから抜けて、最後に評価された !(x % i == 0)の値を返すような、そんなスマートなやりかたを探そう...

頂いたコメント

上記のコード、お悩みに対して、

keyesberry 2011/12/06 22:52
@cache.none? { |i| x % i == 0 } でどうでしょう？

lettas0726 2012/02/11 12:09
@cache.find{|c| x%c == 0}.nil? でどうでしょう？

というコメントを頂きました。全くもってそのとおりだと思います。また、これなら_prime?()っていうプライベートメソッドも要りませんね。ArrayクラスやEnumerableモジュールの持つメソッドをまず調べるっていう姿勢が足りていませんでした。
そして、ツムジさんのコメント。

ツムジ 2011/12/09 11:10
私は、ソースコードを見た時にすぐにメソッドの返り値が分かるように、あえて "return" を書いています。

それから、oropon さんのコードは、素数の性質を考慮してもう少し工夫すると、約2倍の速さになりますよ。

"素数の性質を考慮する","約２倍"というところから、"ある数が素数か判別する際、その数の平方根以上、半分以下の整数で割り切れなければ素数である"という性質を指してのご指摘かと思います。
今回は素数のキャッシュを使っているので、"ある数が素数か判別する際、その数の半分以下の全素数で割り切れなければ素数である"と言い換えることになり、これを考慮して高速化してみます。

改良

まずは古いコードから。
arr = [10007, 10008, 5003]
これを素数判定にかけます。

10007 is prime? : true
4.606626s
10008 is prime? : false
0.000389s
5003 is prime? : true
0.000194s

キャッシュは効いていますが、やけに遅いです。
これをちょちょいと修正します。 シングルトンにするとかバリデーションとかは置いておきます。

class PrimePredicater
  def initialize
    @cache = [2]
  end

  def prime?(x)
    extend_cache x if x > @cache.last
    return @cache.include? x
  end

private
  def extend_cache(x)
    (@cache.last + 1 .. x).each do |i|
      @cache.push i if _prime? i
    end
  end

  def _prime?(num)
    @cache.each do |i|
      return true if i > num / 2 #変更点はほぼこれだけ
      return false if num % i == 0
    end
    return true
  end
end

prime = PrimePredicater.new
arr = [10007, 10008, 5003]
arr.each do |i|
  start_time = Time.now
  puts "#{i} is prime? : #{prime.prime? i}"
  end_time = Time.now
  puts "#{end_time - start_time}s"
end

結果、こうなりました。

10007 is prime? : true
0.061888s
10008 is prime? : false
5.7e-05s
5003 is prime? : true
3.1e-05s

半分どころの話ではありませんでした。一行で70倍ほどの高速化です。
使い道によっては使えなくもない速度ってところでしょうか。
なお、Rubyは標準添付ライブラリでPrimeクラスを提供しています。こちらと比べてみます。

# 自作
100003 is prime? : true
3.307069s
100004 is prime? : false
0.000371s
# ライブラリ
100003 is prime? : true
0.000104s
100004 is prime? : false
1.0e-05s

差は歴然です。素数生成アルゴリズムを学んでCで書くのもまた一興ですが、使う分には普通にPrimeクラスを使っとけって話ですね。はい。
コメントいただいた方々、ありがとう御座いました。”この書き方だせえ”とかありましたら是非教えてください。