Cuaderno de bitácora del faro

Los hash-sets son colecciones mutables y sin orden que almacenan cada valor como mucho una vez. La búsqueda, la inserción y la eliminación son todas O(1) de media. Están en hash-sets e implementan el protocolo sets.

Literales de hash-set

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

HS{ } es el literal vacío. Como otros literales de Factor, es un objeto compartido: todas las referencias a HS{ } en el código fuente apuntan al mismo conjunto. HS{ } clone te da una copia nueva e independiente en cada llamada.

A partir de una secuencia

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

Cuando ya tienes los valores en una secuencia, >hash-set los convierte en un solo paso y descarta los duplicados.

USING: hash-sets prettyprint ;

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

Añadir y eliminar

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

Los tres mutan el conjunto; ninguno devuelve nada en la pila.

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 es la forma masiva: añade cada elemento de una secuencia, saltándose los duplicados igual que hace adjoin de uno en uno.

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)

Preguntar al conjunto

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? es la prueba de pertenencia del protocolo de conjuntos. Es distinta de member? (de sequences), que hace un recorrido lineal sobre una secuencia. Para un hash-set, in? es una búsqueda por hash, O(1) de media, que es justo el motivo de usar un hash-set.

null? informa de si el conjunto no tiene elementos: la forma directa de preguntar «¿está vacío?» en lugar de comparar cardinality con cero.

: 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

Combinar conjuntos

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

union es «todos los elementos de cualquiera de los dos»; intersect es «los elementos que están en ambos»; diff es «los que están en set1 pero no en set2». Cada una devuelve un conjunto nuevo sin mutar sus entradas.

set-like convierte set al tipo de exemplar. Las implementaciones predeterminadas de union/intersect/diff lo usan para que el resultado coincida con el tipo del receptor: <my-set> <hash-set> union devuelve un my-set, no un hash-set.

Por qué esto importa

Los hash-sets se combinan de forma natural con las hashtables para el recorrido de grafos: una hashtable asocia cada nodo con sus vecinos, y un hash-set registra qué nodos ya se han visitado para que la búsqueda no entre en bucle ni repita trabajo. El recorrido es entonces una cola más las dos estructuras, mutadas en el lugar a medida que avanzas hacia fuera.