A hash-setek módosítható, rendezetlen gyűjtemények, amelyek minden
értéket legfeljebb egyszer tárolnak. A keresés, a beszúrás és a törlés
átlagosan O(1) idejű. A hash-sets szótárban élnek, és
megvalósítják a sets protokollt.
Hash-set literálok
HS{ "NS-1024" "WB-203" } .
! => HS{ "NS-1024" "WB-203" }
A HS{ } az üres literál. A többi Factor-literálhoz hasonlóan ez egy
megosztott objektum: a forráskódban minden HS{ } hivatkozás
ugyanarra a halmazra mutat. A HS{ } clone minden hívásnál egy friss,
független másolatot ad.
Sorozatból
>hash-set ( seq -- set ) ! build a fresh set from a sequence
Ha az értékek már egy sorozatban vannak, a >hash-set egyetlen lépésben
átalakítja őket, és közben elhagyja a duplikátumokat.
USING: hash-sets prettyprint ;
{ "NS-1024" "WB-203" "NS-1024" } >hash-set .
! => HS{ "NS-1024" "WB-203" }
Hozzáadás és eltávolítás
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
Mindhárom módosítja a halmazt, és egyik sem ad vissza semmit a veremre.
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" }
Az adjoin-all a tömeges forma: hozzáadja egy sorozat minden elemét, és
ugyanúgy kihagyja a duplikátumokat, ahogy az adjoin teszi egyesével.
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)
A halmaz lekérdezése
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
Az in? a set-protokoll tagsági vizsgálata. Különbözik a member?
szótól (amely a sequences szótárból származik), mert az egy lineáris
bejárást végez egy sorozaton. Egy hash-setnél az in? hash-keresés:
átlagosan O(1), és pont ezért érdemes hash-setet használni.
A null? azt jelzi, hogy a halmazban nincs elem. Ez a közvetlen módja
annak, hogy megkérdezd: „üres ez?”, ahelyett hogy a cardinality
értékét hasonlítanád össze nullával.
: 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
Halmazműveletek
union ( set1 set2 -- set )
intersect ( set1 set2 -- set )
diff ( set1 set2 -- set )
set-like ( set exemplar -- set' )
A union jelentése „az összes elem valamelyikükből”, az intersect „a
mindkettőben benne lévő elemek”, a diff pedig „a set1-ben benne van,
de a set2-ben nem”. Mindegyik új halmazt ad vissza, anélkül hogy
módosítaná a bemeneteit.
A set-like a set-et az exemplar típusára alakítja. Az
union/intersect/diff alapértelmezett implementációi ezt használják,
hogy az eredmény a fogadó típusával egyezzen: a <my-set> <hash-set> union returns a my-set-et ad vissza, nem hash-setet.
Miért fontos ez
A hash-setek természetesen társulnak a hashtáblákhoz gráfbejáráshoz:
a hashtábla minden csomópontot a szomszédaihoz rendel, a hash-set pedig
nyilvántartja, mely csomópontokat látogattuk már meg, hogy a keresés ne
kerüljön ciklusba, és ne végezze el ugyanazt a munkát kétszer. A bejárás
ekkor egy sor és a két adatszerkezet, amelyeket menet közben, helyben
módosítasz, ahogy egyre kifelé haladsz.
Tanulófeladat
