1. В решении задачи 9 из предыдущей главы описан алгоритм получения упорядоченного набора целых чисел, придуманный Бобом Флойдом. Можете
ли вы реализовать его алгоритм с помощью структур IntSet, описанных в этой книге? Насколько удачно эти структуры работают с неслучайными распределениями, порождаемыми алгоритмом Флойда?
2. Как бы вы изменили упрощенный интерфейс класса IntSet, чтобы сделать его более надежным?
3. Добавьте к классам функцию find, позволяющую определить, присутствует ли некоторый элемент в сииске. Можете ли вы реализовать эту функцию так, чтобы она работала быстрее, чем insert?
4. Перепишите функции вставки для списков, корзин и двоичных деревьев, заменив рекурсию итерацией. Затем измерьте разницу во времени выполнения.
5. В разделе 9.1 главы 9 и решении задачи 9 из топ же главы описан способ Криса Ван Вайка, использованный им для уменьшения количества обращений к подсистеме выделения памяти. Он создавал собственную структуру, в которой хранил указатели на доступные узлы. Покажите, как можно применить эту идею к структурам IntSet, реализованным через списки, корзины и двоичные деревья.
6. Что даст вам измерение времени работы приведенного ниже фрагмента кода для различных реализаций класса IntSet?
IntSetlmp S(m. n) r
for (i nt i * 0: i < mr i ++)
S.insert(i ),
7. В наших реализациях с массивами, списками и корзинами используются элементы-маркеры. Покажите, как этот метод можно применить к двоичным деревьям поиска.
8. Покажите, как можно ускорить операции инициализации и перечисления элементов для битовых векторов, используя параллельность одновременных операций с несколькими битами. С каким из типов данных программа работает быстрее всего: char, short, int, Long или с каким-нибудь другим?
9. Покажите, как можно ускорить работу корзин, заменив дорогостоящий оператор деления на более дешевый логический сдвиг.
10. Какие еще структуры можно использовать для представления наборов целых чисел в задаче о генерации случайной выборки?
11. Постройте самую быструю функцию для получения упорядоченного набора случайных целых чисел без повторений. Чувствуйте себя свободным от любых ограничений на вид интерфейса представления наборов.
13.7. Дополнительная литература
Отличные учебники Кнута и Седжвика но теории алгоритмов описаны в разделе 11.6. Поиск является предметом исследования главы 6 (второй половины) книги Кнута «Сортировка и поиск» и четвертой (последней) части книги Седжвика «Алгоритмы».
Главная
Каталог файлов
