エラトステネスの篩とビット配列

UNIX Magazine 2000/01のPERL ADVISOR 26には、エラトステネスの篩で素数を求める際に、素数かどうかを覚えておくためのビット配列を使って省メモリ化している例が載っています。よく知らないのですが、Perlではvec演算子を利用すればビット配列を直接扱うことができるようです。
さてこれをRubyでどうやろうかなぁと思って以下のプログラムを書いてみました。ビット配列を扱うライブラリがすでに提供されているような気もしますが、5分探して諦めました。

class String
  def set_vec(index, on)
    q, r = index.divmod(8)
    if on
      self[q] |= 1 << r
    else
      self[q] &= 0xff - (1 << r)
    end
  end    

  def get_vec(index)
    q, r = index.divmod(8)
    not ((self[q] >> r) & 1).zero?
  end
end

upper = 1_000_000
sieve = "\x00" * (upper + 1)
2.upto(upper) do |guess|
  next if sieve.get_vec(guess)
  p guess
  (guess * 2).step(upper, guess) {|mults| sieve.set_vec(mults, true) }
end

僕の使っている計算機(WindowsXP SP2、PentiumM 1.7GHz)で実行速度を計測したところ、以下のようになりました。

> ruby --version
ruby 1.8.6 (2007-09-24 patchlevel 111) [i386-mswin32]
> time ruby a.rb
ruby b.rb  0.03s user 0.01s system 0% cpu 15.713 total

普通のtrue/falseの配列を使う場合は以下のようになります。

upper = 1_000_000
sieve = Array.new(upper + 1)
2.upto(upper) do |guess|
  next if sieve[guess]
  p guess
  (guess * 2).step(upper, guess) {|mults| sieve[mults] = true }
end

こちらの実行時間は以下の通りです。ビット配列版は2.5倍くらい実行時間がかかります。

> time ruby a.rb
ruby a.rb  0.03s user 0.02s system 0% cpu 6.239 total

メモリがどれくらい削減できたかは上記のプログラムのメモリ使用量の支配的な部分だけを抜き出して、タスクマネージャで目測してみました。メモリ使用量が4分の1くらいになっています。

sleep 60
# rubyのオーバーヘッドを計測。3,060K

upper = 1_000_000
sieve = "\x00" * (upper + 1)
sleep 60
# ビット配列の場合を計測。4,068K

upper = 1_000_000
sieve = Array.new(upper + 1)
sleep 60
# true/falseの配列の場合を計測。7,008K

なお余談ですが、一番上のビット配列版のプログラムは以下のように少し効率化できます。

class String
  def set_vec(index, on)
    q, r = index.divmod(8)
    if on
      self[q] |= 1 << r
    else
      self[q] &= 0xff - (1 << r)
    end
  end    

  def get_vec(index)
    q, r = index.divmod(8)
    not ((self[q] >> r) & 1).zero?
  end
end

upper = 1_000_000
sieve = "\x00" * (upper + 1)
2.upto(upper) do |guess|
  next if sieve.get_vec(guess)
  p guess
  (guess ** 2).step(upper, guess) {|mults| sieve.set_vec(mults, true) }
end

参照: エラトステネスの篩 - Wikipedia