|
|
Cтруктуры данных. Хранение информации.
Сравнение методов
Мы рассмотрели несколько методов организации словарей: хеш-таблицы, несбалансированные двоичные деревья, красно-черные деревья и разделенные списки. Имеются несколько факторов, которые влияют на выбор алгоритма в конкретной ситуации:
-
Сортировка результата. Если результат должен быть отсортирован,
хеш-таблицы представляются не вполне подходящими, поскольку их элементы
заносятся в таблицу в порядке, определяемом только их хеш-значениями. Все
обстоит совсем по-другому при работе с двоичными деревьями. При проходе
дерева в обратном порядке мы получаем отсортированный список. Вот как это
делается:
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.
-
Время. Алгоритм должен быть эффективным. Это особенно важно, когда
ожидаются большие объемы данных. В таблице 2 сравниваются времена поиска
для каждого алгоритма. Обратите внимание на то, что наихудшие случаи для
хеш-таблиц и разделенных списков чрезвычайно маловероятны. Экспериментальные
данные описаны ниже.
-
Простота. Если алгоритм короток и прост, при его реализации и/или
использовании ошибки будут допущены с меньшей вероятностью. Кроме того,
это облегчает проблемы сопровождения программ. Количества операторов, исполняемых
в каждом алгоритме, также содержатся в таблице 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) |
Таблица 2: Сравнение алгоритмов ведения словарей
В таблице 3 приводится среднее время вставки, поиска и удаления 65,536
(216) случайных элементов. В этом эксперименте размер хеш-таблицы
равнялся 10009, для слоёных списков допускалось до 16 слоев. Хотя некоторое
различие времен для этих четырех методов и наблюдается, результаты достаточно
близки, так что для выбора алгоритма нужны какие-то другие соображения.
| метод |
вставка |
поиск |
удаление |
| хеш-таблицы |
18 |
8 |
10 |
| несбалансированные деревья |
37 |
17 |
26 |
| красно-черные деревья |
40 |
16 |
37 |
| разделенные списки |
48 |
31 |
35 |
Таблица 3: Среднее время (мсек) для 65536 случайных элементов
В таблице 4 приведены средние времена поиска для двух случаев: случайных
данных, и упорядоченных, значения которых поступали в возрастающем порядке.
Упорядоченные данные являются наихудшим случаем для несбалансированных
деревьев, поскольку дерево вырождается в обычный односвязный список. Приведены
времена для "одиночного" поиска. Если бы нам понадобилось найти все 65536
элементов, то красно-черныму дереву понадобилось бы .6 секунд, а несбалансированному - около 1 часа.
случайные
данные |
Кол-во элементов |
хеш-таблицы |
несбаланс. деревья |
красно-черные деревья |
слоёные списки |
| 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 |
Таблица 4: Среднее время поиска (мсек)
 Вверх по странице, к оглавлению и навигации. | |
