Сравнение методов

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

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

 void WalkTree(Node *P) {

     if (P == NIL) return;

     WalkTree(P-Left);

     /* Здесь исследуем P-Data */

     WalkTree(P-Right);

 }

 WalkTree(Root);

Чтобы получить отсортированный список узлов разделенного списка, достаточно пройтись по ссылкам нулевого уровня. Вот так:

Node *P = List.Hdr-Forward[0];

while (P != NIL) {

    /* Здесь исследуем P-Data */

    P = P-Forward[0];

}

Память. Минимизация памяти, которая уходит на "накладные расходы", особенно важна, когда нужно хранить много маленьких узлов.

Для хеш-таблиц требуется только один указатель на узел. Кроме того, требуется память под саму таблицу.

Для красно-черных деревьев в каждом узле нужно хранить ссылку на левого и правого потомка, а также ссылку на предка. Кроме того, где-то нужно хранить и цвет узла! Хотя на цвет достаточен только один бит, из-за выравнивания структур, требуемого для эффективности доступа, как правило, будет потрачено больше места. Таким образом, каждый узел красно-черного дерева требует памяти, которой хватило бы на 3-4 указателя.

Для разделенных списков в каждом узле имеется ссылка нулевого уровня. Вероятность иметь ссылку уровня 1 равна 1/2. Вероятность иметь ссылку уровня 2 равна 1/4. В общем, количество ссылок на узел равно

n = 1 + 1/2 + 1/4 + ... = 2.

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

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

Таблица 3.2. Сравнение алгоритмов ведения словарей

В таблице 3-3приводится среднее время вставки, поиска и удаления 65,536 (2¹⁶) случайных элементов. В этом эксперименте размер хеш-таблицы равнялся 10009, для слоёных списков допускалось до 16 слоев. Хотя некоторое различие времен для этих четырех методов и наблюдается, результаты достаточно близки, так что для выбора алгоритма нужны какие-то другие соображения.

Таблица 3.3. Среднее время (мсек) для 65536 случайных элементов

В таблице 3.4 приведены средние времена поиска для двух случаев: случайных данных, и упорядоченных, значения которых поступали в возрастающем порядке. Упорядоченные данные являются наихудшим случаем для несбалансированных деревьев, поскольку дерево вырождается в обычный односвязный список. Приведены времена для "одиночного" поиска. Если бы нам понадобилось найти все 65536 элементов, то красно-черному дереву понадобилось бы .6 секунд, а несбалансированному - около 1 часа.

Таблица 3.4. Среднее время поиска (мсек.)

Внешняя сортировка

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

Проще всего отсортировать файл так: загрузить его, отсортировать его в памяти, затем записать результат. Если файл настолько велик, что загрузить его в оперативную память не удается, приходится применять разнообразные методы внешней сортировки. Мы рассмотрим здесь внешнюю сортировку, использующую выбор с замещением для получения начальных отрезков, за которым следует многофазное слияние для слияния отрезков в один отсортированный файл. Очень рекомендую книжку Кнута [1998]