ビット配列をクラスライブラリにしてみました
エラトステネスの篩とビット配列 - 趣味的にっきの続きです。
使い易いようにビット配列をクラスにしてみました。配列の長さが足りないときは自動的に拡張するようにしています。インデックスに負数を入れると例外が発生するようにしています(これはRubyぽくないかも)。
ファイル: bitarray.rb
#!/usr/bin/env ruby class IndexOutOfBitArrayException < Exception; end class BitArray def initialize(init_size = 1) @buf = "\x00" * (init_size / 8 + 1) end def size @buf.size * 8 end alias length size def []=(index, on) extend_ary(index) q, r = index.divmod(8) if on @buf[q] |= 1 << r else @buf[q] &= 0xff - (1 << r) end end def [](index) extend_ary(index) q, r = index.divmod(8) (@buf[q] >> r) & 1 != 0 end def extend_ary(index) if index < 0 raise IndexOutOfBitArrayException, "index #{index} out of BitArray" end while index >= size @buf += "\x00" * @buf.size end end private :extend_ary end if $0 == __FILE__ upper = 1_000_000 sieve = BitArray.new 2.upto(upper) do |guess| next if sieve[guess] p guess (guess ** 2).step(upper, guess) {|mults| sieve[mults] = true } end end
ファイル: test_bitarray.rb
#!/usr/bin/env ruby # -*- compile-command: "ruby test_bitarray.rb" -*- require 'test/unit' require 'bitarray' class TC_BitArray < Test::Unit::TestCase def test_new assert_equal(8, BitArray.new.size) assert_equal(104, BitArray.new(100).length) end def test_set_get bary = BitArray.new assert_equal(false, bary[0]) bary[0] = true assert_equal(true, bary[0]) bary[0] = false assert_equal(false, bary[0]) assert_equal(false, bary[8]) bary[8] = true assert_equal(true, bary[8]) bary[8] = false assert_equal(false, bary[8]) assert_equal(16, bary.size) end def test_out_of_ary bary = BitArray.new assert_raise(IndexOutOfBitArrayException) do bary[-1] end assert_raise(IndexOutOfBitArrayException) do bary[-1] = true end end end