Як немає єдино правильного способу розставити книги на полиці, так немає й універсального рішення для зберігання інформації в комп’ютері. Коли ви створюєте новий файл, машина повинна швидко знайти місце. Коли захочете видалити — швидко знайти потрібні біти. Дослідники прагнуть проєктувати системи зберігання, які називаються структурами даних, які балансують між часом додавання даних, часом їх видалення та обсягом необхідної пам’яті.
Уявіть, що всі ваші книги стоять у ряд на одній довгій полиці. Якщо вони розставлені за абеткою, знайти потрібну легко. Але кожну нову книгу доведеться довго влаштовувати на своє місце. А якщо ставити книги абияк, ви заощадите час зараз, але потім намучаєтеся з пошуком. Для невеликої бібліотеки це не проблема, але уявіть тисячі томів.
Можна зробити інакше: завести кошики з літерами алфавіту і розкладати книги за першою літерою прізвища автора. Нова книга миттєво вирушає у потрібний кошик, і ви одразу знаєте, де шукати. Але і тут є каверза: миттєвий пошук працює, тільки якщо в кожному кошику по одній книзі. В екстремальному випадку, коли всі ваші книги написані письменниками прізвище яких починається на одну літеру, ви знову отримаєте одну довгу полицю, а решта кошиків захаращуватиме вітальню.
Комп’ютерні вчені вивчають структури даних під назвою хеш-таблиці — більш витончені версії такої системи кошиків. Хеш-таблиця обчислює адресу зберігання кожного елемента з урахуванням її відомої властивості — ключа. У нашому прикладі ключем була перша буква прізвища, але це дуже просто: одні кошики переповняться, інші залишаться порожніми (мало англомовних авторів із прізвищем на X, наприклад). Краще взяти повне ім’я автора, замінити кожну букву числом, що відповідає її позиції в алфавіті, скласти всі числа та розділити суму на кількість літер в абетці. Залишок – число від нуля до останньої цифри абетки – вкаже номер кошика. Таке математичне правило перетворення ключа на адресу зберігання називається хеш-функцією. Грамотно спроєктована хеш-функція розподіляє елементи відносно рівномірно, тому шукати в кожному кошику доведеться менше.
Хочете прискорити пошук – додайте більше кошиків. Але вони займуть місце навіть якщо залишаться порожніми. Цей компроміс між простором і часом — невіддільна властивість хеш-таблиць, плата за звільнення від напруги між часом вставки та вилучення, яке переслідує простіші структури даних. Через понад 70 років після винаходу хеш-таблиць вчені продовжують відкривати нове про їх фундаментальні властивості. Нещодавно їм вдалося створити версію з ідеальним балансом простору та часу. А минулого року студент спростував давню гіпотезу про мінімальний час пошуку елемента у майже заповненій хеш-таблиці.
Хеш-таблиці хороші, коли не можна передбачити, які дані знадобляться. Але так не завжди. Подайте список справ, який постійно поповнюється завданнями з різними термінами. Вам потрібно швидко додавати нові пункти, але витягувати лише тоді, коли вони стають головним пріоритетом.
Тут допоможе структура даних під назвою купа (heap). Як випливає з назви, це дещо хаотичний підхід до зберігання даних — по суті, математична версія купи речей: одні елементи зберігаються вище за інші, і до них простіше дістатися. Елемент із найвищим пріоритетом завжди на вершині його можна миттєво зняти. Нижні шари менш упорядковані, але вам і не потрібно турбуватися про відносне розташування низькопріоритетних елементів.
Найпростіша реалізація використовує математичний об’єкт — бінарне дерево: мережа вузлів особливої форми, де один вузол нагорі, а від кожного вузла відходять два нижні. Подайте бінарне дерево зі списком справ. Кожен вузол зберігає одне завдання з номером, що означає термін. Що пріоритет — то менше число.
Новий елемент потрапляє у порожній слот на нижньому поточному рівні. Потім його термін порівнюється з терміном елемента у вузлі прямо з нього. Якщо нове завдання термінове — вони міняються місцями. Перестановки продовжуються, поки завдання не виявиться прямо під терміновою.
Ця процедура гарантує, що елемент із найвищим пріоритетом завжди спливе нагору. І вона дуже швидка: навіть у кошмарному сценарії з тисячею завдань у списку та постійним потоком нових кожен новий елемент вимагатиме не більше дев’яти перестановок. Коли ви завершуєте найтерміновішу задачу і видаляєте її з купи, новий головний пріоритет швидко підіймається з рівня нижче.
Купи широко застосовуються в алгоритмах пошуку найкоротшого шляху від заданої початкової точки в мережі до решти всіх точок. У 2024 році команда дослідників використовувала дотепну нову конструкцію купи, щоб перетворити класичний алгоритм пошуку найкоротших шляхів на теоретично оптимальний для будь-якої структури мережі.
Книг із суперечливими порадами про найкращий спосіб організувати речі вистачає. Якщо комп’ютерна наука чогось і вчить, то це тому, що ідеального рішення не існує — кожен підхід має свої компроміси. Але якщо одні речі для вас важливіші за інші, не бійтеся залишити трохи безладу.
Більше цікавого:
- Як комп’ютерна модель 1970-х спрогнозувала загибель людства у XXI столітті
- Кубіт: серце квантового комп’ютера
- Історія двійкового коду: як нулі та одиниці визначили долю людства
Джерело: QuantaMagazine