AOP_Tom3 (1021738), страница 100
Текст из файла (страница 100)
2. Например, если .0 = 4 и Я = 18, среднее время вылолнепия Р-путевого слияния Е блоков данных с использованием 4 дисков и Р + 25 входных буферов будет не больше времени чтения т(4,20)Х,/П 1.7851,/4 блоков с единственного диска. Эта теоретическая оценка верхней границы довольно консервативна; на практике результаты бывают даже лучше — — они колеблются в пределах оптимального времени Ь/4. Таблица 2 ГАРАНТИРОВАННАЯ ПРОИЗВОДИТЕЛЬНОСТЬ 11РИ РАНДОМИЗИРОНА НО<И РАЗДЕЛЕНИИ г(4, <7) г(4,2<1] г(<4, 3<!) т(<4,4<!) т(<4, 54) г(<ь б<!) г(<4, 7<4) т(<4, 6<4) г(4, 9<!) г(<1, 104) Поможет ли сортировка ключей? Если записи длинные, а ключи короткие, несыта заманчиво создать новый файл, сос!оящий только из ключей с порядковыми номерами, определяющими их первоначальное положение в файле.
После сортировки этого файла ключей можно заменить ключи последовательными числами 1, 2,.... Затем попый файл можно рассортировать по положению в первоначальном файле, н результате чего получится удобное описание того, как "растасовать" записи, т. е. окончательно перекомпоновать их в требуемом порядке.
Схематически предстаним процесс так. (К1, 1!)(КЗ<12)... (К№ 1м) (1!1, 1)(<туг, 2) .. (К№ <Ч) ЖШ,Р!)Ж.,Р2)" Ж н,РЯ) (1. р1) (2, р2) ° . (< т, рь<) (Ч1,1)(Ч2,2)... (Чм<Х) (Ч! <!)(ЧЗ<<2) ° (Ч№17<) 1) [Чсходный файл й) Файл ключей ш) Рассортированный (й) гт) Отредактированный (ш) у) Рассортированный (гу) у!) Отредактированный (!) Длинный Короткий Короткий Короткий Короткий Длинный Здесь р = lс тогда и только тогда, когда ч1 = 11 Два процесса сортировки на стадиях (<и) и (у) сравнительно быстрые (иногда, можно обойтись ннутр< иней сортировкой), так квк записи не слишком длинные.
На стадии (у!) задача сведена к сортировке файла. ключи которого — просто числа (1,2,..., <!<). Каждая запись теперь определяет в точности то место, куда ее следует переместить. Внешняя перекомпоновка записей, остающаяся после стадии (у!), на первый взгляд кажется тривиальной, .но фактически она очень сложна, и все еще не найдено ни одного действительно хорошего алгоритма (существенно лучш<гго, чем алгоритм для сортировки). Мы, очевидно, могли бы выполнить перекомпановку за <т' шагов, перемещая всякий раз по одной записи.
Д!<я достаточно большого Х это лучше, чем Х)08Х и методах сортировки, хотя Х никогда не бывает таким большим. Но <Ч все-таки достаточно велико, чтобы сделать <5! поисков просто нереальными. <4 = 2 4=4 <4=8 <1= 16 <4= 32 <4=64 и= 128 4= 256 <4 = 512 <4 = 1024 1 500 1.500 1.499 !.467 2.460 2.190 1.986 1.888 3 328 2.698 2.365 2.183 4.087 3.103 2.662 2.434 4.503 3.392 2.917 2.654 5.175 3.718 3 165 2.847 5.431 3 972 а356 2.992 5.909 4.222 3.536 3.155 6.278 4.455 3.747 3.316 6.567 4.689 3.879 ЗМ34 1.444 1.422 1.393 1.785 1.724 1.683 2.056 1.969 1 889 2.277 2.156 2.067 гм58 2.ЗШ ХЗЬЗ 2.613 2.465 2.346 2.759 2.603 2.459 2.910 2.714 2.567 3.024 2.820 2.675 3.142 2.937 2.780 1.370 !.353 1.339 1633 1597 1.570 1.836 1 787 1.743 1.997 1.933 1 890 2.130 2.062 2.005 2.249 2 174 2.107 2.358 2.273 2.201 2.464 2.363 2.289 2.556 2.450 2.375 2.639 2 536 2.452 Г(п) = ~~1 ((181) +1) = Н(п)+п — 1 =п()8п) — 2"1вп +п, (25) 1<1«п где В(п) есть функция бинарной вставки (см, формулу 5.3.1 — (3)).
Согласно 5.3.1- (34) функция Р(п) — это не что иное, квк минимальная длина внешнсго пути бинарного дерева с и листьями, и (26) п18п < Г(п) < п!8п+0.0861п. Так как Р(п) выпукла и удовлетворяет условию Е(п) = и + г'((и/2)) + Р(~п(2)), согласно сформулированной вылив лемме С Е(п) < Е(1с) + Е(п — й) + п при 0 < lс < п. (27) Это соотношение вытекает также из представления Е в ниде длины внешнего пути; в дальнейшем оно окажется ре1пающим аргументом в наших рассуждениях. Как и н разделе 5.4.8, предположим, что лифт вмещает ги человек, каждый этаж вмещает 5 человек и имеется п этажей.
Пусть вб — число людей, находящихся в данный момент на этаже1 и стремящихся попасть на этаж 71 По определению оценка совместности любого расположения людей в здании есть ~181 <„Г(во). Предположим, например, что 5 = гп = п = 6 и что первоначально 36 человек следующим образом распределены между этажами: опоило 123456 123456 123456 123456 123456 123456' (28) Лифт пуст и находится на этаже 1; пмп обозначает свободное место. На каждом этаже имеется по одному человеку, стремящемуся попасть на каждый нз этажей, К отредактированным записям можно эффективно применять какой-либо метод поразрядной сортировки, поскольку ключи имеют строго равномерное распределение.
На многих современных быстродействующих компьютерах время вычислений для В-путеного распределения значительно меньше, чем время вычислений для 8-путевого слияния. Следовательно, распределительная сортировка может быть наилучшей из всех процедур (см. раздел 5.4.7, а также упр. 19). Но, с другой стороны, представляется уж слишком расточительным выполнять сортировку ключей после того, как они уже были рассортированы.
Одна из причин возникновения проблемы, связанной с внешним переразмещением, была открыта Р. У. Флойдом, который нашел нетривиальную нижнюю границу для числа поисков, необходимых для перестановки записей в дисковом файле (Соп1р!ехйу оу Сошрисег Сошрп1абопэ ( чсв гог)с: Р)епшп, 1972), 105-109). Результат Флойда удобна описать, воспользовавшись аналогией с лифтом, как в разделе 5.4.8. На этот раз найдем график работы лифта, минимизирующий число остановок, а не пройденное расстояние.
(Минимизация числа остановок не июлие эквивалентна нахождению алгоритма перегруппировки с минимальным числом поисков, так как одна останонка объединяет вход в лифт с выходом из него. Однако разница не слишком велика, н мы воспользуемся критерием минимизации остановок, чтобы пояснить основные идеи.) Будем использовать функцию дискретной энтропии поэтому все величины в, равны 1 и оценка совместности ранна О. Если теперь лифт отвезет 6 человек на этаж 2, то мы получим расположение 123456 иссооссо 123456 123456 123456 123456 123456 (29) и оценка совместности станет равной 6Г(0) + 24Е(1) + бЕ(2) = 12.
Допустим, лифт перевезет 1, 1, 2, 3, 3 и 4 на этаж 3; 112334 оооиоо 245566 123456 123456 123456 123456 (30) Оценка совместности изменится до 4Е(2) + 26'(3) = 18. Когда каждый пассажир будет, в конце концов, перевезен к своему месту назначения, оценка совместности станет равной 6Е(6) = 96. Флойд заметил, что оценка совместности никогда не увеличивается болыпе чем на Ь+ пс за одну остановку, .так как множество из в пассажиров с одним пунктом назначения, объединяясь с аналогичным множеством мощности в', увеличивает оценку на Р(е + э') — Р(а) — Г(в') < в + в'. Таким образом, имеем следующий результат. Теорема Е. Пусть 1 — определенная выше оценка совместности начального рас- положения пассажпров. Лифт должен сделать по крайней мере Г(Е(6) и — 1)/(Ь+ Л остановок, чтобы доставссгь всех пассажнров к нх месту назначения.
1 Сформулируем этот результат применительно к дискам. Допустим, что имеется Ьп записей по Ь в каждом блоке, и предположим, что н оперативной памяти одновременно помещается сп записей. При каждом чтении с диска один блок переносится в память, а при каждой записи один блок помещается на диск, и в; есть число записей в блоке с, принадлежащих блоку 21 Если и > 6, то существует начальное расположение, для которого все в, < 1, так что 1 = О. Следовательно, для переразмещения записей необходимо выполнить хотя бы /(Ь)п/(Ь+ сп) = (Ьп1кЬ)/сп операций чтения блока.
(Если 6 велико, то множитель 1яЬ делает эту нижнюю оценку нетривиальной.) В упр, 17 выведена несколько более строгая нижняя оценка длн общего случая, когда гп существенно больше Ь. УПРАЖНЕНИЯ 1. (Мвй) В тексте раздела анализируется метод, с помощью которого среднее время ожидания, необходнмое для чтения доли х дорожки, уменьшается с —.', до —.' (1 — г") оборотов. Это минимально возможное время, когда имеется один держатель головок Каково соответствующее минимальное время ожидания, еюси имеется два держателя головок, разнесенных на 180' (в предположении.
что в любой момент данные могут перелаватьгя только через головки на одном из держателей)? 2. (МУО) (А Г Конхейм (А С Копбесш).) Нвзначессие этого упражнения " исследовать, на какое расстояние должен переместиться держатель головок во время ысияния файлов, расположенных "ортогонассс но" к цилиндрам. Допустим, имеется Р файлов, в каждом из которых содержится Ь блоков записей, и предположим, что первый блок каждого файла находится на ци'индре 1, второй — на цилиндре 2 и т.
д. Движением 8. [49] Существует ли алгоритм, который при заданных а, В и весах и м..., и:„находит оптимальные в смысле упр. 7 деревья, затрачивая только 0(п') шагов при некотором с? Я. [НМЗ9] (Л. Хьяфил (1. Нуаб!), Ф. Прускер (Е. Ргнвйег) и Ж. Вуйлемен (1. Ъгш!!еш!п).) Докажите, что для фиксированных а и )7 получаетгя А1(п) = (ш!п /! п)об и + 0(к) ат+8! йд !обт / при и -д со, где член 0(п) > О. 10. [НЛЩ] (Л. Хьяфнл, Ф. Прускер и Ж. Вуйлемен.) Докажите, что при фиксированных а и /) А1(п) = атп+ !3п+ А (и) для всех достаточно больших и, если т минимизирует коэффициент в упр. 9. 11.
[Лгйр] В обозначениях (б) и (11) докажите, что / (в) + тп > /(и) при всех т > 2 и и > 2, и определите все гп и и, при которых имеет место равенство. 12. [35] Докажите, что при всех и > 0 существует дерево с, и листьями и минимальной длиной степенного пути соответственно (б), все листья которого расположены на одном уровне. 13. [ЛЩ] Покажите, что прн 2 < и < г!(аа8), где 8(а, !?) определено в соотношении (12), единственной наилучшей схемой слияния в смысле теоремы Н являетгя вьпутевое слияние. 14. [40] При использовании квадратичного метода распределения буферов время поиска для схемы слияния, представленной на рис.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
