エラトステネスの嵐

Ruby

Ruby 勉強会の小波せんせのセッションについて。

最初のセッションだったので、遅れて来た人のネットワーク接続サポートとかしていてちゃんと聞けなかった。

また週末は次の勉強会だけど復習しておく。

まずは答えを見ずに素直に実装してみた。(erato.rb)

require 'forwardable'

class Erato
  extend Forwardable

  def initialize(n = 1000)
    @era = [nil, nil] + (2..n).to_a
    @era.each do |prime|
      next  if prime.nil?
      ((prime*2)..n).step(prime).each{|i| @era[i] = nil}
    end
    @era.compact!
  end

  def prime?(n) @era.include? n; end

  def_delegators(:@era, :include?, :each)
end

if $0 == __FILE__
  era = Erato.new(100)
  era.each do |prime|
    puts prime
  end
end

実行結果 (あってるはず)

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

ベンチマーク、プロファイルを採ってみる。(analyze.rb)

n = ARGV[0].to_i
n = 100000  if n == 0

if defined? Profiler__
  Erato.new(n)
else
  require 'benchmark'
  puts Benchmark.measure {
    Erato.new(n)
  }
end

使い方は以下の通り。

$ ruby -rerato analyze.rb            # ベンチマーク
$ ruby -rerato -rprofile analyze.rb  # プロファイル

プロファイルの結果、

  %   cumulative   self              self     total
 time   seconds   seconds    calls  ms/call  ms/call  name
    ...
  6.38    22.94      1.52    90409     0.02     0.02  NilClass#nil?

nil? が 90409 回しか呼ばれてないのを見て狼狽える。

もうちょっと下の方に

  0.19    23.84      0.05     9592     0.00     0.00  Kernel.nil?

を見つけて (90409 + 9592 = 100001) 安心する。

でも、ちょっと考えると 100001 回繰り返さなくても √n 回でいいんですよね。
(昔は知らずに n/2 回繰り返していました)

勉強会の資料にも出てきます。(P.9)


小波せんせの資料は大変すばらしいので一読をお勧めします。

この資料の最初の実装は、

  • まず、1〜100000 までの配列を用意する。(1)
  • 2 の倍数の配列 [4, 6, 8, 10, 12, ... 100000] を算出 (2)
  • (1) から (2) を引くと篩の 1 回目が終了。
  • 同様に 3 の倍数, 5 の倍数 ... と繰り返す。

というもの。

Ruby では配列の引き算ができるから簡単にできそう。という着想らしい。

資料を読み進むと、私が書いたのに似たコードが出てきます。

私のコードとの違いは √n 回で止めようとする点。
こんな感じ (erato2.rb) 

require 'forwardable'

class Erato
  extend Forwardable

  def initialize(n = 1000)
    @era = [nil, nil] + (2..n).to_a
    enough = Math.sqrt(n).floor
    @era.each do |prime|
      next   if prime.nil?
      break  if prime > enough
      ((prime*2)..n).step(prime).each{|i| @era[i] = nil}
    end
    @era.compact!
  end

  def prime?(n) @era.include? n; end

  def_delegators(:@era, :include?, :each)
end
しかしプロファイルしてみると、ループを余計に回ってる。 
$ ruby -rerato2 -rprofile analyze.rb 169
  %   cumulative   self              self     total
 time   seconds   seconds    calls  ms/call  ms/call  name
    ...
  0.00     0.01      0.00       11     0.00     0.00  NilClass#nil?
    ...
  0.00     0.01      0.00        7     0.00     0.00  Kernel.nil?
    ...

本当は 14 回 (0 + √169) でいいはずなのに、18 回もループしてる。
14..16 が素数じゃないから。(nil だから)

それじゃあ each_with_index を使ってみる? (erato3.rb) 
require 'forwardable'

class Erato
  extend Forwardable

  def initialize(n = 1000)
    @era = [nil, nil] + (2..n).to_a
    enough = Math.sqrt(n).floor
    @era.each_with_index do |prime, i|
      break  if i > enough
      next   if prime.nil?
      ((prime*2)..n).step(prime).each{|i| @era[i] = nil}
    end
    @era.compact!
  end

  def prime?(n) @era.include? n; end

  def_delegators(:@era, :include?, :each)
end
プロファイルの結果はこんな感じ。 
$ ruby -rerato3 -rprofile analyze.rb 169
  %   cumulative   self              self     total
 time   seconds   seconds    calls  ms/call  ms/call  name
    ...
  0.00     0.02      0.00        8     0.00     0.00  NilClass#nil?
    ...
  0.00     0.02      0.00        6     0.00     0.00  Kernel.nil?
    ...
ちゃんと 14 回で終わってる。 each を each_with_index に変更して、かえって遅くなるかと思って、ベンチマークを見てみたけど、若干速くなってた。意外。 その他、気付いたこと。
  • Integer#step よりも Range#step の方が速い。
  • next if prime.nil? は next unless prime とした方が読みやすいかも。