AOP_Tom3 (1021738), страница 208
Текст из файла (страница 208)
В приведенном решении используются циклические списки, следуя предлоя»енню Аллена Ньювелла (АПеп ?эе»гей), с установления»м ТАС[»] = 1 в первол» слове каждого списка. А1. [И»»ицнализация.] Установить»» — 1» — 6(К) + 1, (]»- Ч(К). А2. [Это список?] Если ТАВЬЕ[П пуст, установить ТАСЯ» — 1 и перейти к шагу А8. В противном глучае, если ТАС [П = О, перейти к шагу А?, АЗ.
[Сравнение,] Если (» = ХЕТБ], алгоритм успешно завершается. А4. [Переход к следующему.] Если Ь1ИК[П ~ 1, установить»»- 1.1ИК[П н вернуться к шагу АЗ. А5. [Поиск пустого узла.] Уменьшить К один или несколько раз до тех пор, пока не будет найдено значение, такое, что ТАВЬЕ[К] пуст. Если К = О, алгоритм завершается после переполнения; в противном случае установить 11ИКЯ» — ](. Аб. [Подготовка к вставке.) Установить» +- ]1, ТАС[К] +- 0 и перейти к шагу АЗ.
АТ. [Перемещение записи.] Установить»» — ЬТИКЯ один нли несколько раз, пока не будет выполнено условие ЬТИКЯ = 1, Затем выполнить шаг А5 и установить ТАВЬЕ[В] +- ТАВ1.Е[»], »» — ], ТАС[]]»- 1. АВ. [Вставка нового ключа.] Пометить ТАВЬЕЯ как занятый узел с КЕТЯ» — (Ч, Ь1ИКЯ»- ]. ! (Зал»етые, что, если ТАВЬЕБ] занят, можно определить соответствующий полный ключ К по данно»»у значению». Имеем Ч(К) = КЕТ Я, а затем, несколько рвз присвоив»»- 1.1ИХ [»] до тех пор, пока не выполнится равенство ТАСЯ = 1, получим 6(К) = » — 1.) 14. Согласно указанным соглашениям запись "К ~ АЧА1Ь" иэ 2.2.3 — (б) теперь означает гледующее. "Установить Х» — АЧАП., присвоить К +- ЬТИК(Х) нуль илн несколько раз до 1 = А (ошибка переполнения) или до ТАС(Х) = 0 и наконец установить АЧАТЬ» — [ТИК(Х)." Для вставки нового ключа К: установить Ц ~ АЧА11, ТАС(С)»- 1 и сохранить К в этом слове.
(Можно также, если все ключи коротки, опустить этот шаг н заменить в дальнейших шагах О на К.) Затем установить Е ~ АЧАПо ТАСОХ) +- 1, АОХ(Е) + — Ц, 1.1ЯК(Е) +- Л. Присвоить Р +- )<(К), а затем, если ТАС(Р) = О, установить ТАС(Р) < — 2, АОХ(Р) <- Е; если ТАС(Р) = 1, установить Я ~ АЧАПь СОЯТЕЯТБ(Б) +- СОЯТЕЯТЯ(Р), ТАС(Р) <- 2, АСХ(Р) < — Е, 1.1ЯК(Р) +- Б, если ТАС(Р) = 2, установить 1.1КК(Е) +- АСХ(Р), АСХ(Р) +- Е. Для получения ключа К: установить Р < — Л(К) и, егли ТАС(Р) Ф 2, К отсутствует; если ТАС(Р) = 2, установить Р < — АСХ(Р), а затем присвоить Р <- ЫКК(Р) нуль или несколько раз до тех пор, пока не выполнится либо Р = Л, либо ТАС(Р) = 1, тогда либо АОХ(Р) = К (если все ключи коротки), либо АСХ(Р) указывает на слово, содержащее К (возможно, косвенно через слово с ТАС = 2).
В оригинальной схеме Элькока «Сотр ). В (1965), 242-243) в действительности исполь- зовались ТАС = 2 н ТАС = 3 для того, чтобы различить списки единичной длины (когда можно сохранить одно слово памяти) и более длинные списки. Это улучшение заслуживает внимания, поскольку мы предположительно работаем с такой большой хеш-таблицей, что почти все списки имеют единичные длины. Другой путь размещения хеш-таблицы "наверху" большой связанной памяти с исполь- зованием срастающихся списков вместо раздельных цепочек был предложен Дж.
С. Вит- тером (1 Я. ТЗ<ыег) [1пй Ргос. 1ешегз 13 (1981), 77 — 79«. 16. Зная о том, что всегда ииеется свободный узел, можно сделать внутренний цикл более быстрым, поскольку нег необходимости в счетчике для определения, сколько рэз был выполнен шаг 1.2 Более короткая программа компенсирует одну потерянную ячей- ку. (С другой стороны, в алгоритме Б изящно указывается, как избежать использования переменной Л< и допустить полное заполнение таблицы без заметного замедления работы метода (за исключением случая реального переполнения таблицы): просто проверка «О должна выполняться дважды! К алгоритму П этот трюк неприменим.) 16. Нет: О всегда приводит к метке ЯСССЕЯБ, независимо от того, был ли он вставлен.
В разные моменты мы попадаем на метку ЯСССЕББ с различными значениями <. 17. Тогда вторая проба всегда будет обращаться к позиции О. 18. "Стоимость" кода (31) на 3(А — 51) единиц больше, чем стоимость кода (ЗО); экономия при этом составляет 4и, умноженное на разность между (26), (27) и (28), (29).
В случае успешного поиска (31) предпочтительнее только тогда, когда таблица заполнена более чем иа 94%; выигрыш при этом не превь<шает -'и. В случае неудачного поиска (31) предпочтительнее, если таблица заполнена более чем на 71%. 20. !((ы хотим показать, что ( ) =( ) (помодулю2ж) и 1<) <А<2™ влечет )' = А. Заметим, что тождество у()' — 1) = А(А — 1) (ло модулю 2™+<) приводит к ()< — ))()с+) — 1) = О. Если /с — ) нечетно, /с+2 — 1 должно быть кратно 2"'+', но это невозможно, поскольку 2 < А + ) — 1 < 2 +' — 2.
Следовательно, lс — ) четно, так что Iс -!- З вЂ” 1 нечетно и /с — 2 кратно 2ш "', откуда А = ). (И обратно, егли М не является степенью 2, такая последовательность проб не будет работать.) Эта погледовательность проб имеет вторичную кластеризацию и приводит к увеличению времени работы программы () (модифицированной в соответствии с (ЗО)) примерно на -'(С вЂ” 1) — (А — В1) единиц, поскольку В (~з+')/М можно не принимать во внимание. Пока таблица ие заполнена примерно на 60%, это дает небольшое улучшение работы.
21. При уменьшении Х алгоритм П может некорректно работать, так как, достигнув состояния, в котором отсутствует пустое пространства, он зациклится. С другой стороны, если Ж не будет уменьшаться, алгоритм П может сообщить о переполнении при имеющемск свободном пространстве Причем этот вариант — меньшее из двух зол, поскольку дли освобождении от удаленных ячеек можно воспользоваться рехешированием (в этом случае алгоритм П должен увеличивать Х и проверять переполнение только при вставке элемента в пустую позицию, так как М вЂ” количество иепустых позиций).
В программе также можно поддерживать два счетчика. 22. Предповожим, что позиции 7' — 1, 7' — 2,, 2 — й заняты, а,у — й — 1 пуста по модулю М. Ключи, которые проверяют позицию 7 и находят ее завитой перед вставкой, совпадают с ключами в позицикх от 1 — 1 до 1' — Й, хеш-адреса которых не лежат между 7' -1 и 7'- й; такие "проблематичные" ключи поввляютск в порядке вставки. Алгоритм В перемещает первый такой ключ в позицию 2 и повторяет процесс на меньшем диапазоне проблематичных позиций до тех пор, пока будет оставаться хоть один проблематичный ключ.
23. Схема удаления для срастающихся цепочек, изобретенная Дж. С. Виттером (Л. Б. %Свет) (,Ь А!бог111илв 3 (1982), 2б1 — 275), сохраняет распределение времен поиска. 24. Р(Р— «(Р— 2)Р(Р-«Р(Р-1)((МР(МР— «... (МР-б)) = М ~(1-(5-217М)Р ~+ О(Р з)) В общем, вероятность появления хеш-последовательности а1 .. ал равна (П'ы ' х хР1 ))(МР)8 = М вЂ” л -~-0(Р-'), где Ь, — количество о„равных 7'. 25.
Пусть (Х + «-й ключ хешируетск в позицию а, Рв равно М 'ч, умноженному на количество хеш-последовательностей, которые оставляют к позиций а, а — 1,, а — й + 1 (по модулю М) занятыми, а а — й — пустой. Количество таких последовательностей с занятыми а-~-1,..., аЧ-Г и пустой а+1+1 равно д(М,Х,1+)г) в силу циклической симметрии алгоритма. 9! 26. —, ' 7(3,2)7(3,2)у(5,4)7(2, « = 2 3 5 7 = 4252500.
27. С,ледуя указанию, находим в(и,х,у) = ~ ~( )х(х+И) (у-й)™ 1(у — и)+и~ ( )(х+И)~(у — И)™ 1(у — и). ь ь В первой сумме заменим Ь на и — Ь и применим формулу Абеля; во второй заменим 8 на Й+ 1. Теперь ( 1(й+ «в-~(М й «л-в-1(М „ ~Й/ с О/О = 1 при й = Ф = М вЂ” 1 и Первая сумма равна М~ 2 Рь = М~, вторая — в(г7 1, М вЂ” « = М +21>М~ '+ЗХ(Х— «Мл + = Мл91(М, Ю).
(См. Л. Н1огдав, СошЬшасопв7 Иевсйбев (1эезг гог1г: Ъуйеу, 19б8), 18 — 23; здесь приводится дополнительная информация о суммах наподобие в(и, х, у).) 28. Пусть г(и, х, у) = 2,'ь>е (") (в+Ь)~т~(у — Ь)" '(у-и); тогда, как и в упр. 27, находим г(гд х, у) = хв(п, х, у) + иг(и-1, х+1, у — «, 1(Х, 1, М-« = М (ЗЦв(М, Х) — 2Яв(М Х)). Значит, ~ (й+ «Рв = М х (в(к+ «+ в(х+ «+ в(к+ «)9(М Х гг) = Яв(М А')— усгз(ЛГ,Аг) + ЧЯ~(М,/Ч) + -'.
Вычитание (Си) лает дисперсию, приближенно равную -„(1 — а) "— з(1 — а) з — —,' . Стандартное отклонение зачастую больше среднего значения, например при и = .9 среднее значение равно 50.5, а стандартное отклонение — -'Л7333 82.7. 29. Пусть М = гп + 1, Х = и; логледователыгость парковки та же, что и при применении алгоритма 1 к хеш-последовательности (М вЂ” а~)... (М вЂ” а„), при которой позиция О остается пустой. Следовательно, искомый ответ — /(го+1, и) = (т+ 1)" — п(го+ 1)" (Эта задача была поставлена в работе А. С. Ковйенп апб В. ъте!ээ, БАЛХ Х Арр!!ес! Маей.
14 (1966), 1266-1274; см. также В. РуЬе, Алла!э оГ Масб. аеас. 30 (1959), 568-576, лемма 1.] 30. Очевидно, что егчи машины припарковались, то они определяют такую перестановку. И обратно, если имеется перестановка р~рз ., р„, пусть 9~Чз .. Ч„означает обратную перестановку (Ч, = 2 тогда и только тогда, когда р, = ~) и пусть ܄— количество о„равных !. Каждый автомобиль припаркуется, если мы докажем, что Ь„< 1, Ь„~ + Ь < 2 и т. д.
(что эквивалентно Ь| > 1, Ь| + Ьз > 2 и т. д.). Но это, очевидно, истинно, поскольку все Ь элементов аю,..., аы не болыпе /с. (ПУсть г~ оэначает "левое влиЯние" Чг, а именно г, = й тогДа и только тогда, когда % — ~ < Чз -, Чз-ь — ~ < 99 и либо у = Ь, либо Ч~ ь > Чг. Из всех перестановок ры ..р„, мажорирующих данную последовательность пробуждений аь .. а„, алгоритм "немедленно остановись!" находит наименьшую (е лексикографическом порядке). Конхейм и Вейсс заметили,что количество последовательностей пробуждений, приводящих к данной перестановке ры .. р, равно ) ) ", гг; интересно, что сумма этих произведений, взятая по всем перестановкам Чы ..
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
