まつもと ゆきひろです

In message "[ruby-list:22961] most efficient check-list implementation"
    on 00/05/28, Hideto ISHIBASHI <hideto-i / rr.iij4u.or.jp> writes:

|Ruby で効率のよいチェックリストの実現方法を教えてください。
|
|1 つの要素について「チェック済」と「未チェック」の 1 bit です。
|これを Ruby でやりたいので質問しました。
|
|お知恵を拝借したいのは:
| (1) メモリ効率
| (2) 時間効率 (速度)
|が最も良い方法は何か、という点です。
|
|とくにメモリ効率に興味があります。理想的には 100 万ビットで、
|120 kB くらいのメモリ使用量ですね (1B = 8bit)。

k = 1024 とすると100万ビットは122kB強ですね。

整数をbit arrayとして使う方法は、メモリ効率は良いのですが、
数値はimmutableなので毎回コピーが発生するというデメリットが
あります。GCも刺激しそう。

配列を使う方法は、各要素を1ビットに対応させる場合、メモリ効
率は情報1ビットに対して32ないし64ビット消費します。が、逆に
オブジェクトのコピーは発生しません。

折衷案としては

  (a) 配列の各要素を8ビットまたは16ビットに対応させるクラス
      を作る(Rubyで定義)

  (b) Bignumと類似の実装でmutableなBitVectorクラスを拡張ライ
      ブラリで記述する。

というものが考えられます。まずaをやってみて遅すぎるようなら、
bを検討するという流れでしょうか?

                                まつもと ゆきひろ /:|}