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

В 1948 году миссис Гольбертон придумала интересный способ выполнения двухпутевого слияния с полным совмещением чтения, записи и вычислений с использованием шести буферов ввода. Для каждого вводного файла имелись один "текущий" буфер и два "'вспомогательных" буфера; она предложила так организовать слияние, что всякий раз, когда приходило время вывода одного блока, два текущих буфера ввода содержали вместе одни блок необработанных данных.

Следовательно, за время формирования каждого выводного блока ровно один буфер ввода становился пустым и можно было организовать работу так, чтобы три вспомогательных буфера из четырех оказывались заполненными всякий рвз, когда данные читались в оставшийся буфер. Этот метод чуть быстрее метода прогнозирования (см. алгоритм 5.4.6Е), так как иет необходимости проверять результат одного ввода перед началом следующего. [См.

Со)!виол Мейодэ Гог сЬе ()1хЛхАС Буэсет (ЕсЫхс-МаисЛ!у Сотрцсег Согр., 1950), 2 то1шпев.] Кульминацией этой работы стало создание генератора программ сортировки, который был первой крупной программой, разработанной для автоматического программирования. Пользователь указывал размер записи; позиции ключей (до вятн) в частичных полях каждой записи и "концевые" ключи, отмечающие конец файла, и после этого генератор сортировки порождал требуемую программу сортировки для файлов на одной бобине. На первом проходе этой программы выполнялась внутренняя сортировка блоков по 60 слов с использованием метода сравнения и подсчета (алгоритм 5.2С); затем выполнялось несколько сбалансированных двухпутевых проходов слияния с обратным чтением, исключающих сцепление лент, как описано выше.

[См. Маасег Сепегас!пд Конг!ле 1ог 2-яву Богс!п8 (Ес(сегс-МапсЫу П!г!э!оп о1 Кепппйсоп Каис!, 1952). Первый набросок этого доклада был озаглавлен "Основная составляющая программа двухпутевого слияния" (Маясег РгеуаЬНсаНоп Копс!пе 1ог 2-ъау Со!)ас!оп)! См. также Е. Е. Но!Ьегсоп, Яушроэ!пт ол Аисотас!с Рго8гагптт8 (ОЖсе о1 !чаха! КеэеахсЛ, 1954), 34-39.] К 1952 году многие методы внутренней сортировки прочно вошли в программистский фольклор, но теория была развита сравнительно слабо. Даниэль Гольденберг (Пап!е! Со!бепЬег8) [Типе апа(уэш о1 изг(опэ тесбос(э оу эогс!л8 х(аса, Г!!8!са! Сопсросег 1аЬохасогу шепю М-1680 (Маав. 1пэс.

оГ ТесЬ., 17 ОссоЬех, 1952)] запрограммировал для машины ЖЛ!г!ячпс! сошрцсег пять различных методов и выполнил анализ наилучшего и наихудшего случаев для каждой программы. Он нашел, что для сортировки сотни 15-битовых записей по 8-битовому ключу наилучшие по скорости результаты получаются в том случае, если используется таблица нз 256 слов и каждая запись помещается в единственную соответствующую ее ключу позицию, а затем эта таблица сжимается. Однако данный метод имел очевидный недостаток: запись уничтожалась, если последующая имела тот же ключ.

Оста ьные четыре проанализированных метода были ранжированы следующим образом: прямое двухпутевое слияние лучше поразрядной сортировки с основанием 2, которая лучше простого выбора, который, в свою очередь, лучше метода пузырька. Эти результаты получили дальнейшее развитие в диссертации Гарольда Х. Сьюворда (Наго!6 Н. 8еиагб) в 1954 году [1п1огхпас!ол эогс!п8 !л йе арр!!сас!оп оуе!ессгоп!с сс!8!са! сотрнсегз со Ьпэ!пеаэ орехас!олэ, В!8!са! Согпрцсег ЬаЬ. герогс К-232 (Маэз. 1пэС. о( ТесЛ., 24 Мау, 1954; 60 радев)). Сьюворд высказал вдеи распределяющего подсчета и выбора с замещением. Он показал, что первый отрезок случайной перестановки имеет среднюю длину е — 1, н проанализировал наряду с методами внутренней сортировки методы внешней сортировки, причем не только на магнитных лентах, но и на устройствах внешней памяти других типов. Еще более достойная внимания диссертация — на этот раз докторская— была написана Говардом Б.

Демутом (Новагс! В. ВепшсЛ) в 1956 голу [Е!ессгоп!с Паса БогНп8 (Зсап(огс! Еп!тетя!су, ОссоЬег, 1956), 92 райез; 1ЕЕЕ Тхалэ. С-34 (1985), 296-310[. Эта работа помогла заложить основы теории сложности вычислений. В ней рассматривались три абстрактные модели задачи сортировки: с использованием циклической памяти, линейной памяти и памяти с произвольным доступом; для каждой модели были разработаны оптимальные или почти оптимальные методы. (См. упр.

5.3.4-68.) Хотя непосредственно из диссертации Демута, ие вытекает никаких практических следствий, в ней содержатся важные идеи о том, как связать теорию с практикой. Таким образом, история решения проблемы сортировки тесно связана с большинством этапов развития вычислительной техники: с первыми машинами для обработки данных, первыми хранимыми программами, первым программным продуктом, первыми мегодамн буферизации, первой работой по анализу алгоритмов и сложности вычиг чений. Ни один нз документов, касакицихся ЭВМ и упомянутых выше, не появлялся в "открытой литературе': Так уж случилось, что почти вся ранняя история вычислительньж машин отражена в сравнительно труднодоступных докладах, поскольку относительно немного людей было в то время связано с вычислительной техникой.

Наконец, в 1955 и 1956 годах литература о сортировке проникает в печать в виде трех больших обзорных статей. Первая статья была подготовлена Дж. К. Хоскеном (Л. С. Ноэйеп) [Ргос. Еаэгегл Лнлг Сош1зигег Солгегепсе 8 (1955), 39 — 55[. Он начинает с тонкого наблюдения: "Чтобы снизить стоимость единицы результата, люди обычно укрупняют операции. Но при этом стоимость единицы сортировки не уменьшается, а возрастает'! Хоскен описал все оборудование специатьного назначения, имевшееся в продаже, а также методы сортировки с использованном существовавших на то время ЭВМ. Его библиография включает 54 ссылки и основана большей частью на брошюрах фирм-изготовителей. Подробная статья Э.

Е Френда (Е. Н. ЕПепб) Яогйля оп Е!ее~гоше Сошршег Яуэсешэ [.УАСМ 3 (1956), 134-168~ явилась важной вехой в развитии технологии сортировки. Хотя за время, прошедшее с 1956 года, было разработано множество методов, эта статья все еще необычно современна во многих отношениях. Фрэнд дал тщательное описание весьма большого числа алгоритмов внутренней и внешней сортировки и обратил особое внимание на методы буферизации и характеристики накопителей на магнитных лентах. Он предложил некоторые новые методы (например, выбор из дерева, метод двуглавого змия и прогнозирования) и проанализировал некоторые математические свойства старых методов. Третий обзор по сортировке, который появился в то время. был подготовлен Д.

У, Дэвисом (В. %. Вагбеэ) [Ргос. Ььэа Е1еск Епя1леегэ 103В, Бпрр1ешепг 1 (1956), 87-93[, В последующие годы было опубликовано еще несколько прекрасных обзоров: 11. А. Вей [Сошр, 7. 1 (1958), 71-77[, А. 8. Вопй!аэ [Сотр. Х 2 (1959), 1-9[:, В. Р. МсСгас1сеп, Н. Же1ээ, Т.

Бее [Ргодгатш1лй Впяпеээ Сошрпгегэ (Нею Уогк: %'!!еу, 1959), СЬаргег 15, радев 298-332[, 1. Е1огеэ [2АСМ 8 (1961), 41-80[, К. Е. 1хегэоп [А Ргойгшпаплй Еалйиайе (Незг Ъог)г: %11еу, 1962), СЬарсег 6, 176-245[, С. С. Оог11еЬ (С4СМ 6 (1963), 194-201[, Т. Н. Н1ЬЬагб [САСМ 6 (1963), 206-213[, М. А. Ооеш [В181Ы Сошри1ег Пэег'э Напг)боои, ео1сеп Ьу М. К!егег апб С, А. Когп (Не» Уогйп МсСгаъ-НВ!, 1967), СЬаргег 1.10, радев 1,292 — 1.320[. В ноябре 1962 года АСМ организовала симпозиум по сортировке (ббльшая часть работ, представленных на этом симпозиуме, опубликовала в мае 1963 года в выпуске САСМ). Они дают хорошее представление о состоянии работ в этой области на то время.

Обзор К. К. Готлиба (С. С. ОосйеЬ) о современных генераторах сортировки, обзор Т. Н. Хиббарда (Т. К. Н~ЬЬагб) о внутренней сортировке с минимальной памятью и раннее исследование Дж. А. Хаббарда (О. Н. НцЬЬап1) о сортировке файлов на дисках — статьи из этого сборника, заслуживающие наибольшего внимания. За прошедший период были открыты новые методы сортировки: вычисление адреса (1956), слияние с вставкой (1959), обменная поразрядная сортировка (1959), каскадное слияние (1959), метод Шелла с убывающим смещением (1959), миогофазное слияние (1960), вставки в дерево (1960) „осциллирующая сортировка (1962), быстрая сортировка Хоара (1962), пирамидальная сортировка Уильямса (1964), обменная сортировка со слиянием Бэтчера (1964).

История каждого отдельного алгоритма прослеживается в тех разделах настоящей главы, в которых этот метод описывается. Конец 60-х годов нашего столетия ознаменовался интенсивным развитием соответствующей теории. Полная библиография всех работ, изученных автором при написании н подготовке первого издания этой главы и составленная с помощью Р. Л. Ривест (Н. 1.

М- геее), приводится в сотрист8 негееке 13 (1972), 283-289. Последние достижения. Со времени выхода из печати первого издания этой книги (1970 г.) появилось много сообщений об изобретении новых алгоритмов сортировки, однако почти все они являются вариациями уже известных алгоритмов. Бмстрал сортировка на мкохсестве ключей, которая обсуждалась в упр. 5.2,2 — 30, представляет собой прекрасный пример таких более новых методов. Другая тенденция в этой области, представляющая, скорее, теоретический интерес, — изучение адатливкмх схем сортировки. Такие схемы по замыслу разработчиков должны гарантировать более быстрое выполнение сортировки в <лучаях, когда входная последовательность удовлетворяет какому-либо из заранее установленных критериев. 1См., например, Н.

Мапп11а, 1ЕЕЕ Тгалеасе)опе С-34 (1985), 318-325; Ч. ЕеспчП-Саясго, П. %ооо, Сошрие!п8 Яиггеуе 24 (1992), 441-476; С, Ьетсороп1ое, О. Ре1егееоп, 2оигпа1 ог А1яопйше 14 (1993), 395-413; А. Мо(1ае, О. Еооу, О. Ресегезоп, Яойкаге Ргасбсе 3с Ехрепепсе 26 (1996), 781-797.) Разительные изменения в характеристиках аппаратного обеспечения современных компьютерных систем стимулировали интерес к исследованию проблемы эффективности алгоритмов сортировки при совершенно новых критериях стоимости затрат. (См., например, обсуждение применения виртуальной памяти в упр.