AOP_Tom3 (1021738), страница 198
Текст из файла (страница 198)
Замечание. Учитывая то, что 1/(х+ у) > зз ппп(1/х, 1/у), когда х и р положительны, можно выразить эту нижнюю оценку в более приемлемой форме: Такой результат получен в работе А. Абба»па!, Л. Б. У(ееег, САСМ 31 (1988), 1115-1127, в которой также приводится соответствующая верхняя оценка: О( )(Ь,! 8 йЬ))). Расширение этого решения для нескольких дисков описано в работе М. Н.
7»ое)!пе, Л. Б. У!Ы еег, АСМ Бушроз!от оп Рата!!е! А!Бог!ейшз апс! Агсййесеигез 5 (1993), 120 — 129. 18. Ожидаемое число остановок есть 2 ',> р„где р, — вероятность того, что необходимо не менее з остановок. Пусть д, = 1 — р,.ю — вероятность того, что необходимо не более з остановок. Тогда нэ упр. 17 следует, что д, < /(в — 1+ (э = О]), где /(э) = Ы"а'/(Ьп)! и и = п((Ь+т)е/Ь) . Если/(1 — 1) < 1 < Я) то Я > р~ > р~+ +р~ = г — (йо+ . +4с-~) > С вЂ” (Г~П) + /(0) +...
+/(С вЂ” 2)) > г — (и'-'+ а'-~+ + а-') > à — 1 > 5 — 1. 19. Осуществляя анализ, выполните шаг (тй) в обратном направлении, распределяя записи сначала в ящик 1, а затем — в ящик 2. Это именно та операция, которая моделируется в отношении файла ключей на шаге (1т). ]Ргшсесов СопГегепсе оп ГвГогшаБоп Бспшсез апд Яуэсешз 6 (1972), 140-144.] 20.
Следует серьезно отнестись к выбору метода внутренней сортировки, учитывая ограничения, которые накладмваются страничной организацией, Такие методы, как метод Шелла с уменьшением смещения, вычисление адреса, пирамидальная сортировка и сортировка списка, вряд ли приемлемы, если мал реальный объем оперативной памяти, поскольку при нх реализации потребуется большое число "рабочих страниц". Методы быстрой сортировки, обменной поразрядной сортировки и последовательно рвспределяемого слияния или поразрядной сортировки значительно лучше "себя чувствуют" в страничной среде.
Существуют определенные нюансы, которые можно учитывать при создании алгоритмов внешней сортировки, но которые исключаются при использовании автоматической системы распределения страниц: (1) выбор на основе предсказания файла исходных данных, который должен читаться следующим, чтобы нужные данные оказались загруженными к тому моменту, когда в них появится необходимость; (й) выбор размера буфера и порядка слияния в соответствии с характеристиками оборудования и данных. С другой стороны, виртуальная машина значительно упрощает программирование и с ее помощью можно получить неплохие результаты, если программист работает аккуратно н учитывает воэможности той реальной вычислительной системы, для которой разрабатывается программа.
Первое достаточно полное исследование этой проблемы выполнено Браун (Вгавп), Густавовнам (Ооэгатэоп) я Манкиным (Мап)пп) (САСМ 13 (1970), 483 — 494.] 31. ](à — Г)/Р~]; см. СМаСЬ, формула (3.24). 33. После считывания группы из В блоков, которые содержат аз, понадобится знать азьп, прежде, чем будет выполнено считывание следующей группы из В блоков. Если хранить и ьп, с а,, то понадобятся также значения ао, ..., ап-э в виде некоторого заголовка файла с тем, чтобы начать процесс. Но, следуя этой схеме, невозможно записать блоки ао...ап ~ до тех пор, пока не будет вычислено ап... азп ъ Таким образом, потребуется 3Р— 1 выходных буфера вместо 2Р для того, чтобы продолжительное время сохранять записываемую информацию.
Отсюда следует, что лучше записать значения а в отдельный короткий файл. ]Такие же соображения можно привести и по отношению к рандомизированиому разделению.] 23. (а) Для реализации алгоритма 5.4.6Е требуется 4 входных буфера, каждый объемом, соответствующим размеру суперблока РВ. (Если к этому прибавить еще и буфера вывода, то в сумме получится бРВ записей в буферах оперативной памяти в случае использования алгоритма 5.4.6Е и 5Р — в случае использования алгоритма БупсЯогк) (Ъ) В то время, когда считывается группа из В блоков, нужно иметь в своем распоряжении пространство для буферов, чтобы хранить предыдущие Р блоков и одни незавершенный блок, т.
е. (2Р+ 1)В записей. (Для вывода требуется еще 2РВ, но в результате многих операций обработки данных в ходе выполнения 2-путевого слияния на практике передается на выход сравнительно небольшой объем информации.) 24. Пусть 1-м блоком в хронологическом порядке будет блок У! серии й!, в частности у! = О и й! = 1 при 1 < 1 < Р.
Этот блок будет считываться в момент времени г! = 2 ь, !шю где г !мз = ~(г ) 1 < г < 1 и й, = lс и (хь + у ) шоб В = Ы)) есть число блоков серии й на диске !1, которые хронологически < 1 и !7 = (хс, + у!) шоб В, Пусть нгь = )(г ) 1 < г < 1 и )г, = к) ~; тогда щь — (!1 — х!) шоб В ~ 1!ш = поскольку у, пробегает значения О, 1, ..., вп„. — 1, если 1 < г < 1 и й„= /с. Последователь- ность 1! для примера из (19) .(21) есть 11111 22223 43456 34567 82345 67893 После того как пачнетсн слияние с 1-го в хронологическом порядке блока, количество необходимых блоков в буферах будет составлять Х! + В + Р, если 1 > Р. Здесь 1! есть число "инверсий с равенством" в 1!, а именно — ~(г ) г > 1 и 1„< 1!Ц, т. е.
число заполненных буферов, в которые мы считали информацию, но еще не готовы ее использовать; В представляет буфера, в которые будут считываться следующие исходные данные, н Р— частично заполненные буфера, из которых берутся данные для слияния. (Приняв некоторые специальные меры, можно, используя связи, как в случае с алгоритмом БупсБогс, ослабить последнее требование с Р до Р— 1, но усложнение процесса, которое при этом происходит, вряд ли сделает такую операцию целесообразной,) Таким образом, проблема сведена к определению верхней оценки 7!. Можно предположить, что входные серии имеют бесконечно большую длину.
Предположим также, что з в элементах (г!,..., !!) больше, чем !!; тогда !! имеет 1! — ! + в инверсий с равенством, поскольку точно !!В элементов < !!. О!сюда следует, что максимум 7! получается, когда э = О и 1! есть максимум слева направо, Имеем 2 'ь ! и!ь = 1; значит, учитыван приведенные выше формулы, для !! получаем 7! < тах(1! — 1) < ) (иш — (!7 — хь) шобВ+  — 1 — щь) $>г ь=! = Р( — 1) — ~ (!1 — хь) !поб В ь=! < Р( — 1) — ппп ~ (!2 — хь) шос1 В оба<о ь=! н существуют хронологические порядки, для которых достижима эта верхняя оценка. Предположим, что г! из г! равны 6 Желательно выбрать х! таким образом, чтобы максимизировать шшобз<р вю где эз = 2 „!(Ы вЂ” хь) шоОВ = 2, ((Н вЂ” 1) шобВ)г!.
Можно предположить, что минимум будет прн !2 = О. Тогда в! = зо + Р— г!В, вт = з!+Р— ггВ, .... Отсюда получаем ! ! < (Р(В), г!+г! < ~(2Р(В), ..., поэтому минимумом является и — ! 1 эе = ( — 1)г! + ( — 2)г! + + го ! < ) (5Р!В) = — ((Р— 1)( — 1) +бсп(Р,В) — 1), 2 что вытекает нз результатов упр. 1 2 4-37. Эта граница достигается, когда х! = )2В) Р) — 1 при1<у<Р. Имея такое х„можно работать с любой хронологической последовательностью иа полной скорости, если в нашем распоряжении есть 7„„„+ В + Р = 5РВ + -В + -Р + ! з -'бсб(Р, Р) — 1 входных буферов, в каждом из которых отведено место длн В записей. г (Это особенно хорошо, когда 77 = 2 или 3.) 25. Обратите внимание на то, что в цикле 4 мы возвращаемся к чтению /! с диска О. Активные слинния Прочие В ожидании (-------) " Ьаса(езда — — — ) ба еа/ада(«Х«сКг/! ) Ла «««(а«гег««з/«д«ог) е! «1! с!«1зо«/! Ь! д! 0 ог Угрз(6«дг ) ««4 (И«Ьгдгоз/зе« вЂ” ) с! 6«Ьгдгоз/зе«( г ) пз 26.
В то время, когда Р блоков считываются и Ь«блоков записываются, процедура слияния могла бы сформировать до Р + Π— 1 блоков на выход, предполагая выполнение схемы (24). (Но не Р+ 4/, поскольку только один буфер слияния будет абсолютно пуст.) Считывание выполняется с той же скоростью, что и запись, а потому необходимо 17+ Р+ «,",« — 1 буферов вывода для предотвращения задержки вывода. Однако в среднем не более 77 блоков являются выводными для каждых входных П блоков, так что на практике нужно ориентироваться примерно на 3В выходнь«х буферов. 27.
(а) Е («п«,...,тр) = 2„«д«, где д«есть вероятность того., что в некоторой урне содержится не менее г шаров. Очевидно, что д«< 1 и д«< ~ Рг(урна 6 содержит не менее З шаров) = иРг(Я («и«,...,тр) > !). з=а (Ь) Производящая функция вероятностей для Я (т«,..., тр) такова: ( ) = П ""('+( - ')" /") где дз = (тз/и) и гь = ть що«(и. Теперь 1+ и < (1+ а/и)" и 1 + пг/и < (1+ и/т«)", когда и > 0; отсюда имеем Рг(Я (т«,..., тр) > З) < (1+ и) 'Р(1+ и) < (1+ а) ' П,",,(1+ сз/и)ма = (1+«!) «(1+и/и)».
Еш«и 1 < т/и, используется член "1» в сформулированном минимуме. Если Г > т/и, величина (1+ и) (1+ и/и) принимает минимальное значение (и — 1)'"' 'т"'/(и Р(т— 1) '), когда и = (иг — «и)/(т — З). 28. Как нам кажется, числовой подсчет подтверждает зто предположение. Например, получим Е! а(1, 1, 1, 1, 1, 1, 1, 1) = 2.3993180, Е! а(2, 1, 1, 1, 1, 1, .1) = 2.364540, Е«а(2, 2, 1, 1, 1, 1) = 2 32076, Е«а(3, 1, 1, ), 1, 1) = 2 29958, Е«а(2,2,2, 1, 1) = 2.2628, Е! а (3, 2, 1, 1, 1) = 2.
2460, Е«а(4, 1, 1, 1, 1) = 2.2076, Ь«а(2,2, 2, 2) = 2 178, Е«а(3,2,2, 1) = 2.166, Е«а(3, 3, 1, 1) = 2.152, Е«а(4, 2, 1, 1) = 2.138, Ь«а(5,1, 1, 1) = 2,090, Е«а(3,3,2) = 2.02, Ь«а(4, 2, 2) = 2.01, 29. (а) В момент З со всех дисков считываются блоки, которые появятся не ранее, чем блок, маркированный в момент й Следующие Я блоков никогда не будут удалены из группы прочих буферов, если они прочитаны. Таким образом, интересующие нас блоки на Цикл 1 Цикл 2 Цикл 3 Цикл 4 Цикл 5 Цикл б Цикл 7 Цикл 8 Активные чтения еабадаоаса /! да А Из /а озбаегд!«1з /«е«6«д«а! ог/зб«езда «1«из/збге« с«аз/з 7 ез «гзоа ' оаЬаса«1а — — —— аа 6а са Иа еа /а да ба оабаса«4«е«/адаба огЬ! са«4зег/«д«Ьа агЬ«са«з«ез/гд«ба ог6! с««««сз/гд«Ьа Еш(4,3, 1) = 2.00, Е«а(5,2,1) = 1.98, Е«а(б, 1, 1) = 1 94 Е«а(4,4) = 1.7, Е«а(5„3) = 1.7, Е«а(6,2) = 1.7, Ею(7, 1) = 1.7.
диске / будут счнтаны во время < ! + )Чз; все онн должны принять участие в слиянии во время З+ лпах(№,...,)Чи л). (Ь) Если (),)+1)-й блок после маркнрованного блока не удален, то можно использовать тот же аргумент. В прозвоним случае предыдущие )'„) не маркнрованы н )в+ 2 блоков не могут размещаться на разных дисках. (с) Разделите хронологнческнй порядок блоков на группы размером л„) + 2 и рассмотрите любую нз ннх. Если существует Мз блоков нз серии )з, то числа )Ч, эквивалентны числу шаров в 2-й урне в задаче о цнклнческой занятости прн и = Р н ш = Я + 2. Таким образом, ожидаемое число маркированных ячеек не превышает верхней оценкн в упр. 27, (Ь).
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
