Τα hash-sets είναι μεταβλητές, μη διατεταγμένες συλλογές που αποθηκεύουν κάθε τιμή
το πολύ μία φορά. Η αναζήτηση, η εισαγωγή και η διαγραφή είναι όλες κατά μέσο
όρο O(1). Βρίσκονται στο hash-sets και υλοποιούν το
πρωτόκολλο sets.
Τα literals των hash-set
HS{ "NS-1024" "WB-203" } .
! => HS{ "NS-1024" "WB-203" }
Το HS{ } είναι το κενό literal. Όπως και τα άλλα literals της 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
Και τα τρία μεταβάλλουν το σύνολο· κανένα δεν επιστρέφει κάτι στη στοίβα.
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 ένα κάθε φορά.
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? είναι ο έλεγχος συμμετοχής του πρωτοκόλλου συνόλων. Διαφέρει από το
member? (από το sequences), που κάνει γραμμική σάρωση πάνω σε μια ακολουθία.
Για ένα hash-set, το in? είναι αναζήτηση σε πίνακα κατακερματισμού, κατά μέσο
όρο O(1), που είναι και το όλο νόημα της χρήσης ενός hash-set.
Το null? αναφέρει αν το σύνολο δεν έχει στοιχεία, ο άμεσος τρόπος να ρωτήσεις
"είναι αυτό κενό;" αντί να συγκρίνεις το cardinality με το μηδέν.
: 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, όχι ένα hash-set.
Γιατί έχει σημασία
Τα hash-sets ταιριάζουν φυσικά με τα hashtables για διάσχιση γράφου: ένα
hashtable αντιστοιχίζει κάθε κόμβο με τους γείτονές του, και ένα hash-set
καταγράφει ποιοι κόμβοι έχουν ήδη επισκεφθεί, ώστε η αναζήτηση να μην κάνει
κύκλους ή να μην επαναλαμβάνει δουλειά. Η διάσχιση είναι τότε μια ουρά συν τις
δύο δομές, που μεταβάλλονται επί τόπου καθώς απλώνεσαι προς τα έξω.
Άσκηση εκμάθησης
