Справочник функций

Ваш аккаунт

Войти через: 
Забыли пароль?
Регистрация
Информацию о новых материалах можно получать и без регистрации:

Последние темы форума

Показать новые сообщения »

Почтовая рассылка

Подписчиков: 11634
Последний выпуск: 19.06.2015

Сравнение методов организации словарей.

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

  • Сортировка результата. Если результат должен быть отсортирован, хеш-таблицы представляются не вполне подходящими, поскольку их элементы заносятся в таблицу в порядке, определяемом только их хеш-значениями. Все обстоит совсем по-другому при работе с двоичными деревьями. При проходе дерева в обратном порядке мы получаем отсортированный список. Вот как это делается:
 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.
  • метод операторы среднее время время в худшем случае
    хеш-таблицы 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приводится среднее время вставки, поиска и удаления 65,536 (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: Среднее время поиска (мсек)

    Оставить комментарий

    Комментарий:
    можно использовать BB-коды
    Максимальная длина комментария - 4000 символов.
     
    Реклама на сайте | Обмен ссылками | Ссылки | Экспорт (RSS) | Контакты
    Добавить статью | Добавить исходник | Добавить хостинг-провайдера | Добавить сайт в каталог