灯台日誌

ハッシュセットは、それぞれの値を最大1回だけ保持する、変更可能で順序のないコレクションです。検索・挿入・削除はどれも平均O(1)です。hash-setsの中にあり、setsのプロトコルを実装しています。

ハッシュセットのリテラル

HS{ "NS-1024" "WB-203" } .
! => HS{ "NS-1024" "WB-203" }

HS{ }は空のリテラルです。他のFactorのリテラルと同じく、これは共有されるオブジェクトであり、ソース中でHS{ }を参照する箇所はどれも同じセットを指します。HS{ } cloneを使うと、呼び出すたびに新しい独立したコピーが得られます。

シーケンスから作る

>hash-set ( seq -- set )    ! build a fresh set from a sequence

値がすでにシーケンスに入っているなら、>hash-setを使えば一度に変換でき、重複は取り除かれます。

USING: hash-sets prettyprint ;

{ "NS-1024" "WB-203" "NS-1024" } >hash-set .
! => HS{ "NS-1024" "WB-203" }

要素の追加と削除

adjoin     ( elt set -- )    ! insert in place; no-op if already present
adjoin-all ( seq set -- )    ! insert every element of seq in place
delete     ( elt set -- )    ! remove in place; no-op if absent

3つともセットをその場で変更し、スタックには何も返しません。

USING: hash-sets kernel sets ;

HS{ } clone
"NS-1024" over adjoin
"WB-203"  over adjoin
"NS-1024" over adjoin    ! duplicate — no effect
.                        ! => HS{ "NS-1024" "WB-203" }

adjoin-allはまとめて行う形です。シーケンスの各要素を追加し、adjoinが1つずつ行うのと同じように重複を飛ばします。

USING: hash-sets kernel sets ;

HS{ "NS-1024" } clone
{ "WB-203" "NS-1024" "QR-7" } over adjoin-all
.                        ! => HS{ "QR-7" "NS-1024" "WB-203" }  (order not guaranteed)

セットに問い合わせる

in?         ( elt set -- ? )   ! is elt in the set?
null?       ( set -- ? )       ! is the set empty?
cardinality ( set -- n )       ! number of elements
members     ( set -- seq )     ! enumerate as a sequence

in?は、setプロトコルが定める所属テストです。sequencesのmember?とは別物で、こちらはシーケンスを線形に走査します。ハッシュセットの場合、in?はハッシュの検索であり、平均O(1)です。これこそがハッシュセットを使う意味です。

null?は、セットが要素を持たないかどうかを報告します。cardinalityを0と比べるのではなく、「これは空か？」と直接尋ねる方法です。

: my-log ( -- set ) HS{ "NS-1024" "WB-203" } ;

"NS-1024" my-log in? .   ! => t
"X-99"    my-log in? .   ! => f
my-log null? .           ! => f
HS{ } clone null? .      ! => t
my-log cardinality .     ! => 2

セットの組み合わせ

union     ( set1 set2 -- set )
intersect ( set1 set2 -- set )
diff      ( set1 set2 -- set )
set-like  ( set exemplar -- set' )

unionは「どちらかにあるすべての要素」、intersectは「両方にある要素」、diffは「set1にあってset2にない要素」です。どれも入力を変更せず、新しいセットを返します。

set-likeは、setをexemplarの型に変換します。union/intersect/diffの既定の実装はこれを使い、結果をレシーバーの型に合わせます。<my-set> <hash-set> unionはハッシュセットではなくmy-setを返すのです。

これが大切な理由

ハッシュセットは、グラフ探索でハッシュテーブルと自然に組み合わせられます。ハッシュテーブルは各ノードをその隣接ノードに対応づけ、ハッシュセットは、探索がループしたり同じ作業を繰り返したりしないよう、すでに訪問したノードを記録します。探索は、キューとこの2つの構造を組み合わせたものになり、外側へとたどりながらその場で書き換えていきます。