Треки
/
Factor
Factor
/
Вправи
/
Комора скарбника
Комора скарбника

Комора скарбника

Навчальна вправа

Вступ

Хеш-таблиці у 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)

Зручно, коли ми зібрали або перетворили список пар і хочемо згорнути його назад у хеш-таблицю, щоб шукати записи за ключем.

Вказівки

Уявімо себе скарбниками на кораблі, які ведуть облік запасів у коморі. Інвентар - хеш-таблиця, у якій ключами є назви предметів, а значеннями - їхня кількість на складі.

1. Створити інвентар з масиву

Визначмо create-inventory, яка приймає послідовність назв предметів і повертає хеш-таблицю, що зіставляє кожну унікальну назву з її кількістю.

{ "coal" "wood" "wood" "diamond" "diamond" "diamond" } create-inventory .
! => H{ { "coal" 1 } { "wood" 2 } { "diamond" 3 } }

2. Додати більше предметів

Визначмо add-items, яка приймає інвентар і послідовність предметів та повертає новий інвентар, у якому кількості збільшено на одиницю для кожного з перелічених предметів. Початковий інвентар не повинен змінюватися.

H{ { "coal" 1 } } { "wood" "iron" "coal" "wood" } add-items .
! => H{ { "coal" 2 } { "wood" 2 } { "iron" 1 } }

3. Зменшити кількості

Визначмо decrement-items, яка приймає інвентар і послідовність предметів та повертає новий інвентар, у якому кількості зменшено на одиницю для кожного з перелічених предметів. Кількості ніколи не повинні ставати меншими за нуль, а предмети, яких ще немає в інвентарі, слід пропустити (записи з відʼємними значеннями не додаються).

H{ { "coal" 3 } { "diamond" 1 } { "iron" 5 } }
{ "diamond" "coal" "iron" "iron" } decrement-items .
! => H{ { "coal" 2 } { "diamond" 0 } { "iron" 3 } }

4. Вилучити предмет повністю

Визначмо remove-item, яка приймає інвентар і предмет та повертає новий інвентар без цього предмета. Якщо предмета немає в інвентарі, повернімо незмінену копію.

H{ { "coal" 2 } { "wood" 1 } { "diamond" 2 } } "coal" remove-item .
! => H{ { "wood" 1 } { "diamond" 2 } }

5. Перелічити наявні предмети

Визначмо 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 } }
Редагувати через GitHub Посилання відкривається в новому вікні або вкладці
Factor Exercism

Час розпочати Комора скарбника?

Зареєструйтеся на Exercism, щоб вивчати й опановувати Factor, а також 47 концепцій163 вправи та справжнє наставництво від людей, і все це безкоштовно.