エラトステネスの篩とビット配列
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