Diario del faro

Gli hash-set sono collezioni mutabili e non ordinate che memorizzano ogni valore al massimo una volta. La ricerca, l'inserimento e la cancellazione sono tutti O(1) in media. Si trovano in hash-sets e implementano il protocollo sets.

I letterali degli hash-set

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

HS{ } è il letterale vuoto. Come gli altri letterali di Factor, è un oggetto condiviso: ogni riferimento a HS{ } nel codice sorgente punta allo stesso insieme. HS{ } clone produce una copia nuova e indipendente a ogni chiamata.

A partire da una sequenza

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

Quando hai già i valori in una sequenza, >hash-set li converte in un solo passaggio, scartando i duplicati.

USING: hash-sets prettyprint ;

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

Aggiungere e rimuovere

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

Tutte e tre modificano l'insieme; nessuna restituisce nulla sullo 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 è la versione in blocco: aggiunge ogni elemento di una sequenza, saltando i duplicati proprio come fa adjoin uno alla volta.

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)

Interrogare l'insieme

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? è il test di appartenenza del protocollo dei set. È diverso da member? (di sequences), che esegue una scansione lineare su una sequenza. Per un hash-set, in? è una ricerca hash: O(1) in media, ed è proprio il motivo per cui si usa un hash-set.

null? indica se l'insieme non ha elementi: è il modo diretto per chiedere «è vuoto?» invece di confrontare cardinality con zero.

: 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

Combinare gli insiemi

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

union è «tutti gli elementi di entrambi»; intersect è «gli elementi in comune»; diff è «quelli in set1 ma non in set2». Ognuna restituisce un nuovo insieme senza modificare i suoi input.

set-like forza set al tipo di exemplar. Le implementazioni predefinite di union/intersect/diff la usano per far corrispondere il tipo del risultato a quello del ricevente: <my-set> <hash-set> union restituisce un my-set, non un hash-set.

Perché è importante

Gli hash-set si abbinano naturalmente alle hashtable per l'attraversamento dei grafi: una hashtable associa ogni nodo ai suoi vicini, e un hash-set tiene traccia di quali nodi sono già stati visitati, così la ricerca non entra in cicli né ripete lavoro. L'attraversamento è quindi una coda più le due strutture, modificate sul posto mentre si procede verso l'esterno.