чтения r{4,20)L/D « 1.785L/4 блоков с единственного диска. Эта теоретическая оценка верхней границы довольно консервативна; на практике результаты бывают даже лучше - они колеблются в пределах оптимального времени L/4.

Таблица 2

ГАРАНТИРОВАННАЯ ПРОИЗВОДИТЕЛЬНОСТЬ ПРИ РАНДОМИЗИРОВАННОМ

РАЗДЕЛЕНИИ

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

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

Здесь Pj - к тогда и только тогда, когда qu = j. Два процесса сортировки на стадиях (Ш) и (v) сравнительно быстрые (иногда можно обойтись внутренней сортировкой), так как записи не слишком длинные. На стадии (vi) задача сведена к сортировке файла, ключи которого - просто числа {1,2,..., iV}. Каждая запись теперь определяет в точности то место, куда ее следует переместить.

Внешняя перекомпоновка записей, остающаяся после стадии (vi), на первый взгляд кажется тривиальной, но фактически она очень сложна, и все еще не найдено ни одного действительно хорошего алгоритма (существенно лучшего, чем алгоритм для сортировки). Мы, очевидно, могли бы выполнить перекомпоновку за N шагов, перемещая всякий раз по одной записи. Для достаточно большого N это лучше, чем NlogN в методах сортировки, хотя N никогда не бывает таким большим. Но N все-таки достаточно велико, чтобы сделать N поисков просто нереальными.

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

Но, с другой стороны, представляется уж слишком расточительным выполнять сортировку ключей после того, как они уже были рассортированы. Одна из причин возникновения проблемы, связанной с внешним переразмещением, была открыта Р. У. Флойдом, который нашел нетривиальную нижнюю границу для числа поисков, необходимых для перестановки записей в дисковом файле [Complexity of Computer Computations (New York: Plenum, 1972), 105-109].

Результат Флойда удобно описать, воспользовавшись аналогией с лифтом, как в разделе 5.4.8. На этот раз найдем график работы лифта, минимизирующий число остановок, а не пройденное расстояние. (Минимизация числа остановок не вполне эквивалентна нахождению алгоритма перегруппировки с минимальным числом поисков, так как одна остановка объединяет вход в лифт с выходом из него. Однако разница не слишком велика, и мы воспользуемся критерием минимизации остановок, чтобы пояснить основные идеи.)

Будем использовать функцию дискретной энтропии

F{n)= ([Igfc]+1) =B(n)+n-l = nrignl-2Г8"1-t-n, (25)

1<*;<гг

где В{п) есть функция бинарной вставки (см. формулу 5.3.1-(3)). Согласно 5.3.1-(34) функция F{n) - это не что иное, как минимальная длина внешнего пути бинарного дерева с тг листьями, и

nlgn <F(n) < nig n-t-0.0861гг. (26)

Так как F{ti) выпукла и удовлетворяет условию F{ti) - п + F([n/2J) + F("n/2]), согласно сформулированной выше лемме С

F{ti) < F{k) +F{Ti-k)+Ti при О < < п. (27)

Это соотношение вытекает также из представления F в виде длины внешнего пути; в дальнейшем оно окажется решающим аргументом в наших рассуждениях.

Как и в разделе 5.4.8, предположим, что лифт вмещает m человек, каждый этаж вмещает b человек и имеется тг этажей. Пусть - число людей, находящихся в данный момент на этаже г и стремящихся попасть на этаж j. По определению оценка совместности любого расположения людей в здании есть Yli<i.j<n iij)-

Предположим, например, что Ь = т = п = 6и что первоначально 36 человек следующим образом распределены между этажами:

UUUUUU ,пе\

123456 123456 123456 123456 123456 123456"

Лифт пуст и находится на этаже 1; "и" обозначает свободное место. На каждом этаже имеется по одному человеку, стремящемуся попасть на каждый из этажей.

поэтому все величины s- равны 1 и оценка совместности равна 0. Если теперь лифт отвезет 6 человек на этаж 2, то мы получим расположение

123456 .

UUUUUU 123456 123456 123456 123456 123456 "

и оценка совместности станет равной 6F(0) + 24F(1) + 6F(2) = 12. Допустим, лифт перевезет 1, 1, 2, 3, 3 и 4 на этаж 3:

112334 ,

UUUUUU 245566 123456 123456 123456 123456

Оценка совместности изменится до 4F(2) + 2F(3) = 18. Когда каждый пассажир будет, в конце концов, перевезен к своему месту назначения, оценка совместности станет равной 6F(6) = 96.

Флойд заметил, что оценка совместности никогда не увеличивается больше чем на Ь + m за одну остановку, так как множество из s пассажиров с одним пунктом назначения, объединяясь с аналогичным множеством мощности s, увеличивает оценку на F(s + s) - F{s) - F{s) < s + s. Таким образом, имеем следующий результат.

Теорема F. Пусть t - определенная выше оценка совместности начального расположения пассажиров. Лифт должен сделать по крайней мере

\F{b)n-t)l{b + m)

остановок, чтобы доставить всех пассажиров к их месту назначения.

Сформулируем этот результат применительно к дискам. Допустим, что имеется Ьп записей по Ь в каждом блоке, и предположим, что в оперативной памяти одновременно помещается т записей. При каждом чтении с диска один блок переносится в память, а при каждой записи один блок помещается на диск, и Sij есть число записей в блоке г, принадлежащих блоку j. Если гг > Ь, то существует начальное расположение, для которого все < 1, так что t = Q. Следовательно, для переразмещения записей необходимо выполнить хотя бы f{b)n/{b + m) к {bn\gb)/m операций чтения блока. (Если b велико, то множитель Igb делает эту нижнюю оценку нетривиальной.) В упр. 17 выведена несколько более строгая нижняя оценка для общего случая, когда m существенно больше Ь.

УПРАЖНЕНИЯ

1. [М22] В тексте раздела анализируется метод, с помощью которого среднее время ожидания, необходимое дтя чтения доли х дорожки, уменьшается с до (1 - х) оборотов. Это минимально возможное время, когда имеется один держатель головок. Каково соответствующее минимальное время ожидания, если имеется два держателя головок, разнесенных на 180° (в предположении, что в любой момент данные могут передаваться только через головки на одном из держателей)?

2. [МЗО] (А. Г. Конхейм (А. G. Konheim).) Назначение этого упражнения - исследовать, на какое расстояние должен переместиться держатель головок во время слияния файлов, расположенных "ортогонально" к цилиндрам. Допустим, имеется Р файлов, в каждом из которых содержится L блоков записей, и предположим, что первый блок каждого файла находится на цилиндре 1, второй - на цилиндре 2 и т. д. Движением