3.5 Сравнение методов

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

• Сортировка результата. Если результат должен быть отсортирован, хеш-таблицы представляются не вполне подходящими, поскольку их элементы заносятся в таблицу в порядке, определяемом только их хеш-значениями. Все обстоит совсем по-другому при работе с двоичными деревьями. При проходе дерева в обратном порядке мы получаем отсортированный список. Вот как это делается:

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 сравниваются времена поиска для каждого алгоритма. Обратите внимание на то, что наихудшие случаи для хеш-таблиц и разделенных списков чрезвычайно маловероятны. Экспериментальные данные описаны

п = 1 + - + -+ ■■■ = 2. 2 4

ниже.

• Простота. Если алгоритм короток и прост, при его реализации и/или использовании ошибки будут допущены с меньшей вероятностью. Кроме того, это облегчает проблемы сопровождения программ. Количества операторов, исполняемых в каждом алгоритме, также содержатся в таблице 3.2.

метод

операторы

среднее время

время в худшем случае

хеш-таблицы

26

0(1)

0(п)

несбалансированные деревья

41

0(18 п)

0(п)

красно-черные деревья

120

0(18 п)

0(18 п)

разделенные списки

55

0(18 п)

0(п)

Таблица 0.2: Сравнение алгоритмов ведения словарей

В таблице 3.3 приведены времена, требуемые для вставки, поиска и удаления 65536 (216) случайных элементов. В этих экспериментах размер хеш-таблицы равнялся 10009, для разделенных списков допускалось до 16 уровней ссылок. Конечно, в реальных ситуациях времена могут отличаться от приведенных здесь, однако, таблица дает достаточно информации для выбора подходящего алгоритма.

метод

вставка

поиск

удаление

хеш-таблицы

18

8

10

несбалансированные деревья

37

17

26

красно-черные деревья

40

16

37

разделенные списки

48

31

35

Таблица 0.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

Таблица 0.4: Среднее время поиска (мсек)