Целью данной работы является сравнение следующих подходов:
- Квадратичный подход к построению идеальной хеш-таблицы; (см. Кормен, 3-е издание, 11.5 Идеальное хеширование, или видео запись)
- Двух-уровневый подход к построению идеальной хеш-таблицы; (см. Кормен, 3-е издание, 11.5 Идеальное хеширование, или видео запись)
- (опционально) Графовый подход к построению идеальной хеш-таблицы (см. https://habrahabr.ru/post/254431/, вот исходная статья, обязательно посмотрите http://cmph.sourceforge.net/papers/chm92.pdf). Что измеряется?
- Время построения хеш-таблицы;
- Время операции поиска элемента;
- Затрачиваемая память Замечание: В качестве хеш-функций используйте только функции из универсальных семейств, про них рассказывалось на семинарах. Список универсальных хеш-функций можно найти здесь https://en.wikipedia.org/wiki/Universal_hashing. Замечание: Для двух-уровневой хеш-таблицы нужно обязательно провести эксперименты с разлиными значениями параметров, разобраться как различные значения параметров влияют на производительность и найти оптимальный выбор параметров. Без этих экспериментов работа не будет зачтена. Про какие именно параметры идет речь смотрите в записи лекции. Входные данные: a) Случайные натуральные числа. б) Случайные вектора или строки. с) Очень бы хотелось увидеть как поведут себя таблицы на real life данных, например на словарях или словах какого нибудь литературного произведения. Ваш вывод должен содержать:
- Графики сравнения скорости построения и количества занимаемой памяти для подхода 1) при различных значениях параметров. Выбор оптимального, с Вашей точки зрения, набора параметров.
- График сравнения скорости построения хеш-таблиц для подходов 1) 2) 3), причем для подхода 2) нужно использовать оптимальный набор параметров.
- График сравнения скорости поиска для обоих подходов.
- Все графики нужно продублировать, если Вы используете разные входные данные: случайные строки и real life данные. Итого, должно быть как минимум 4 картинки с несколькими кривыми на каждой.
Целью данной работы является сравнение различных методов борьбы с коллизиями:
- Метод цепочек;
- Метод открытой адресации (см. Кормен, 3-е издание, 11.4 Открытая адреация);
- Метод кукушки (см. https://en.wikipedia.org/wiki/Cuckoo_hashing).
- Для интереса, предлагается также сделать сравнения со стандартными средствами языка c++: std::map, std::hash_map. Вдруг получится их обогнать. Замечание: В качестве хеш-функций используйте только функции из универсальных семейств, про них рассказывалось на семинарах. Список универсальных хеш-функций можно найти здесь https://en.wikipedia.org/wiki/Universal_hashing. Что измеряется?
- Время вставки;
- Время удаления;
- Время поиска. Более конкретно об измерении: Нужно выбрать какое-то стартовое значение N, скажем 100, выбрать шаг step, скажем пусть step = 100, и выбрать максимальное значение, скажем 100 000. После чего нужно для каждого N с шагом step от минимального значения до максимального построить таблицу размера N (из случайных элементов, или сделать выборку из заранее подготовленной базы) и произвести одну или несколько операций (если несколько, скажем 10, то нужно усреднить). Измеряем именно время одной операции. Некоторые допускают ошибку и делают N вставок с замером времени, но не понятно, что в итоге Вы измерили. Входные данные: a) Случайные натуральные числа. б) Случайные вектора или строки. с) Очень бы хотелось увидеть как поведут себя таблицы на real life данных, например на словарях или словах какого нибудь литературного произведения. Ваш вывод должен содержать:
- График зависимости скорости вставки от количества элементов в таблице;
- График зависимости скорости удаления от количества элементов в таблице;
- График зависимости скорости поиска от количества элементов в таблице; На каждом графике должно быть несколько кривых, по одной или больше для каждого подхода. Заметим также, что таблицы из подходов 1) и 2) имеют дополнительный параметр m – ёмкость таблицы. Хорошо бы построить на графиках кривые для разных значений m, например m = 2n, m = n, m = ½ n. Но это не обязательно.