From: Akinori MUSHA <knu@...>
Date: 2002-04-06T18:04:16+09:00
Subject: [ruby-dev:16765] Set

　Set というクラスを書いてみました。これは重複なし、順序なしの
要素集合を表現するものです。

　自分で使っていて、ほぼ満足な仕上がりと思えてきたのでアナウンス
します。物は rough にあります。

http://www.ruby-lang.org/cgi-bin/cvsweb.cgi/rough/lib/set.rb


　Ruby で何らかのリスト、たとえばファイルリストを管理するとき、
一般的には Array を使うと思います。要素の追加や削除は自在ですし、
&, |, - など、リスト同士の演算もサポートしています。

　ところが、これには大きな問題があります。要素の数が増えてくると
include?() や &, |, - などの演算が目に見えて遅くなってしまう。
全要素をなめて比較せざるを得ないというのは非常に不利な点です。
ソートしてあれば bsearch が使えますが、常にソートしておくのは
コストや手間がかかります。


　一方 Hash を使うという解はあります。値の追加や検索は高速ですし、
each_key や keys で走査や配列化もできます。

　しかし、これにも欠点があります。まず、キーにダミーの値を登録
するという操作が直感的でない。そして、リスト同士の演算も困難。


　rubygarden や #ruby-lang で話を聞くと、 Array と Hash を適宜
組み合わせて使っているという人が多いようで、これは専用のクラスを
作る価値がありそうだと思いました。

　そこで、 Set の登場です。Hash の高速検索に Array の直感的な
演算能力を掛け合わせ、任意の Enumerable オブジェクトとの様々な
演算ができるようになっています。(ここに載せるのは無駄なので、
コードに埋め込んであるドキュメントを参照してください)


　今の実装は Hash を Ruby でラップしただけですが、これでも十分な
速度で動いてくれています。ただ、 Ruby 内部でもこの手の重複なし
集合の操作に Hash を使ったり Array を使ったりしているので、 C で
実装して組み込んでも使いでがあるかなと思ったりはしています。

　この手のは標準にないと使えないので、ある程度反応がよければ
lib/set.rb に入れる方向で考えています。


　ということで、何か注文や指摘があればよろしくお願いします。

-- 
                     /
                    /__  __            Akinori.org / MUSHA.org
                   / )  )  ) )  /     FreeBSD.org / Ruby-lang.org
Akinori MUSHA aka / (_ /  ( (__(  @ iDaemons.org / and.or.jp

"Somewhere out of a memory.. of lighted streets on quiet nights.."