Хеш-множини - це змінювані невпорядковані колекції, які зберігають кожне
значення щонайбільше один раз. Пошук, вставлення і вилучення в середньому
мають складність O(1). Вони живуть у hash-sets і реалізують
протокол sets.
Літерали хеш-множин
HS{ "NS-1024" "WB-203" } .
! => HS{ "NS-1024" "WB-203" }
HS{ } - це порожній літерал. Як і інші літерали 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), яка виконує лінійний перебір послідовності. Для
хеш-множини in? - це хеш-пошук, у середньому O(1), і саме заради цього
хеш-множини й використовують.
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,
а не хеш-множину.
Чому це важливо
Хеш-множини природно поєднуються з хеш-таблицями для обходу графа:
хеш-таблиця зіставляє кожному вузлу його сусідів, а хеш-множина
запамʼятовує, які вузли вже відвідано, щоб пошук не зациклювався й не
повторював роботу. Тоді обхід - це черга плюс ці дві структури, які
змінюються на місці, поки ми просуваємося назовні.
Навчальна вправа
