Д. Кнут - Искусство программирования том 3 (2-е издание) - 2001 (Часть 1) (1119456), страница 99
Текст из файла (страница 99)
ав, на дисках от Одопис — 1, а Р— Ьблоков Ьв...Ьп в т— на дисках от  — 1 до Й, Далее можно продолжать в том же духе, но с дисками, номера которых сдвигаются циклически на Й. Этот трюк хоро!по известен карточным фокусникам, которые называют его принципом Гилбрегпа. Трюк изобретен в 50-х годах Норманом Гилбретом (Ног»пап 00ЬгеавЬ) (см. Маггш Саг»1пег, МагЬешав»са1 Марс ЯЬож (Хек !'огЬ: Кнор?, 1977), СЬаргег 7; Х. 0»1ЬгеагЬ, Сеп»! 52 (1989), 743-744]. Для того чтобы решить, какой блок следует считывать следующим, нужна информация из блоков а и,?, но она занимает только малую долю всего объема а и 6 и, следовательно, можно хранить ее в отдельных файлах. Отсюда следует, что можно обойтнсь меньшими буферами для хранения считанных на полной скорости данных (см.
упр. 23). Рапдомизировапное разделение. Если нужно выполнить Р-путевое слияние на:0 дисках при условии, что Р н й достаточно велики, одновременное чтение информации с В дисков без конфликтов реализовать не удастся (если только не организовать большое количество буферов).
Это связано с тем, что аналога принципу Гилбрета при Р ) 2 не существует. Как бы мы ни организовали распределение блоков файла между дисками, всегда есть вероятность, что придется считывать множество блоков в оперативную память прежде, чем появится возможность их использовать, поскольку те блоки, которые действительно нужно обрабатывать, могут оказаться на одном и том же диске, Предположим, что нужно выполнить 8-путевое слияние на 5 дисках н блоки поп! пв ° °, ЬоЬ! Ь!..., ..., ЛеЛгйз...
по 8 серий разделены по такому правилу: о„— на диск у шо»(П, Ь! — на диск Ц + 1) шо!1В, ..., Ь вЂ” на диск Ц + 7) шос) Ю. Необходима реализовать доступ к этим блокам в следующем порядке: яОЬОсе<гаее ~090ЬОю»е!»(вевпвп»у! 6»д»п2Ьев»г»с!Ь»ЬздвпзХзе»»(в!гв ° ° . (19) Тогда они появятся на соответствующих дисках 01234 01240 01111 22222 23333 33334 ..., (20) так что наилучший вариант для нас — вводить их следующим образом. Такт 1 Такт 2 Такт 3 Такт 4 Такт 5 авЬосе»6)ее ~одойосг!1! е! етЬ»Ь!»(в»(з»(ад! Ьз? ? а!авда? Такт б Такт 7 Такт 8 Такт 9 (21) У!»зов ' ' евзз ' »(»е» .
<(в К тому моменту, когда понадобится использовать блок !(в, придется уже прочесть »(в и еще 15 блоков следующих за нпм данных, обозначенных через "?", вследствие переполнения на диске 3. А это нельзя сделать, не организовав семь буферов, в котоРых содеРжатсЯ остатки от ав, Ьз, с», е», ув, д! и Ь!. Таким обРазом, в нашем примере потребуется пространство в памяти для, по крайней мере, (1б + 8+ 5)В входных записей. Вместо этого при использовании обычной процедуры распределения суперблоков при разделении дисков будем считывать блоки аеа! атава» на такте 1, 6оЬ! Ь»6!6»вЂ” нэ такте 2, . ° Ьой»ЬзйзЬ» — на такте 8, »?в»(в»(г»»в!»в — на такте 9 (поскольку следующим нам понадобится суперблок г(вЫв»1т»?в»(в) и т.
д. Использование стратегии Яупс8ог! потребует буферов для хранения (Р + 3)ЮВ записей и РРВ указателей в оперативной памяти. Можно показать, что более динамичный подход, упомянутый вылив, потребует не более половины этого объема буферов, но по-прежнему объем к~ = 3, хз = 1, хз = 4, ха = 1, зь = О, яв = 4, яг = 2, яв = 1 (22) (это цифры в числе я) для серий а, 6, ..., Ь. Таким образом, если перечислить данные блоки в хронологическом порядке, на соответствукпцих дисках будет содержаться следующее. Диск Блоки О: ее 1: Ьо 6о Ье е~ 2: йв 4 ез 3: ое ~12 4: се "за~ Л ат П4С~ Л пз и ь, Уз Ые .. ез 6, 9з еа (23) необходимой оперативной памяти почти пропорционален РОВ прн больших Р н Р (см.
упр. 24). В работе В.. Б. Багге, Е. Г. Стоге, 3. Я. ~ъ1мег, Ршайе1 СошриГш6 23 (1997), 601-631, показано, что небольшая модификация этого подхода с независимыми блоками позволяет получить алгоритм, который практически полностью использует скорость обмена данными с диском, но при этом требует буферов всего лишь для 0(Р + )2 1ок О) блоков вместо П(РХ>), Предложенная в работе технология рандомизироеанного разделения (гапИошгаед з1пр1пд) предполагает помещение блока у серии lс на диск (кь + у) шод В, где тя — случайное число, которое выбирается как раз перед тем, как будет впервые записана серия к.
Вместо того чтобы постоянно использовать в качестве исходных данных Р блоков по одному с каждого диска, применяется довольно простой механизм отслеживания наступления момента, когда не оказывается достаточного пространства для выполнения чтения вперед с определенных дисков. В приведенной выше работе доказано„ что этот метод асимптотическн стремится к оптимальному. Для того чтобы реализовать Р-путевое слияние на П дисках с рандомизированным разделением, нужно организовать 20 + Р + Ц вЂ” 1 буферов плавающего ввода, каждый для одного блока из В записей.
Исходные данные, как правило, считываются в .0 из этих буферов, называемых акшивнмми буферами чтиеннл. В то же время Р нз оставшихся буферов содержат лидирующие блоки, записи из которых в текущий момент участвуют в слиянии. Такие буфера называются акшивнььии буферами слияния. Оставшиеся Р+ Ц вЂ” 1 прочих "разношерстных" буферов либо пусты, либо содержат данные, которые понадобятся позже.
Неотрицательный параметр (~ можно увеличить в процессе настройки системы, чтобы уменыпить вероятность возникновения ситуации, когда придется выполнять повторное чтение с любого из дисков. Блоки всех серий можно скомпоновать в хронологическом порядке, как в (19): первыми идут блоки О каждой серии, за ними следуют другие, поздерживая при этом порядок, в котором освобождаются активные буфера слияния. Как было показано выше, такой порядок определен последними ключами в каждом блоке, так что несложно предсказать, какой из блоков может потребоваться первым. Вновь рассмотрим пример (19), приняв Р = 8, Ю = 5 и с„= 4.
Теперь в нашем распоряжении имеется только 2Р + Р+ Я вЂ” 1 = 21 буферов для исходных блоков вместо 29, которые нужны были ранее для обеспечения максимальной скорости считывания. Будем использовать смещения .
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
