> |Ruby で効率のよいチェックリストの実現方法を教えてください。
> |
> |1 つの要素について「チェック済」と「未チェック」の 1 bit です。
> |これを Ruby でやりたいので質問しました。
> |
> |お知恵を拝借したいのは：
> | (1) メモリ効率
> | (2) 時間効率 (速度)
> |が最も良い方法は何か、という点です。

> 整数をbit arrayとして使う方法は、メモリ効率は良いのですが、
> 数値はimmutableなので毎回コピーが発生するというデメリットが
> あります。GCも刺激しそう。
> 
> 配列を使う方法は、各要素を1ビットに対応させる場合、メモリ効
> 率は情報1ビットに対して32ないし64ビット消費します。が、逆に
> オブジェクトのコピーは発生しません。
> 
> 折衷案としては
> 
>   (a) 配列の各要素を8ビットまたは16ビットに対応させるクラス
>       を作る(Rubyで定義)
> 
>   (b) Bignumと類似の実装でmutableなBitVectorクラスを拡張ライ
>       ブラリで記述する。


Stringをバッファ(?)として使うのはどうでしょうか?
ちょっと試したところではサイズは増えない様でした。
速度はこれしか試してないのでわかりません。


class Bits
  def initialize(n)
    @size = n
    @bits = "\0" * ((n/8)+1)
  end
  public
  attr_reader(:size)
  def lengh
    size
  end

  private
  def idx(i)
    raise "index" if (i >= size) or (i < 0)
    return i/8, (1<<(i%8))
  end
  
  public
  def set(i)
    bytes, bits = idx(i)
    c = @bits[bytes]
    @bits[bytes] = c | bits
  end

  public
  def reset(i)
    bytes, bits = idx(i)
    c = @bits[bytes]
    @bits[bytes] = c & (~bits)
  end

  public
  def set?(i)
    bytes, bits = idx(i)
    c = @bits[bytes]
    c & bits != 0
  end
end