9. Чтобы заменить деление па сдвиг, нужно пронницнализировать переменные следующим образом:
goal = n/m binshift = 1
for (i = 2, i < goa1. i*=2)
binshif t + + nbi ns = 1+ ( n >> bi nsh i ft)
Функция вставки начинает проход с узла
р = &(b1n[t>>b1nsh1 ft])
10. Для представления случайных наборов можно применять различные структуры. Поскольку мы имеем полную информацию о статистическом распределении данных по корзинам, можно воспользоваться идеями из раздела 13.2 и представлять данные в большинстве корзин с помощью небольшого массива (если корзина переполняется, лишние элементы помещаются в связанный список). Д. Кпут предложил для этой задачи в колонке «Programming Pearls» за май 1986 года «упорядоченную таблицу хэширования», в качестве иллюстрации к его системе документирования программ на языке Паскаль. Эта статья включена в качестве главы 5 в его книгу «Literate programming».
Решения к главе 14
1. Выполнение функции siftdown может быть ускорено вынесением операций с временной переменной из цикла. Функцию siftup можно ускорить вынесением кода из циклов и добавлением маркерного элемента в х[0] для устранения проверки if i==l.
2. Новая версия siftdown имеет лишь небольшие отличия от приведенной в тексте. Присваивание i=l заменяется на Ы, а сравнения с п заменяются на сравнения с и. Время выполнения получившейся функции будет равно (3(Iog и - log /). Приведенный ниже код строит кучу за время О(п):
for ( 1 = п-1 . 1 >= 1 . 7 - - )
/* инвариант maxheap(i+1, n) */ siftdown(i, n)
/* maxheap(i , n) */
Поскольку высказывание maxheap (I, n) верно для всех чисел 1>п/2, границу п-1 в цикле for можно заменить на п/2.
Опубликовал vovan666
April 17 2013 00:07:08 ·
0 Комментариев ·
3706 Прочтений ·
• Не нашли ответ на свой вопрос? Тогда задайте вопрос в комментариях или на форуме! •
Комментарии
Нет комментариев.
Добавить комментарий
Рейтинги
Рейтинг доступен только для пользователей.
Пожалуйста, залогиньтесь или зарегистрируйтесь для голосования.
Нет данных для оценки.
Гость
Вы не зарегистрированны? Нажмите здесь для регистрации.
Главная
Каталог файлов
