Лекция 13
Сравнение методов
Мы рассмотрели несколько методов организации словарей:
хеш-таблицы, несбалансированные двоичные деревья, красно-черные деревья и
разделенные списки. Имеются несколько факторов, которые влияют на выбор
алгоритма в конкретной ситуации:
Сортировка результата.
Если результат должен быть отсортирован, хеш-таблицы представляются не вполне
подходящими, поскольку их элементы заносятся в таблицу в порядке, определяемом
только их хеш-значениями. Все обстоит совсем по-другому при работе с двоичными
деревьями. При проходе дерева в обратном порядке мы получаем отсортированный
список. Вот как это
делается:
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. Сравнение алгоритмов ведения словарей
метод
|
операторы
|
среднее
время
|
время
в худшем случае
|
хеш-таблицы
|
26
|
O(1)
|
O(n)
|
несбалансированные
деревья
|
41
|
O(lg
n)
|
O(n)
|
красно-черные
деревья
|
120
|
O(lg
n)
|
O(lg
n)
|
разделенные
списки
|
55
|
O(lg
n)
|
O(n)
|
В таблице 3-3приводится среднее время вставки, поиска и
удаления 65,536 (216) случайных элементов. В этом эксперименте
размер хеш-таблицы равнялся 10009, для слоёных списков допускалось до 16 слоев.
Хотя некоторое различие времен для этих четырех методов и наблюдается,
результаты достаточно близки, так что для выбора алгоритма нужны какие-то
другие соображения.
Таблица 3.3. Среднее время (мсек) для 65536 случайных элементов
метод
|
вставка
|
поиск
|
удаление
|
хеш-таблицы
|
18
|
8
|
10
|
несбалансированные
деревья
|
37
|
17
|
26
|
красно-черные
деревья
|
40
|
16
|
37
|
разделенные
списки
|
48
|
31
|
35
|
В таблице 3.4 приведены средние времена поиска для двух
случаев: случайных данных, и упорядоченных, значения которых поступали в
возрастающем порядке. Упорядоченные данные являются наихудшим случаем для
несбалансированных деревьев, поскольку дерево вырождается в обычный односвязный
список. Приведены времена для "одиночного" поиска. Если бы нам понадобилось
найти все 65536 элементов, то красно-черному дереву понадобилось бы .6 секунд,
а несбалансированному - около 1 часа.
Таблица 3.4. Среднее время поиска (мсек.)
случайные
данные
|
Кол-во элементов
|
хеш-таблицы
|
несбаланс. деревья
|
красно-черные деревья
|
слоёные списки
|
16
|
4
|
3
|
2
|
5
|
256
|
3
|
4
|
4
|
9
|
4,096
|
3
|
7
|
6
|
12
|
65,536
|
8
|
17
|
16
|
31
|
упорядоченные данные
|
16
|
3
|
4
|
2
|
4
|
256
|
3
|
47
|
4
|
7
|
4,096
|
3
|
1,033
|
6
|
11
|
65,536
|
7
|
55,019
|
9
|
15
|
Внешняя сортировка
В предыдущих алгоритмах предполагалось, что все имеющиеся
данные помещаются в памяти. Однако, довольно часто данные слишком велики и для
работы с ними нужны адекватные методы. В данном разделе исследуются методы
сортировки (внешняя сортировка) и реализации словарей (Б-деревья) для такого
случая.
Проще всего отсортировать файл так: загрузить его,
отсортировать его в памяти, затем записать результат. Если файл настолько
велик, что загрузить его в оперативную память не удается, приходится применять
разнообразные методы внешней сортировки.
Мы рассмотрим здесь внешнюю сортировку, использующую выбор с замещением для получения
начальных отрезков, за которым следует многофазное слияние для слияния отрезков в один
отсортированный файл. Очень рекомендую книжку Кнута [1998]
|