Д. Кнут - Искусство программирования том 3 (2-е издание) - 2001 (Часть 1) (1119456), страница 70
Текст из файла (страница 70)
Когда Р' > Р, некоторые записи могут оказаться в этом буфере дважды, но при Р' < Р такого случиться не может. Фрейзер и Уон, проведя обширные эмпирические испытания своего метода, заметили, что Р достаточно велико (скажем, Р > 32) и Р' = Р, средняя длина серии для случайных данных оказывается равной еР, где е ю 2.718 — основание натуральных логарифмов. Это явление, а также тот факт, что метод был получен в результате эволюции метода простого выбора с замещением.
послужили авторам основанием для того, чтобы назвать свой метод нащууальнмм выбором. Можно доказать "натуральный' закон для длины серии, вновь воспользовавшись аналогией со снегоочистителем (см. рис. 64) и применив элементарный математический анализ. Пусть | обозначает длину пути, а х(Г) — положение снегоочистителя в момент 1 при 0 < г < Т. Предположим, что в момент Т внешний буфер (резервуар) заполняется. В этот момент падение снега временно прекращается, пока снегоочиститель возвращается в исходное положение (счищая Р снежинок, оставшихся на его пухи).
Ситуация такая же, как и ранее, только "условия равновесия" другие: вместо Р снежинок на всей дороге мы имеем Р снежинок перед снегоочистителем и резервуар (за снегоочистителем), заполняющийся до уровня, равного Р' = Р снежинок. В течение времени о1 снегоочиститель продвигается на сЬ, если выводятся Ь(я, 1) Пх записей, где Ь(х, г) — толщина слоя снега в момент времени г в ь — к Снег на вхане Снег Рис. 67. Вводятся и выводится равное количество снега; зв времн Ф снегоочиститель перемешается яа дх.
точке х = х(1), измеряемая в соответствующих единицах. Следовательно, Ь(х, Ф) = Ь(х,0) + КФ для всех х. Так как число записей в памяти остается постоянным, то Ь(х, г) дх есть также число записей, вводимых перед снегоочистителем, а именно— К па (Х вЂ” х), где К вЂ” скорость падения снега (рис. 07). Таким образом„ дх К(Х вЂ” х) д1 Ь(х, Ф) (2) К счастью, оказывается, что Ь(х, г) — - константа, равная КТ при всех х = х(1) и 0 < 1 < Т„так как снег падает равномерно в точку х(Ф) в течение Т вЂ” 1 единиц времени после того, как снегоочиститель проходит эту точку, плюс 1 единиц времени перед тем, как он вернется.
Иными словами, снегоочиститель все время видит перед собой одинаковый слой снега на протяжении всего пути, если допустить, что достигнут установившийся режим, т. е, этот путь всегда один и тот же, Следователыю, общее количество счищаемого снега (длина серии) составляет ХКТ, а количество снега в памяти есть количество снега, счищаемого после момента Т, а именно — КТ(Х,— х(Т)). Решением уравнения (2) при условии, что х(0) = О, будет х(1) =Х(1 — е 'г~). (3) Следовательно, Р = ХКТе ~ = (длина серии)7е — как раз то, что и требовалось доказать. В упр.
21-23 показано, что данный анализ можно распространить на произвольное Р', например, когда Р' = 2Р, средняя длина серии оказывается равной ее(е— 0)Р, где д = (е — 4Р— 4)/2. Это результат, который вряд лн можно было предвидеть заранее! В табл. 2 приводится зависимость между длиной серии и размером дополнительного буфера. С помощью этой таблицы можно оценить эффективность натурального выбора для конкретного компьютера в той или иной ситуации. Строки таблицы. соответствующие размеру дополнительного буфера < Р, получены с помощью несколько усовершенствованной методики, которая рассматривается в упр. 27.
Идеи преобразования серий с задержкой и натурального выбора можно скомбинировать, как описано в работе Т. С. Т!пй, У. %. Жаля, Сошр.,У. 20 (1977), 298-301. еАиализ выбора с замещением. Вернемся теперь к выбору с замещением без вспомогательного буфера. Аналогия со снегоочистителем дает довольно хорошую оценку средней длины серий, получаемых при выборе с замещением "в пределе". Тем не менее можно получить значительно более точную информацию об алгоритме В, используя результаты анализа серий в перестановках, который выполнен в разде- Таблица 2 ДЛИНА СЕРИЙ ПРИ НАТУРАЛЬНОМ ВЫБОРЕ Размер Длина 5+ 9 Размер Длина й+ д дополнительного серии дополнительного серии буфера буфера О.НЮООР О 50000 1.00000Р 2.0000ОР З.ОООООР 4.00000Р 5.ОООООР рзлюааоР 2.15780Р 2.54658Р 2.71828Р 3.53487Р 4Л6220Р 4.69446Р 5.16369Р 7.00877Р 2.ОООООР 250000Р З.ОООООР з.заоооР 4АЮООО 5.ооаооР иаооаооР 52914ЗР О.З2О71 О.69952 1.00000 1.43867 1.
74773 2.01212 2.24938 ЗЛ7122 ООООООР 0.43428Р 1,З04ЗгР 1.95014Р 2.72294Р 4.63853Р 21,72222Р 5.29143Р о.ааааа 0.65348 1.15881 1.42106 1.66862 2.16714 4.66667 2.31329 Величина л+ д определена в упр. 22 или (если и = 0) в упр, 27. ле 5.1.3. Для удобства будем считать, что входной файл является последовательностью произвольной длины независимых случайных чисел в диапазоне от 0 до 1.
Пусть др(зыгз,...,аь) = ~~' арЯ 1з .. 1ь)з1 зз "° зэ пзи-"лайв является производящей функцией для длины серии, которая получена прн Р-путевом выборе с замещением, примененном к такому файлу, где пр11ы)з,...,1ь) есть вероятность того, что первая серия имеет длину 1О вторая — - 1з...., л-я — 1ы Будем основываться на следующей "теореме независимости", так как она пюдит наш анализ к случаю Р = 1. Теорема К. др(з1„зт,..., ь) =91(лмзз,...,хь)Р. Доказательство. Пусть исходные ключи суть Хм Хз, Хз,.... Алюритм Н разделяет их на Р подпоследовательностей в соответствии с тем, в какой внешний узел дерева оин попадают.
Подпоследовательность, содержащая Х„, определяется значениями Хы..., Х„. и Таким образом, эти подпоследовательности являются независимыми последовательностями независимых случайных чисел, расположенных между 0 и 1. Кроме того, результат выбора с замещением в точности совпадает с результатом Р-путевого слияния, если ею выполнить нвд этими подпоследовательностями. Некоторый элемент принадлежит у-й серии подпоследовательности тогда и только тогда, когда он принадлежит у-й серии, полученной при выборе с замещением (так как на шаге Н4 ключи 1,АЯТКЕ7 и КЕУ(Ц) принадлежат одной подпоследовательносги).
Иначе говоря, можно считать, что алгоритм Н применяется к Р случайным независимым исходным файлам и что на шаге Н4 считывается следующая запись из файла, ссютветствующею внешнему узлу Я. В этом смысле рассматриваемый алгоритм эквивалентен Р-путевому слиянию, при котором концы серий отмечаются "убыванием" элементов. Таким образом, на выходе будут получены серии длиной ~1ы ...,1ь) тогда и только тогда, когда подпоследовательности состоят из серий длиной П~ы ...,1ы), ..., (1рм...,1р«), где 10 — некоторые неотрицательные целые числа, удовлетворя- ющие соотношению 2.',«;р10 = 1, при 1 < у < Й.
Отсюда получаем ар(1„...,?ь) = ~~~ а|(?м,...,?гв)...аг(1р„...,Хрь), С««+- +бч =6 6«+" чЧ«««ы« что эквивалентно искомому результату. ! В разделе 5.1.3 было проанализировано среднее значение Ь« — длины й-й серии прн Р = 1 (этн значения приведены в табл.
5.1.3 — 2). Из теоремы К следует, что средняя длина я-й серии при любом Р в Р раз больше средней длины при Р = 1; она равна 1«Р. Дисперсия также в Р раз больше, так что стандартное отклонение длины серии пропорционально ~/Р. Эти результаты были впервые получены Б. Дж. Гэсснер (В.
У. Оаввпег) около 1958 года. Таким образом, первая серия, полученная для случайных данных алгоритмом В, будет иметь длину, приближенно равную (е — 1)Р ъ 1.718Р записей, вторая— (ез — 2е)Р щ 1.952Р, третья — 1.996Р; длина следующих серий будет очень близка к 2Р, пока мы не дойдем до последних двух серий (упр. 14 . Стандартное отклонение длины болыпинства этих серий приближенно равно (4е — 10)Р ж 0,934~/Р [С4СМ 6 (1963), 685-687). Кроме того„согласно упр.
5.1.3-10 суммарная длина первых?с серий будет довольно близка к (2я — ~1) Р со стандартным отклонением (( з ?с + 2~) Р) '~~. Производящие функции 9«(с, г,...,к) и 91(1,...,1,т) выводятся в упр. 5.1.3-9 и 11, В приведенном выше анализе предполагалось, что исходный файл бесконечно длинный, но доказательство теоремы К показывает, что такая же вероятность ар(1м..., 1ь) получилась бы прн наличии любой случайной исходной погшедовательности, содержащей, по крайней мере, 1, +.
+?ь+ Р элементов. Значит, полученные результаты применимы для файла размером, скажем, Ф > (2к + 1)Р в силу малой величины ствндартного отклонения. В дальнейшем мы познакомимся с рядом приложений, в которых схема слияния требует, чтобы одни серии были восходящими, а другие — нисходящими. Поскольку остаток, накапливающийся в памяти у конца восходпщей серии, как правило, содержит числа, в среднем меньшие, чем случайные данные, то изменение направления упорядочеяия приводит к уменьшению средней длины серий, Рассмотрим, например, снегоочиститель, который должен разворачиваться каждый раз по достижении конца прямой дороги; он будет очень быстро передвигаться по только что очищенному участку.
В случае изменяемого направления длина серий для случайных данных изменяется между 1.5Р н 2Р (см. упр. 24). УПРАЖНЕНИЯ 1. (10) Каким будет щаг 4 в примере лля четырсхпутсвого слияния, приведенном в начале этого разлвла? 2. [И) Какие изменения пронзощлп бы в дереве на рис. 63, ели бы ключ 061 был заменен ключом 612? 3. (?6] (Э. Ф. Мур (Е. г. Мооге).) Что получится врезультатеприменениячстырскпутеваго выбора с замещением к последовательным словам приведенного ниже предложения: Товгвсоге аав ветен уеагв або овг Таейегв Ьговбйе Тогев ов слвв совеввевс а вев ваг1ов совсейте4 1в 11ьегсу авб ве41сасев со зле ргоровэейов элаг а11 иев аге сгеасев еова1. (Используйте обычный алфавитный порвдок, рассматривая каждое слово как один ключ.) 4. [)6] Примените четырехпутевой нашура,аьнмй выбор к предложению иэ упр. 3, используя дополнительный буфер емкостью 4.
$. [00] Верно ли, что выбор с замещением, использующий дерево, работает, только если Р есть степень 2 или сумма двух степеней 2? 8. [16] В алгоритме К указывается, что Р должно быть > 2. Какие относительно небольшие изменения необходимо сделать в этом алгоритме, чтобы оп правильно работал для всех Р > 1? Т. [) 7] Что делает алгоритм К в случае отсутствия походной информации? 8. [20] Алгоритм К использует искусственный ключ "оо", который должен быть больше любого возможного ключа. Покажите, что если бы какой-нибудь реальный ключ оказался равным оо, то алгоритм мог бы ошибиться, и объясните, как изменить алгоритм в случае, когда реализация "настоящего" со неудобна.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
