Hash-Sets sind veränderbare, ungeordnete Sammlungen, die jeden Wert höchstens einmal speichern. Nachschlagen, Einfügen und Löschen sind im Durchschnitt alle O(1). Sie sind im Vokabular hash-sets definiert und implementieren das sets-Protokoll.
Hash-Set-Literale
HS{ "NS-1024" "WB-203" } .
! => HS{ "NS-1024" "WB-203" }
HS{ } ist das leere Literal. Wie andere Factor-Literale ist es ein geteiltes Objekt: Jede Referenz auf HS{ } im Quelltext zeigt auf dasselbe Set. HS{ } clone gibt dir bei jedem Aufruf eine frische, unabhängige Kopie.
Aus einer Sequenz
>hash-set ( seq -- set ) ! build a fresh set from a sequence
Wenn du die Werte bereits in einer Sequenz hast, wandelt >hash-set sie in einem Schritt um und lässt dabei Duplikate weg.
USING: hash-sets prettyprint ;
{ "NS-1024" "WB-203" "NS-1024" } >hash-set .
! => HS{ "NS-1024" "WB-203" }
Hinzufügen und Entfernen
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
Alle drei verändern das Set an Ort und Stelle; keine von ihnen legt einen Wert auf den Stack.
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 ist die Variante für mehrere Elemente auf einmal: Sie fügt jedes Element einer Sequenz hinzu und überspringt Duplikate, genau wie adjoin es einzeln tut.
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)
Das Set abfragen
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? ist der Zugehörigkeitstest des Set-Protokolls. Es unterscheidet sich von member? (aus sequences), das eine lineare Suche über eine Sequenz durchführt. Bei einem Hash-Set ist in? ein Hash-Lookup mit durchschnittlich O(1), und genau das ist der Sinn eines Hash-Sets.
null? gibt an, ob das Set keine Elemente hat. Das ist der direkte Weg, um zu fragen, ob es leer ist, statt cardinality mit null zu vergleichen.
: 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
Sets kombinieren
union ( set1 set2 -- set )
intersect ( set1 set2 -- set )
diff ( set1 set2 -- set )
set-like ( set exemplar -- set' )
union bedeutet „alle Elemente aus beiden"; intersect bedeutet „Elemente, die in beiden vorkommen"; diff bedeutet „in set1, aber nicht in set2". Jede von ihnen gibt ein neues Set zurück, ohne ihre Eingaben zu verändern.
set-like wandelt set in den Typ von exemplar um. Die Standardimplementierungen von union/intersect/diff nutzen es, damit das Ergebnis zum Typ des Empfängers passt: <my-set> <hash-set> union gibt ein my-set zurück, kein Hash-Set.
Warum das wichtig ist
Hash-Sets passen natürlich zu Hashtabellen, wenn es um Graphdurchläufe geht: Eine Hashtabelle ordnet jedem Knoten seine Nachbarn zu, und ein Hash-Set merkt sich, welche Knoten bereits besucht wurden, damit die Suche nicht in Schleifen gerät oder Arbeit wiederholt. Der Durchlauf ist dann eine Warteschlange plus die beiden Strukturen, die verändert werden, während du dich nach außen vorarbeitest.
Lernübung
