Сравнение методов организации таблиц
В малых таблицах средняя длина поиска приблизительно одинакова для всех методов (табл. 5.1, столбец m=8).
Поэтому для малого числа элементов предпочтительнее линейные таблицы (алгоритм проще, быстрее по времени). Для удаления элементов удобнее списки.
В больших таблицах самый быстрый поиск дают методы хеширования. Если они неудобны по каким-то причинам (требуется упорядоченная распечатка, частые удаления, трудно найти подходящую функцию расстановки или предугадать размер таблицы), используют древовидные таблицы, возможно с балансировкой.
Таблица 5.1
Сравнение таблиц по длине поиска
| Вид таблицы | Средняя длина поиска (m – количество элементов) | |||
| Формула для Dср | m = 8 | m = 64 | m= 1024 | |
| Линейная | m / 2 | |||
| Древовидная | 1.39 log2 m | 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. Недостающие детали представления уточнить самостоятельно.