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