Поиск по сайту.


Другие алгоритмы.

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: Среднее время поиска (мсек)

 





Вверх по странице, к оглавлению и навигации.