Хеш-таблиці у Factor - це асоціативні масиви, тобто колекції пар
key/value з доступом за O(1). Вони належать до ширшої родини
assocs.
H{ { "coal" 1 } { "wood" 2 } } .
H{ } позначає порожню хеш-таблицю. Хеш-таблиці змінювані: вони
ростуть і скорочуються, коли ми додаємо та видаляємо ключі. Якщо
потрібно залишити оригінал без змін, спершу варто викликати clone.
Друк хеш-таблиці показує її записи, але порядок не повʼязаний із
порядком додавання. Хеш-таблиці невпорядковані.
at (з assocs) читає значення й повертає f, якщо ключа
немає:
at ( key assoc -- value/f )
key? ( key assoc -- ? )
"coal" H{ { "coal" 1 } { "wood" 2 } } at . ! => 1
"gold" H{ { "coal" 1 } { "wood" 2 } } at . ! => f
set-at додає або перезаписує; delete-at видаляє; change-at
виконує quotation над поточним значенням. Усі три змінюють
хеш-таблицю на місці:
set-at ( value key assoc -- )
delete-at ( key assoc -- )
change-at ( key assoc quot: ( old -- new ) -- )
H{ } clone 5 "coal" pick set-at .
! => H{ { "coal" 5 } }
inc-at як скорочення для підрахункуinc-at (також із assocs) додає 1 до наявного значення для
ключа, а якщо ключа немає, вставляє його зі значенням 1. Ідеально для
підрахунку:
inc-at ( key assoc -- )
H{ } clone "coal" over inc-at .
! => H{ { "coal" 1 } }
assoc-each проходить кожну пару ( key value -- ); cache
повертає значення для ключа, обчислюючи його один раз наданим
quotation, якщо ключа немає.
assoc-each ( assoc quot: ( key value -- ) -- )
cache ( key assoc quot: ( key -- value ) -- value )
cache втілює шаблон «знайти або створити» в одному слові. Це зручно,
коли ми будуємо хеш-таблицю з потоку ключів і не хочемо обробляти
випадок відсутнього запису в кожному місці виклику.
Коли вхідні дані - це послідовність ключів і ми хочемо оновити
хеш-таблицю по одному разу на кожен ключ, перебираємо послідовність
за допомогою each і використовуємо fried quotation '[ _ … ]
(з fry), щоб вбудувати хеш-таблицю в тіло циклу. Наприклад,
видалення списку ключів:
{ "wood" "iron" } H{ { "coal" 5 } { "wood" 3 } { "iron" 2 } } clone
[ '[ _ delete-at ] each ] keep .
! => H{ { "coal" 5 } }
'[ _ delete-at ] захоплює хеш-таблицю, що лежить над ним у стеку,
тож на кожній ітерації each має надати лише ключ. keep виконує
quotation, зберігаючи хеш-таблицю для фінальної ..
map>assoc (з assocs) відображає quotation на послідовність
і збирає результати ( elt -- key value ) в assoc типу зразка:
map>assoc ( seq quot: ( elt -- key value ) exemplar -- assoc )
{ "wood" } [ dup length ] H{ } map>assoc .
! => H{ { "wood" 4 } }
keys і values (з assocs) повертають лише ключі або
лише значення; >alist повертає пари { key value }.
keys ( assoc -- keys )
values ( assoc -- values )
>alist ( assoc -- alist )
H{ { "wood" 11 } { "coal" 7 } } keys . ! the keys (order not guaranteed)
H{ { "wood" 11 } { "coal" 7 } } values . ! the matching values
keys і values відповідають одне одному: значення на певній позиції
належить ключу на тій самій позиції.
sort-keys (з sorting) повертає пари { key value },
відсортовані за ключем:
H{ { "wood" 11 } { "coal" 7 } } sort-keys .
! => { { "coal" 7 } { "wood" 11 } }
>hashtable (з hashtables) виконує перетворення,
обернене до >alist: він перетворює будь-який assoc (найчастіше alist
із пар { key value }) у хеш-таблицю з доступом за O(1).
>hashtable ( assoc -- hashtable )
{ { "coal" 7 } { "wood" 11 } } >hashtable .
! => H{ { "wood" 11 } { "coal" 7 } } (entry order not guaranteed)
Зручно, коли ми зібрали або перетворили список пар і хочемо згорнути його назад у хеш-таблицю, щоб шукати записи за ключем.
Уявімо себе скарбниками на кораблі, які ведуть облік запасів у коморі. Інвентар - хеш-таблиця, у якій ключами є назви предметів, а значеннями - їхня кількість на складі.
Визначмо create-inventory, яка приймає послідовність назв предметів і повертає хеш-таблицю, що зіставляє кожну унікальну назву з її кількістю.
{ "coal" "wood" "wood" "diamond" "diamond" "diamond" } create-inventory .
! => H{ { "coal" 1 } { "wood" 2 } { "diamond" 3 } }
Визначмо add-items, яка приймає інвентар і послідовність предметів та повертає новий інвентар, у якому кількості збільшено на одиницю для кожного з перелічених предметів. Початковий інвентар не повинен змінюватися.
H{ { "coal" 1 } } { "wood" "iron" "coal" "wood" } add-items .
! => H{ { "coal" 2 } { "wood" 2 } { "iron" 1 } }
Визначмо decrement-items, яка приймає інвентар і послідовність предметів та повертає новий інвентар, у якому кількості зменшено на одиницю для кожного з перелічених предметів. Кількості ніколи не повинні ставати меншими за нуль, а предмети, яких ще немає в інвентарі, слід пропустити (записи з відʼємними значеннями не додаються).
H{ { "coal" 3 } { "diamond" 1 } { "iron" 5 } }
{ "diamond" "coal" "iron" "iron" } decrement-items .
! => H{ { "coal" 2 } { "diamond" 0 } { "iron" 3 } }
Визначмо remove-item, яка приймає інвентар і предмет та повертає новий інвентар без цього предмета. Якщо предмета немає в інвентарі, повернімо незмінену копію.
H{ { "coal" 2 } { "wood" 1 } { "diamond" 2 } } "coal" remove-item .
! => H{ { "wood" 1 } { "diamond" 2 } }
Визначмо list-inventory, яка приймає інвентар і повертає масив пар { name quantity }, що містять лише предмети, кількість яких більша за нуль, відсортований за назвами в абетковому порядку.
H{ { "coal" 7 } { "wood" 11 } { "diamond" 2 } { "iron" 7 } { "silver" 0 } }
list-inventory .
! => { { "coal" 7 } { "diamond" 2 } { "iron" 7 } { "wood" 11 } }
Зареєструйтеся на Exercism, щоб вивчати й опановувати Factor, а також 47 концепцій163 вправи та справжнє наставництво від людей, і все це безкоштовно.