Д. Кнут - Искусство программирования том 3 (2-е издание) - 2001 (Часть 1) (1119456), страница 88
Текст из файла (страница 88)
85 (на котором показан случай для пяти лент), ближе к прямыи линиям для многофазного алгоритма; каскадный метод превосходит многофазный на шести лентах для 14 < 5 < 15 и 43 < 5 < 55 вблизи еточных" каскадных чисел 15 и 55, но многофазное распределение по алгоритму 5.4.2ат лучше или, по крайней мере, не хуже для всех остальных 5 < 100. Каскадный метод предпочтительнее многофазного при 5 е оа, но на практике 5 не может быть слишком большим. Заниженная оценка в примере 9 обусловлена аналогичными обстоятельствами, "миогофазная сортировка лучше осциллирующей, несмотря на то что, как следует из аснмптотического выражения, для больших 5 осциллирующая сортировка будет наилучшей.
Несколько дополнительных замечаний. Сейчас самое время сделать несколько более или менее случайных замечаний относительно ленточного ыияния. е Приведенные формулы показывают, что сортировка является, в сущности, функцией от произведения д7 и С, а не те' и С по отдельности. За исключением нескольких относительно незначительных соображений (например, что В выбирается кратным С) из наших формул следует, что сортировка миллиона записей по 10 символов займет примерно столько же времени, сколько сортировка 100000 записей по 100 символов. На самом деле здесь может появиться различие, которое невозможно обнаружить в наших формулах, так как во время выбора с замещением некоторое пространство используется'для полей связи.
В любом случае размер ключа едва ли окажет какое-либо влияние, если только ключи не будут сталь длинными и сложными, что внутренние вычисления не смогут угнаться за работой НМЛ, При длинных записях и коротких ключах соблазнительно выделить ключи, рассортировать их, а затем как-нибудь переставить записи целиком. Но зта идея, кажется, не работает: она может только отсрочить агонию, поскольку процедура окончательной перестановки требует почти столько же времени, сколько потребовала бы обшепринятая сортировка методом слияния. ° Разрабатывая программу сортировки, которая должна использоваться многократно, разумно очень тщательно оценить время работы и сравнить теорию с действительными наблюдаемыми характеристиками выполнения.
Так как теория сортировки развита довольно хорошо, эта процедура, как известно, способна внезапно выявить дефекты в оборудовании или программном обеспечении ввода-вывода в существующих системах. Оказывается, обслуживание выполнялось медленнее, чем следовало, и никто этого не замечал, пока данный недостаток не проявился на программе сортировки! в Наш анализ выбора с замещением был выполнен в предположении, что данные в файле расположены случайно, но файлы, встречакициеся на ирак гике, очень часто уже являются упорядоченными в той или иной степени.
(Фактически иногда пользователи обращаются к сортировке файлов, уже упорядоченных ранее, толысо для того, чтобы убедиться в этом.) Таким образом, опыт даже в большей мере, чем указывают наши формулы, показал., что выбор с замещением предпочтительнее других видов внутренней сортировки. Данное преимущество несколько ослабляется в случае многофазной сортировки с обратным чтением, так как должен быть порожден ряд убывающих серий; на самом деле Р. Л. Гилстад (11. 1.. С1)втаб) (он первым опубликовал описание метода многофазного слияния) первоначально по этой причине отверг метод обратного чтения. Но позднее ои заметил, что чередование направлений будет все же давать длинные возрастакнцие серии. Кроме того, многофазный метод с обратным чтением — это единственный стандартный метод, который благосклонен к убывающим входным файлам в той же степени, что и к возрастающим.
в Другое преимущество выбора с замещением состоит в том, что этот метод допускает совмещение процессов чтения, записи и вычислений. Если бы мы просто выполняли внутреннюю сортировку очевидным способом — заполнили память, расссортировали данные в ней н затем записывали данные по мере того. как память заполняется новым содержимым, — то проход распределения занял бы примерно вдвое больше времени, Из рассмотренных нами методов внутренней сортировки еще только один можно приспособить к одновременному чтению, записи и вычислениям — пирамидальную сортировку. (Эта идея была использована при подготовке примера 10 диаграммы А.) Предположим для удобства, что внутренняя память содержит 1 000 записей, а каждый блок на ленте — по 100.
Действовать можно следующим образом (через Вд... В~ в обозначено содержимое памяти, разделенной на 10 блоков по 100 записей) . Шаг О. Заполнить память и сделать так, чтобы элементы Вз... В~е удовлетворяли неравенствам пирамиды (с наименьшим элементом в вершине). Шаг 1. Свести В~...
Вю в пирамиду, затем выбрать наименьшие 100 записей и переписать их в В~е. Шаг 2. Записать из Вю, в то же время выбрать наименылне 100 записей из В~ ... Вэ и поместить их в Вэ, Шаг Я. Прочитать в В~е и записать в Вэ; в то же время выбрать наименьшие 100 записей из В~... Вэ и поместить их в Вв. Шаг 9.
Прочитать в Ва и записать из Вз, в то же время выбрать наименьшие 100 записей из В~ Вв, поместить их в Вз и сделать так, чтобы неравенства пирамиды были справедливы для Вз .. В~о. Шаг 10. Прочитать в Вз и записать из Вт, сортируя В~, в то же время сделать так, чтобы неравенства пирамиды были справедливы для В4 .. Взо. Шаг 11. Прочитать в Вз и записать из В~, .в то же время сделать так, чтобы Вз... В~е удовлетворяли неравенствам пирамиды. Шаг 1в.
Прочитать в Вы делая так, чтобы Вт... Вю удовлетворяли неравенствам пирамиды. Вернуться к шагу 1. ° Мы предполагаем, что число сортируемых записей дг заранее неизвестно. На самом же деле большинство компьютеров позволяет постоянно следить за числом записей во всех файлах н можно считать, что наша вычислительная система способна сообщить значение )У. Насколько существенно нам бы это помогло? К сожалению, не очень! Мы видели, что выбор с замещением весьма выгоден, но он ведет к непредсказуемому числу начальных серий. В сбалансярованном слиянии мы могли бы использовать информацию о ?г' для установления такого размера буфера В, чтобы о' оказалось, скорее всего, чуть меньше степени Р; в многофвзном распределении с оптимальным размещением фиктивных серий мы могли бы использовать информацию о г? чтобы решить, какой уровень выбрать !см.
табл. 5.4.2-2). ° НМЛ часто оказываются наименее надежными устройствами в вычислительной технике. Следовательно, можно принять за аксиому, что исходная вводная лвнгпа ни в коем случае ив долоюна изменлщьсл, пока не станет известно, что вся сортировка удовлетворищельно «аверюена.
В некоторых примерах на диаграмме А существует досадное "время, пока оператор сменит ленту", но было бы слишком рискованно затирать исходные данные ввиду возможности появления какого-либо сбоя во время длинной сортировки. ° Прн переходе от прямой записи к обратному чтению мы можем сэкономить некоторое время, вовсе не записывая последний буфер на ленту; он в любом случае будет вновь прочитан.
Диаграмма А показывает, что этот прием в действительности экономит сравнительно немного времени, за исключением случая осцнллирующей сортировки, когда направления меняются часто. в Хотя в большинстве вычислительных систем имеется достаточно много НМЛ, было бы стишком рискованно все их использовать в процессе сортировки. Рекомендуемое процентное отношение находится в диапазоне между !око В и !икр+, Я н не очень велико при достаточно большом Р. Более высокий порядок сортировки влечет за собой, как правило, использование небольших по размеру блоков, Подумайте также о бедном операторе компьютера, который должен устанавливать все эти рабочие ленты! С другой стороны, в упр. 12 описан интересный способ использования дополнительных НМЛ, группируемых так, чтобы совместить время ввода н вывода без увеличения порядка слияния.
° При использовании компьютеров, подобных ИХХ, которые имеют фиксированный и довольно маленький размер блоков, для слияния едва ли требуется много внутренней памяти, Здесь осциллирующая сортировка более предпочтительна, потому что становится возможным сохранять дерево выбора с замещением в памяти во время слияния.
На самом деле в этом случае можно усовершенствовать осциллирующую сортировку (как предложил К. Дж. Белл !С. Л, Ве!!) в 1962 году), сливая новую начальную серию с выводом каждый раз. когда выполняется слияние с рабочих лент! ° Мы видели, что файлы на нескольких бобинах должны сортироваться последовательно бобина за бобиной, чтобы избежать чрезмерной работы, связанной с перестановкой лент. Иногда такого рода приложения называются многобобинными.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
