AOP_Tom3 (1021738), страница 68
Текст из файла (страница 68)
е. не меньше 67. Последовательность (1) не является серией с двумя степенями свободы, так как 17 меньше, чем 50 и 90. Серия с т степенями свободы в процессе чтения на следующей фазе сортировки может быть преобразована таким образом, что лля всех практических целей она будет серией в обычном смысле. Начнем с чтения первых т блоков в т буферов и будем выполнять их т-путевое слияние; когда один из буферов исчерпается, поместим в него (пг + 1)-й'блок.
и т. д. Таким образом можно восстановить серию в виде одной упорядоченной последовательности, поскольку первое слово каждого вновь считываемого блока должно быть больнге последнега слова только что исчерпанного блока или равно ему (если оно не было меньше, чем наибольшие элементы каких-либо предшествующих ему т блоков). Этот метод преобразования серии, в сущности, является т-путевым слиянием, использующим только одно устройство внешней памяти для всех входных блоков! Процедура ггреабразования действует, как сопрограмма, к которой обрашаются каждый раз, когда нужно получить одну очередную запись серии.
Можно в одно и то же время преобразовывать различные серии с различных устройств и с различными степенями свободы и сливать получающиеся серии. Это, по существу, подобно тому, как если бы процесс четырехпутевого слияния, рассмотренный в начале настоящего раздела, был представлен в виде нескольких процессов двухпутевого слияния, которые происходят одновременно. Такую остроумную идею трудно до конца проанализировать, но в работе Т.
О. Еэре)Ы, В1Т 16 (1976), 133-142, показано, как распространить нашу аналогию с работой снегоочистителя на этот случай и получить соответствующую приближенную формулу. Как следует из выведенной формулы аппроксимации, длина серии будет равна примерно / 2Р+ (гп — 2)Ы если 6 — размер блока и гп > 2. Эти данные довольно хорошо согласуются с проведенными практическими экспериментами.
Такое увеличение длины нельзя считать достаточным для компенсации повышения сложности процесса. Но, с другой стороны, это может дать некоторые преимущества, когда существует возможность организовать довольно большое число буферов на второй фазе сортировки. эНатурнльный выбор. Другой путь увеличения длины серий, порождаемых выбором с замещением, был исследован в работе %'. В. Егахег, С. К. Жопб, САСМ 15 (1972), 910 — 913. Изложенная авторами идея состоит в том, чтобы следовать алгоритму й, кроме случая, когда в дерево включается новая запись, ключ которой меньше, чем 1.АБТККУ.
Тогда вывод направляется во внешний дополиигаельнмй 6916ер н считывается новая запись. Этот процесс продолжается до тех пор, пока в дополнительном буфере не окажется определенного количества записей Р'. Тогда остаток текущей серии выводится из дерева, а элементы из дополнительного буфера используются в качестве исходных данных для следующей серии. Рассмотренный метод должен порождать более длинные серии, чем метод выбора с замещением, поскольку он "обходит" вновь поступающие "мертвые" записи, вместо того чтобы позволять им заполнять дерево; но ему требуется дополнительное время на обмен с дополнительным буфером.
Когда Р' > Р, некоторые записи могут оказаться в этом буфере дважды, но при Р' < Р такого случиться не может. Фрэйзер и Уон, проведя обширные эмпирические испытания своего метода, заметили, что Р достаточно велико (скажем, Р > 32) и Р' = Р, средняя длина серии дчя случайных данных оказывается равной еР, где е ы 2.718 — основание натуральных логарифмов. Это явление, а также тот факт, что метод был получен в результате эволюции метода простого выбора с замещением, послужили авторам основанием для того, чтобы назвать свой метод нагпуральнмм выбором. Можно доказать "натуральный" закон для длины серии, вновь воспользовавшись аналогией со снегоочистителем (см.
рис. 64) и применив элементарный математический анализ. Пусть 1 обозначает длину пути, а х(1) — положение снегоочистителя в момент г при 0 < г < Т. Предположим, что в момент Т внешний буфер (резервуар) заполняется. В этот момент падение снега временно прекращается, пока снегоочиститель возвращается в исходное положение (счищая Р снежинок, оставшихся на его пути). Ситуация такая же, как и ранее, только "условия равновесия" другие: вместо Р снежинок на всей дороге мы имеем Р снежинок перед снегоочистителем и резервуар (за снегоочистителем), заполняющийся до уровня, равного Р' = Р снежинок.
В течение времени 61 снегоочиститель продвигается на дх, если выводятся Й(х, С) пх записей, где 6(х, 1) — толщина слоя снега в момент времени 1 в в — д Снег нв входе К ег Снег Рис. 67. Вводится и выводится равное количество снега; за время Ж снегоочиститель перемещается на Нх. точке х = х(г), измеряемая в соответствующих единицах.
Следовательно, п(х, г) = 6(х, О) + К1 для всех х. Так как число записей в памяти остается постоянным, то й(х, ~) дх есть также число записей, вводимых перед снегоочистителем, а именно— К е)г1Б — х), где К - — скорость падения снега (рис. 67). Таким образом, сЬ К(Š— х) (2) а й(х 1) К счастью, оказывается, что гг(х,1) — константа, равная КТ при всех х = х(г) и 0 < й < Т, так как снег падает равномерно в точку х11) в течение Т вЂ” 1 единиц времени после того, как снегоочиститель проходит зту точку, плюс 1 единиц времени перед тем, как он вернется. Иными слонами, снегоочиститель все время видит перед собой одинаковый слой снега на протяжении всего пути, если допустить, что достигнут установившийся режим, т. е, этот путь всегда один и тот же.
Следовательно, общее количество счищаемого снега (длина серии) составляет е.КТ, а количество снега в памяти есть количество снега, счишаемого после момента Т, а именно — КТ(1,— х(Т)) . Решением уравнения (2) при условии, что х(0) = О, будет х(г) =1 (1 — е 'г ). 13) Следовательно, Р = БКТе = (длина серии)/е — квк раз то, что и требовалось — 1 доказать.
В упр. 21 — 23 показано, что данный анализ можно распространить на произвольное Р', например, когда Р' = 2Р, средняя длина серии оказывается равной ее(е— В)Р, где В = (е — ъ'ее — 4)/2. Это результат, который вряд ли можно было предвидеть заранее! В табл. 2 приводится зависимость между длиной серии и размером дополнительного буфера. С помощью этой таблицы можно оценить эффективность натурального выбора для конкретного компьютера в той или иной ситуации. Строки таблицы, соответствующие размеру дополнительного буфера < Р, получены с помощью несколько усовершенствованной методики, которая рассматривается в упр. 27. Идеи преобразования серий с задержкой и натурального выбора можно скомби- нировать, как описано в работе Т. С. Тшб, У.
%. 11гапб, Согпр. Х 20 (1977), 298 — 301. *Анализ выбора с замещением. Вернемся теперь к выбору с замещением без вспомогательного буфера. Аналогия со снегоочистителем дает довольно хорошую оценку средней длины серий, получаемых при выборе с замещением "в пределе". Тем ие менее можно получить значительно более точную информацию об алгоритме В, используя результаты анализа серий в перестановках, который выполнен в разде- Таблица 2 длинл серий нрг| нлтурлльном' выворе Размер Длина дополнительного серии буфера А+В Размер Длина дополнительного серии буфера одаооа~ 0.50000Р 1.00000Р 2 ОООООР 3.00000Р 4. ОООООР 5.00000Р 10.00000Р 2.15780Р 2.54658 Р 2.71828Р 3.53487Р 4.16220Р 4.69446Р 5 16369Р 7.00877Р 2.00000Р 2.50000Р З.ОООООР 3.50000Р 4.00000Р 5.00000Р 10.00000Р 5.29143Р 0.00000 0.65348 1 15881 1.42106 1.66862 2.16714 4.66667 2.31329 О.ОООООР ОД3428Р 1.30432Р 1.95014Р 2.72294Р 4.63853Р 21.72222Р 5.29143Р 0.32071 0.69952 1.
00000 1 43867 1.74773 2.01212 2.24938 3. 17122 Величина А Ч-9 определена в упр. 22 нлн (если А = О) в упр. 27. ле 5.1.3. Для удобства будем считать, что входной файл является последовательностью произвольной длины независимых случайных чисел в диапазоне от О до 1. Пусть 9Р(е1~ з2 ° зь) — )' аР(11 12 )А) г1 зз хь О г, ц ьл, ц>е является производящей функцией для длины серии, которая получена при Р-путевом выборе с замещением, примененном к такому файлу, где ар(1м 1з,...,1А) есть вероятность того, что первая серия имеет длину 1м вторая — 1з, ..., Й-я — 1А. Будем основываться на следующей "теореме независимости", так как она сводит наш анализ к случаю Р = 1.
Теорема К. 9, (е,,зз,... „аь) = 91(ем г~.....,.ег)~. Доказашельстеа. Пусть исходные ключи суть Л м Лз, Хз,... Алгоритм К разделяет их на Р подпоследовательностей в соответствии с тем, в какой внешний узел дерева они попадают. Подпоследовательность, содержап1ая Х, определяется значениями Хм..., Х„ь Таким образом, эти подпоследовательности являются независимыми последовательностями независимых случайных чисел, расположенных между О и 1. Кроме того, результат выбора с замещением в точности совпадает с результатом Р-путевого слияния, если его выпщп1ить над этими полпоследовательностями. Некоторый элемент принадлежит 7-й серии подпоследовательности тогда и только тогда, когда он принадлежит 7-й серии, полученной при выборе с замещением (так как на шаге Н4 ключи 1АВТКЕУ и КЕг (Ц) принадлежат одной подпосзедовательности).
Иначе говоря, можно считать, что алгоритм К применяется к Р случайным независимым исходным файлам н что на шаге Н4 считывается следующая запись из файла, соответствующего внешнему узлу Ц. Б этом смысле рассматриваемый алгоритм эквивалентен Р-путевому слиянию, при котором концы серий отмечаются "убыванием" элементов. Таким образом, на выходе будут получены серии длиной (1ь...,)ь) тогда и только тогда, когда подпоследовательности состоят из серий длиной (1ы,...,1ы), ..., (1ры..., 1рь), где 16 — некоторые неотрицательные целые чигла, удовлетворя- ющие соотношению 2',«,.р 1;,.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
