Сравнение методов организации таблиц

В малых таблицах средняя длина поиска приблизительно одинакова для всех методов (табл. 5.1, столбец m=8).

Поэтому для малого числа элементов предпочтительнее линейные таблицы (алгоритм проще, быстрее по времени). Для удаления элементов удобнее списки.

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

Таблица 5.1

Сравнение таблиц по длине поиска

Вид таблицы	Средняядлина поиска (m– количество элементов)
	Формула дляDср	m = 8	m = 64	m= 1024
Линейная	m / 2
Древовидная	1.39 log2m	4.2	8.4	13.9
Перемешаннаяпри N=1.25 m, s=0.8	(2-s) / (2-2*s) Dср = 3

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

Граница между малыми и большими таблицами зависит от ЭВМ, длины ключа и других факторов и соответствует обычно значению m от 30 до 80.

Упражнения и задачи

5.1. Составить полные программы по алгоритмам, приведенным в примерах 5.1, 5.2.

5.2. Составить фрагменты программ поиска без использования барьера для линейных таблиц в виде вектора и списка и древовидных таблиц.

5.3. Оформить приведенные в разделе 5 операции над таблицами в виде подпрограмм.

5.4.Написать программу подсчета количества повторений в данном тексте каждой цифры: 0, 1, … , 9.

5.5. В пустую таблицу поступают ключи в следующем порядке: МГУ, ЛГУ, КАИ, ТГУ, КГПУ, ТПИ, НГТУ. Изобразить результирующее дерево поиска и представление в памяти этого дерева с помощью параллельных массивов. Является ли полученное дерево выровненным, АВЛ-деревом? Указать последовательность ключей при обходе этого дерева сверху, слева направо и снизу (см. раздел 4). Как изменится таблица после удаления ключа ЛГУ?

5.6. В пустую таблицу поступают ключи в следующем порядке: МГУ, ЛГУ, КАИ, ТГУ, КГПУ, ТПИ, НГТУ. Для хеш-таблицы с открытым перемешиванием показать содержимое отображающего вектора (расстановочного поля), если его длина равна 9, шаг перемешивания равен 2. Хеш-функция определена таблично:

Ключ	КАИ	КГПУ	ЛГУ	МГУ	НГТУ	ТГУ	ТПИ
Значение хеш-функции

Как изменится таблица после удаления ключа ЛГУ?

5.7. Древовидная таблица содержит ключи (в порядке поступления): МГУ, ЛГУ, КАИ, ТГУ, КГПУ, ТПИ, НГТУ. Найти среднюю длину поиска для дерева полученной конфигурации, считая, что вероятности поиска всех ключей одинаковы и равны 0.1, а вероятность безуспешного поиска (отсутствующего ключа) равна 0.3. Считать, что безуспешный поиск с равной вероятностью заканчивается в любой из пустых ссылок.

Для сравнения оценить длину поиска в таблице в среднем по всем конфигурациям дерева, считая их равновероятными, по общей формуле:

древ

Dср = 1.39 log2 m,

где m — количество элементов таблицы.

5.8. Таблица содержит ключи (в порядке поступления): МГУ, ЛГУ, КАИ, ТГУ, КГПУ, ТПИ, НГТУ.

Даны вероятности:

— безуспешного поиска — 0.1;

— поиска ключей: КАИ — 0.3, КГПУ — 0.1, ЛГУ — 0.1,

МГУ — 0.15, НГТУ — 0.1, ТГУ — 0.1, ТПИ — 0.05 .

Найти среднюю длину поиска для разных методов организации таблиц:

1)линейная таблица с расположением ключей в порядке их поступления;

2)линейная таблица с расположением ключей в лексикографическом порядке (как в словарях);

3)линейная таблица с расположением ключей в порядке убывания вероятностей их поиска;

4)древовидная таблица с расположением ключей в порядке их поступления;

5)перемешанная таблица из задачи 4.3 (рис. 4.2а);

6)перемешанная таблица из 7 элементов с расстановочным полем длиной 9 и равномерно распределенной функцией расстановки (как на рис. 4.2а, только без учета конкретных ключей и их вероятностей).

5.9. Составить фрагменты программы (подпрограммы) включения и исключения элемента в упорядоченной по возрастанию ключей линейной таблице в виде вектора. Ключ элемента — вещественное число.

5.10. Составить фрагменты программы (подпрограммы) инициализации и поиска с включением в древовидной таблице без использования барьера для представления дерева

а) ссылочными данными;

б) параллельными массивами.

5.11. Для перемешанной таблицы cоставить фрагменты программы (подпрограммы)

а) поиска с включением открытым перемешиванием с квадратичным рехешированием;

б) инициализации, поиска, включения и удаления для разрешения конфликтов с помощью списков конфликтующих ключей.

5.12. Для перемешанной таблицы длиной n = 2k cоставить подпрограмму вычисления индекса p повторного перемешивания, используя псевдослучайное число r с начальным значением 1, по следующему методу:

r = младшие к+2 бита 5*r;

p = r, сдвинутое на 2 бита вправо.

5.13. Оценить необходимый объем памяти для организации таблиц в задачах: 5.4 — 5.6, 5.8 — 5.11. Недостающие детали представления уточнить самостоятельно.

Статьи к прочтению:

Сравнение 1 и 9 классов mp4

Похожие статьи: