石橋"rubyholic"秀仁です。

From: matz / netlab.co.jp (Yukihiro Matsumoto)
Subject: [ruby-list:22972] Re: most efficient check-list implementation

> まつもと ゆきひろです
> 
> 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) 時間効率 (速度)
> |が最も良い方法は何か、という点です。

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

なるほど。繰り返し数が多いと、毎回のコピーは痛いです。

> 折衷案としては
> 
>   (a) 配列の各要素を8ビットまたは16ビットに対応させるクラス
>       を作る(Rubyで定義)
> 
>   (b) Bignumと類似の実装でmutableなBitVectorクラスを拡張ライ
>       ブラリで記述する。
> 
> というものが考えられます。まずaをやってみて遅すぎるようなら、
> bを検討するという流れでしょうか?

そのようにします。ありがとうございます。

ところで (a) で欲張って 31 ビット使うのはまずいのでしょうか。

--
Hideto "rubyholic" ISHIBASHI
http://www.rr.iij4u.or.jp/~hideto-i/
blade clone (yaiba) development:
http://www.rr.iij4u.or.jp/~hideto-i/rb/yaiba/index.html