Ruby 「エラトステネスの篩」を通してアルゴリズムの威力を体感する #Ruby

「Ruby で実装するエラトステネスのふるい小波秀雄(pdf)
」の良質な記事を参照している

エラトステネスの篩とは素数を見つけ出すためのアルゴリズムである。
まず最初の素数である２の倍数を削除していく、次に残った数の最初に来る数、３の倍数を削除していく。次にくる数、５の倍数を削除していく。
同じような動作を延々と続けて素数を見つける。

この記事はエラトステネスの篩を通してアルゴリズムの威力を体感する事が目的

require 'benchmark'
def erato_1(n)
  numbers = (2..n).to_a # 2 ～ n の配列を用意
  primes = [] # 素数を放り込むための配列
  loop do
    d = numbers.shift # 配列の先頭要素を取り出して
  break if d == nil # nil なら終了
    primes << d # 素数の配列に追加。
    to_delete = [] # 取り除く候補を入れる配列
    numbers.each do |x|
      to_delete << x if x % d == 0 # d の倍数を取り除く候補に入れる
    end
    numbers -= to_delete # d の倍数がそっくり引かれる
  end
  return primes
end

puts Benchmark.measure{ erato_1(10000) }

=>  0.120000   0.000000   0.120000 (  0.120805)

rubyのプロファイラでチェックする、ファイルの先頭に
#!/usr/local/bin/ruby # -r profileを加えてコードを実行する.


time   seconds   seconds    calls  ms/call  ms/call  name
 57.31    26.15     26.15   777862     0.03     0.16  Object#erato_1
 25.68    37.87     11.72     1230     9.53    36.90  Array#each
  8.99    41.97      4.10   777860     0.01     0.01  Fixnum#==
  7.69    45.48      3.51   776631     0.00     0.00  Fixnum#%
  0.15    45.55      0.07     9999     0.01     0.01  Array#<<
  0.11    45.60      0.05     1229     0.04     0.04  Array#-
....下記省略

if x % d == 0の条件判断に時間がかかっている、
またprime = [ ]のところがnumbersにデータが入っているので不要である

require 'benchmark'
def erato_2(n)
  numbers = (2..n).to_a
  i = 0
  loop do
  break unless d = numbers[i]
    to_delete = []
    (2*d..n).step(d){|e| to_delete << e}
    numbers -= to_delete
    i += 1
  end
  return numbers
end

puts Benchmark.measure{
  erato_2(10000) }
=> 0.090000   0.010000   0.100000 (  0.097825)

少しだけはやくなった
ただ#erato_2にはまだ無駄がある、例えば１００までの素数を調べたいとして、2,3,5,7の倍数を削除した時点で１００までの素数はすべてそろっている状態であるがそのあとの１１、１３、、以降の倍数を削除している処理が無駄である

def erato_3(n)
  sqrt = Math.sqrt(n).floor
  numbers = (2...n).to_a
  i = 0
  loop do
    break if i >= sqrt
    d = numbers[i]
    to_delete = []
    (2*d..n).step(d){|e| to_delete << e}
    numbers -= to_delete
    i += 1
  end
  return numbers
end

puts Benchmark.measure{ erato_3(10000) }
=> 0.020000   0.000000   0.020000 (  0.026519)

３倍近く早くなった、だがまだ早くする余地がある
numbers -= to_deleteの箇所で処理量が増えているのでここの箇所をなくす

def erato_4(n)
  numbers = (0..n).to_a
  numbers[0],numbers[1] = nil
  numbers.each do |d|
    next if d == nil
    break if (Math.sqrt(n) < d)
    (2*d..n).step(d){|e| numbers[e] = nil}
  end
  numbers.compact!
  return numbers
end
puts Benchmark.measure{ erato_4(10000) }
=> 0.010000   0.000000   0.010000 (  0.003047)

８倍ぐらい早くなった、アルゴリズムは深い、、、、