> |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