Эффект Азимова. Почему хранить всё по алфавиту — это плохая идея (для компьютера)

Как нет единственно правильного способа расставить книги на полке, так нет и универсального решения для хранения информации в компьютере. Когда вы создаёте новый файл, машина должна быстро найти для него место. Когда захотите удалить — быстро отыскать нужные биты. Исследователи стремятся проектировать системы хранения, называемые структурами данных, которые балансируют между временем добавления данных, временем их удаления и объёмом необходимой памяти.

Представьте, что все ваши книги стоят в ряд на одной длинной полке. Если они расставлены по алфавиту, найти нужную легко. Но каждую новую книгу придётся долго пристраивать на своё место. А если ставить книги куда попало, вы сэкономите время сейчас, но потом намучаетесь с поиском. Для небольшой библиотеки это не проблема, но представьте тысячи томов.

Можно поступить иначе: завести 26 корзин с буквами алфавита и раскладывать книги по первой букве фамилии автора. Новая книга мгновенно отправляется в нужную корзину, и вы сразу знаете, где искать. Но и тут есть подвох: мгновенный поиск работает, только если в каждой корзине по одной книге. В экстремальном случае, когда все ваши книги написаны Азимовым, Этвуд и Остин, вы снова получите одну длинную полку, а остальные корзины будут захламлять гостиную.

Компьютерные учёные изучают структуры данных под названием хеш-таблицы — более изощрённые версии такой системы корзин. Хеш-таблица вычисляет адрес хранения для каждого элемента на основе его известного свойства — ключа. В нашем примере ключом была первая буква фамилии, но это слишком просто: одни корзины переполнятся, другие останутся пустыми (мало англоязычных авторов с фамилией на X, например). Лучше взять полное имя автора, заменить каждую букву числом, соответствующим её позиции в алфавите, сложить все числа и разделить сумму на 26. Остаток — число от нуля до 25 — укажет номер корзины. Такое математическое правило преобразования ключа в адрес хранения называется хеш-функцией. Грамотно спроектированная хеш-функция распределяет элементы относительно равномерно, так что искать в каждой корзине придётся меньше.

Хотите ускорить поиск — добавьте больше корзин. Но они займут место, даже если останутся пустыми. Этот компромисс между пространством и временем — неотъемлемое свойство хеш-таблиц, плата за избавление от напряжения между временем вставки и извлечения, которое преследует более простые структуры данных. Спустя более 70 лет после изобретения хеш-таблиц учёные продолжают открывать новое об их фундаментальных свойствах. Недавно им удалось создать версию с идеальным балансом пространства и времени. А в прошлом году студент опроверг давнюю гипотезу о минимальном времени поиска элемента в почти заполненной хеш-таблице.

Хеш-таблицы хороши, когда нельзя предугадать, какие данные понадобятся следующими. Но так бывает не всегда. Представьте список дел, который постоянно пополняется задачами с разными сроками. Вам нужно быстро добавлять новые пункты, но извлекать — только когда они становятся главным приоритетом.

Здесь поможет структура данных под названием куча (heap). Как следует из названия, это несколько хаотичный подход к хранению данных — по сути, математическая версия кучи вещей: одни элементы хранятся выше других, и до них проще добраться. Элемент с наивысшим приоритетом всегда на вершине — его можно мгновенно снять. Нижние слои менее упорядочены, но вам и не нужно беспокоиться об относительном расположении низкоприоритетных элементов.

Простейшая реализация использует математический объект — бинарное дерево: сеть узлов особой формы, где один узел наверху, а от каждого узла отходят два нижних. Представьте бинарное дерево со списком дел. Каждый узел хранит одну задачу с номером, обозначающим срок. Чем выше приоритет — тем меньше число.

Новый элемент попадает в пустой слот на текущем нижнем уровне. Затем его срок сравнивается со сроком элемента в узле прямо над ним. Если новая задача срочнее — они меняются местами. Перестановки продолжаются, пока задача не окажется прямо под более срочной.

Эта процедура гарантирует, что элемент с наивысшим приоритетом всегда всплывёт наверх. И она очень быстрая: даже в кошмарном сценарии с тысячей задач в списке и постоянным потоком новых каждый новый элемент потребует не более девяти перестановок. Когда вы завершаете самую срочную задачу и удаляете её из кучи, новый главный приоритет быстро поднимается с уровня ниже.

Кучи широко применяются в алгоритмах поиска кратчайшего пути от заданной начальной точки в сети до всех остальных точек. В 2024 году команда исследователей использовала остроумную новую конструкцию кучи, чтобы превратить классический алгоритм поиска кратчайших путей в теоретически оптимальный для любой структуры сети.

Книг с противоречивыми советами о лучшем способе организовать вещи хватает. Если компьютерная наука чему-то и учит, так это тому, что идеального решения не существует — у каждого подхода свои компромиссы. Но если одни вещи для вас важнее других, не бойтесь оставить немного беспорядка.