Итак, список покупок из простого перечня пунктов становится списком категорий, причем каждая из них, в свою очередь, представляет собой список пунктов.[43] Поскольку продукты в магазине обычно группируются по категориям, Вурзма может просто отправиться в ту часть магазина, где находятся, например, предметы личной гигиены, пробежаться по массиву под названием «личная гигиена» и взять нужные ему вещи со стеллажа. То же самое – для всех остальных покупок. Вот как занимаются шопингом по методу 2. Если бы Вурзма использовал обычный список – массив, как в методе 1, то он бы бродил примерно 13 минут от одного ряда к другому, в худшем случае – просто изучая полки.

Вурзма проходит мимо всех стеллажей для покупки одного предмета из списка. Если n – число проходов, а m – количество пунктов в списке, тогда n/2 × m=(nxm/2). Иными словами, для покупки 20 вещей Вурзма проходит через 20 рядов 20 раз. Принимая во внимание, что для прохождения каждого ряда требуется 2 секунды, то потерянное время составит до 13 минут. С методом 2 его общее время на ходьбу между рядами составляет примерно минуту, так как он не появляется в одном и том же ряду больше одного раза. Вурзма в лучшем случае проходит все ряды один раз, то есть n/2. Так что для приобретения 20 наименований покупок Вурзма, идя от одного ряда к другому, теряет меньше минуты.

Заметьте, что метод 1 не выглядит в точности как сортировка по квадратичному времени, которую мы видели в главах 5 и 11. Он следует шаблону, заставляя Вурзму в худшем случае пройти по всем рядам в магазине для каждой покупки в его списке. Вот как сравниваются два метода:

В главе 1 мы говорили о хеш-таблицах и о том, как они полезны, когда нам нужно провести быстрый обзор и не беспокоиться о порядке. Разговор о многомерных массивах дает нам прекрасную возможность расширить наше знание о хеш-таблицах. Раньше мы принимали на веру, что хеш-функция всегда отмечает позицию элемента, назначая ему уникальное местоположение в хеш-таблице, и именно благодаря этому гарантируется его быстрое нахождение в любое время. В реальности хеш-функция может столкнуться с таким явлением, как коллизия, при которой соответствующее место в хеш-таблице уже занято другим элементом. Это происходит либо потому, что хеш-функция неидеальна, то есть не работает правильно и не обеспечивает единообразного распределения значений хеш-функции, либо у нас больше элементов для хранения, чем может вместить таблица. Степень заполнения хеш-таблицы называется коэффициентом заполнения и равна нулю, когда хеш-таблица пуста, или единице, когда она заполнена.

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

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

Нужно подчеркнуть еще одну вещь: многомерный массив заранее навязывает нашим элементам приоритет, а именно – расстояние от входа магазина до конкретного ряда, где находится нужная вам вещь. Возможно, пора расширить наши знания об очередях с приоритетом, о которых мы упоминали мимоходом в главе 8. Там мы говорили, что, когда вы составляете некий приоритизированный список элементов, а после нужно добавить к нему новый элемент, может понадобиться стереть некоторые части списка, чтобы освободить место. Довольно скоро дело заходит в тупик, и вы обнаруживаете, что нужно делать новый список. Как может машина составить такой список с эффективностью, которую мы ждем от нее?

Мы уже видели структуры, оптимизированные для быстрого просмотра (массивы) и вставки элементов в произвольных точках (связные списки). Теперь подробнее рассмотрим очередь с приоритетом, которая оптимизирована для добавления элемента высшего приоритета[44] к коллекции в логарифмическое время. Она называется очередью, даже если не является таковой в привычном представлении, то есть когда первый предмет, вставший в очередь, первым же из нее выходит.[45] Вместо этого вы можете представить очередь с приоритетом как некое подземное растение, которое пускает только один побег за один раз и позволяет проходящим мимо людям сорвать его.

Когда мы принимаемся за задание высшего приоритета, дерево перестраивается и выталкивает наверх задание второй приоритетности, и так далее. Этот способ описания очереди с приоритетом называется пирамидой. Мы не можем объяснить принцип пирамиды при помощи аналогии, но это замечательная структура. Нам стоит оценить, как она умеет перестроиться и вытолкнуть наверх элемент первоочередной приоритетности в логарифмическом времени, обеспечивая возникновение вставок также в логарифмическом времени.

Давайте смоделируем приоритизированный список в виде пирамиды.

Заметьте, что пирамида представляет собой как бы дерево из узлов. У них есть две особенности. Первое: каждый узел имеет более низкий приоритет, чем родительский.[46] Поэтому пункт с самым большим приоритетом, то есть продукт, расположенный ближе всего ко входу в магазин, помещен на самом верху. Ничего больше не сообщается о порядке других узлов, таких как узлы, которые находятся на одном уровне. Есть другие структуры, они гарантируют, что все узлы в древоподобной структуре упорядочиваются, как бинарное дерево поиска, полезное в ситуациях, которые мы описывали в главе 2.