Д. Кнут - Искусство программирования том 3 (2-е издание) - 2001 (Часть 2)

"Случайиьэе" смещения в (22) в сочетании с последовательным разделением внутри каждой серии, будут стремиться к минимизации '"заторов" в любой отдельной хронологической последовательности. В данном слу эае система будет работать следующим образом. Активные Активные считывания слияния Прочие В ожидании Ц икл 1 еободооосо — — — — — — — — ( — — — — — — — — ) ао Цикл 2 1эйоаэдгуо ао — — — — — — — босо(водо — — — — ) с?о Цикл 3 агбоегд, 1з аобо со~о — — — — еоуодо(аэсЬЛ вЂ” — ) Ьо Цикл 4 агеэбэдэаэ аобосодоеоУодобо А(дгегдз7эдэаг — ) еэ (24) Цикл о аз|гбэездг аобосоАеэ!одобо Аегг(заЖбэдэагО Л Цикл б сэазузбгез агб! содзегЬдэбо его(бэдг — — — — ) сэ Цикл 7 ? 4Ио? ? агбэсэазеээгдэбо Ьэбгдгаз1зез( — — ) Аз В каждом очередном цикле поджидается первый в хронологическом порядке блок, который не участвовал в слиянии и не находится в прочих буферах.

Это один из блоков, которые считываются в текущий момент в активный буфер ввода. Предполагается, что компьютер работает значительно быстрее, чем НМД, и, таким образом, все блоки, находящиеся перед тем, который ожидается, уже задействованы в процессе слияния до завершения ввода.

Предполагается также, что в нашем распоряжении имеется достаточный объем буферов и выполнение слияния не задерживается из-за отсутствия места для размещения результата (см. упр. 26). Когда завершится цикл ввода, блок, который мы ожидаем, немедленно классифицируется как прпнщ1лежащий активному буферу слияния, а опустевший буфер слияния, который, таким образом, выведен из этой категории, будет использоваться в составе активных буферов чтения. Другие Ю вЂ” 1 активных буферов чтения выбираются среди Ю вЂ” 1 наименее важных прочих буферов. Буфера этой последней группы ранжируются в хронологическом порядке по содержимому.

В следующем цикле нам придется ожидать первый блок, еще не вовлеченный в слияние и не представленный в прочих буферах. Любой из прочих буферов, предшествующих этому блоку в хронологическом порядке, становится частью группы активных буферов слияния прежде, чем начнется очередной цикл ввода, но другие — показанные выше в скобках — сохранят свой статус прочего буфера в следующем цикле.

Однако в следующий цикл с сохранением статуса может быть перенесено не более Д из этих буферов в скобках, поскольку придется передать Ю вЂ” 1 прочих буферов в группу активных буферов чтения сразу после того, как будет получен сигнал о готовности к вводу. Любой дополнительный буфер из группы прочих может явно очищаться, как если бы содержащаяся в нем информация еще и не считывалась. Такая очистка выполняется, например, в цикле 4 в (24): невозможно обработать все шесть блоков Ае ИэЛдэаг в течение цикла 5, поскольку Я = 4, Так что придется повторно прочесть дэ и аз. В противном же случае чтение выполняется на полной скорости, В упр, 29 доказано, что для любой заданной хронологической последовательности серий,которьэе должны быть слиты, метод рандомизированного разделения позволяет достичь в среднем минимального числа операций чтения с дисков, пропорционального г(Ю, Я + 2), где функция т табулирована в табл.

2. Например, если Ю = 4 и Я = 18, среднее время выполнения Р-путевого слияния Т, блоков данных с использованием 4 дисков н Р + 25 входных буферов будет не больше времени чтении г(4, 20)1/.0 ж 1.7ВЫ/4 блоков с единственного диска. Эта теоретическая оценка верхней границы довольно консервативна; на практике результаты бывают даже лучше — они колеблются в пределах оптимального времени /./4. Таблица 2 ГАРАНТИРОВАННАЯ ПРОИЗВОДИТЕЛЬНОСТЬ ПРИ РАНДОМИЗИРОВА1Н!ОМ РАЗДЕЛЕНИИ г(4,4) 7(4,24) г(4,34) г(4,44) г(4, Ы) т(4„Ы) г! 4, 74) г(4, 84) э (4, 94) г(4, 104) 1.370 1,353 1.633 1597 1,836 1.787 1.997 1.933 2.130 2.062 2.249 2.174 2.358 2.273 2.464 2.363 2.555 2,450 2.639 2.536 Поможет ли сортировка ключей2 Если записи длинные, а ключи короткие, .

весьма заманчиво создать новый файл, состоящий только из ключей с порядковыми номерами, определяющими их первоначальное положение в файле, После сортировки этого файла ключей можно заменить ключи последовательными числами 1, 2,.... Затем новый файл можно рассортировать по положению в первоначальном файле, в результате чего получится удобное описание того, как "растаеовать" записи, т. е.

окончательно перекомпоновать их в требуемом порядке. Схематически представим процесс так. (л ! -. 11 ) (Кг, 12 ) (Кл, 151 ) (Кг,1)(К2,2)... (К!7,Х) ( 91 ' Р1 ) ( ~~ Гг '. Рг ) ' ' " ( Гя ~ Р~ ) (1 рг)(2 рг)" (Р7:рн) (01,1)(02,2) - (бк,Ж) (01, 11)(02, 12) . "(051, /н) 1) исходный файл й) Файл ключей й() Рассортированный (й) гя) Отредактированный (ш) х) Рассортированный (ьч) 9!) Отредактированный (1) Длинный Короткий Короткий Короткий Короткий Длинный Здесь р. = й тогда и только тогда, когда в, .= 1.

Два процесса сортировки на стадиях (гй) н (7) сравнительно быстрые (иногда можно обойтись внутренней сортировкой), так как записи не слишком длинные. На стадии (71) задача сведена к сортировке файла, ключи которого — просто числа (1. 2,..., Х). Каждая зались теперь определяет в точности то место, куда ее следует переместить. Внешняя перекомпоновка записей, остающаяся после стадии (71), на первый взгляд кажется тривиальной, но фактически она очень сложна, и все еще не найдено ни одного действительно хорошего алгоритма (существенно лучшего, чем алгоритм для сортировки). Мы, очевидно, могли бы выполнить перекомпоновку за )7' шагов, перемещая всякий раз по одной записи. Для достаточно большого Х это лучше„ чем 17 1ок Ж в методах сортировки, хотя А! никогда не бывает та.ким большим. Но !7' все-таки достаточно велико, чтобы сделать А7 поисков просто нереальными, 4=2 4=.

4 4=- 8 бш 16 4 = 32 4=64 4= 128 д.= 256 4 = 512 4= 1024 1.500 1.500 1.499 2.460 2.190 1.986 3.328 2,698 2.365 4.087 3.103 2.662 4.503 3.392 2.917 5.176 3.718 3.165 5.431 3.972 3.356 5.909 4.222 3.536 6.278 4.455 3.7!7 6.567 4.689 ЗМ79 ! Л67 1Л44 1.888 1.785 2.183 2.056 2.434 2.277 2.654 2.458 2.847 2.613 2.992 2.759 3.155 2.910 3.316 3.024 З.4З4 З.мз 1Л22 1. 724 1.969 2.156 2,319 2.465 2.603 2.714 2. 820 2.937 1.393 1.683 1.889 2.067 2.346 2Д59 2.567 2.675 2.780 1,339 1.570 1.743 1.890 2.005 2.

107 2.20! 2.289 2.375 2.452 Р(п) = ~ ' ((18Ц+1) =В(п)+ — 1=в(!8п)-20в"'+и (25) ~<в<в где В(н) есть функция бинарной вставки (см. формулу 5.3.1-(3)). Согласно 5.3.1- (34) функция Е(п) — это пе что иное, как минимальная длина внешнего пути бинарного дерева с и листьями, и п!йп < Г(п) < и 18п+ 0.0861п. Так как Г(п) выпукла и удовлетворяет условию Е(п) = и + г ((и/2)) + г () и/2)), согласно сформушированной выше лемме С Е(п) < Г(Ь)+Г(п — Ь)+н при 0 < й < и. (27) Это соотношение вытекает также из представлении Е в виде длины внешнего пути; в дальнейшем оно окажется решающим аргументом в наших рассуждениях. Как и в разделе 5,4.8, предположим, что лифт вмещает гп человек, каждый этаж вмещает Ь человек и имеется и этажей.

Пусть в," — число людей, находящихся в данный момент па этаже 1 и стремящихся попасть на этаж у, По определению оценка совместности любого расположении людей в здании есть ~,<, .<„г (вц). Предположим, например, что Ь = гп =- и = 6 и что первоначально 36 человек следующим образом распределены между этажами: виооиц 123456 123456 123456 123456 123456 123456 (28) Лифт пуст и находится на этаже 1; "н" обозначает свободное место.

На каждом этаже имеется по одному человеку, стремящемуся попасть на каждый из этажей., К отредактировэлным записям можно эффективно применять какой-либо метод поразрядной сортировки, поскольку ключи имеют строго равномерное распределение. На многих современных быстродействующих компьютерах время вычислений для 8-путевого распределения значительно меньше, чем время вычислений для 8-путевого слияния. Следовательно, распределительная сортировка может быть наилучшей из всех процедур (см. раздел 5.4.7, а также упр. 19).

Но, с другой стороны, представляется уж слишком расточительным выполнять сортировку ключей после того, как они уже были рассортированы. Одна из причин возникновения проблемы, связанной с внешним переразмещением, была открыта Р. У, Флойдом, который нашел нетривиальную нижнюю гранину для числа поисков, необходимых для перестановки записей в дисковом файле (Согпр1ехйу оГ Сошригег СошрпгаМопз (Меж Ъог1с: Р1епшп, 1972), 105-109]. Результат Флойда удобно описать, воспользовавшись аналогией с лифтом, как в разделе 5,4.8. На этот раз найдем график работы лифта, минимизиру ющий число осгиаиовок, а не пройденное расстояние. (Мннимизадия числа остановок не вполне эквивалентна нахождению алгоритма перегруппировки с минимальным числом поисков, так как одна остановка объединяет вход в лифт с выходом из него.

Однако разница не слишком велика, и мы воспользуемся критерием минимизации остановок, чтобы пояснить основные идеи.) Будем использовать функцию дискретной энтропии поэтому все величины вб равны 1 и оценка совместности равна О. Если теперь лифт отвезет 6 человек на этаж 2, то мы получим расположение 123456 ыыиииы 123456 123456 123456 123456 123456 и оценка совместности станет равной 6Г(О) + 24К(1) + ОГ(2) = 12. Допустим, лифт перевезет 1, 1, 2, 3, 3 н 4 на этаж 3: 112334 иомиури 245566 123456 123456 123456 123456 (ЗО) Оценка совместности изменится до 4Г(2) + 2К(З) = 18. Когда каждый пассажир будет, в конце концов, перевезен к своему месту назначения, оценка совместности станет равной 6Г(б) = 96. Флойд заметил, что оценка совместности никогда не увеличивается больше чем на Ь+ т за одну остановку, так как множество нз в пассажиров с одним пунктом назначения, обьеднняясь с аналогичным множеством мощности в', увеличивает оценку на Г(в*в') — Р(в) — Г(в') ( в+ в'.

Таким образом, имеем следующий результат. Теорема Р. Пусть 1 — опредаченная выше опенка совместности начально~о рас- положенп» пассажиров. Лифт дитжен сделать по крайней мере [(Р'(Ь)п — 1)/(Ь+ т) [ остановок, чтобы доставить всех пассажиров к нх месту пвэиачешш. Сформулируем этот результат применительно к дискам. Допустим, что имеется Ьп записей по Ь в каждом блоке, и предположим, что в оперативной памяти одновременно помещается тп записей. При каждом чтении с диска один блок переносится в память, а при каждой записи один блок помещается на диск, н в,.