AOP_Tom3 (1021738), страница 104
Текст из файла (страница 104)
Однако для бинарных вставок нужна весьма сложная структура данных и Мочли затем показал, что при двухпутевом слиянии достигается столь же малое число сравнений. но используется только последовательный просмотр списков. Последняя часть конспекта его лекции посвящена методам поразрядной сортировки с частичными проходами, которые моделируют цифровую карточную сортировку на четырех лентах, затрачивая менее четырех проходов иа цифру (см, раздел 5.4,7).
Вскоре после этого Эккерт и Мочли организовали компанию, выпустившую некоторые нз самых ранних электронных вычислительных машин 01ХАС (для военных приложений) и ОХ!ЪАС (для коммерческих приложений). Вновь Бюро переписи США сыграло в этом свою роль, приобретя первый СХ1Ъ'АС. В это время далеко не всем было ясно, что ЭВМ станут экономически выгодными: вычислительные машины могли сортировать быстрее. но онн н стоили дороже.
Поэтому программисты С'~1ЪАС под руководством Фрэнсис Э. Гольбертон (ггапсев Е. Но!Ьегтоп) приложили значительные усилия к созданию программ внешней сортировки, работающих с высокой скоростью; их первые программы повлияли также на разработку оборудонання. По нх оценкам 100 млн записей по 10 слон могли быть рассортированы на СХ1ЪАС за 9 000 ч (т. е, за 375 дней). Вычислительная маппша 17Х1~'АС 1, официально запущенная в эксплуатацию в июле 1951 года. имела оперативную память обьемом 1 000 12-буквенных (72-битовых) слов. В ней предусматривались чтение н запись на ленту блоков по 60 слов со скоростью 500 счов в секунду; чтение могло быть прямым или обратным, допускалось совмещение операций чтения, записи и вычислений.
В 1946 году массне Гольбертон придумала интересный способ выполнения двухпутевого глняния с полным совмещением чтения, записи и вычислений с использованием шести буферов ввода. Для каждого вводного файла имелись один "текущий" буфер и два "вспомогательных" буфера; оиа предложила так организовать слияние, что всякий раз, когда приходило время вывода одного блока, два текущих буфера ввода содержали вместе один блок необработанных данных. Следовательно, за время формирования каждого выводного блока ровно один буфер ввода становился пустым и можно было организовать работу так, чтобы три вспомогательных буфера из четырех оказывались заполненными всякий раз, когда данные читались в оставшийся буфер. Этот метод чуть быстрее метода прогнозирования (см. алгоритм 5.4.6Е), так как нет необходимости проверять результат одного ввода перед началом глелующего.
[См. СоНапол МеСЬос)я Гог йе ЬсХ1УАС Яуягет (Ес1сегС-МаисЫу СотриСег Согр., 1950), 2 во1шпея.) Кульминацией этой работы стало создание генератора программ сортировки, который был первой крупной программой, разработанной для автоматического программи!ювания. Пользователь указывал размер записи, позиции ключей (до пяти) в частичных полях каждой записи и "концевые" ключи, отмечающие конец файла, и после этого генератор сортировки порождал требуемую программу сортировки для файлов на одной бобине.
На первом проходе этой щюграммы выполнялась внутренняя сортировка блоков по 60 слов с использованием метода сравнения и подсчета (алгоритм 5.2С); затем выполнялось несколько сбалансированных двухпутевых проходов слияния с обратным чтением, исключающих сцепление лент, как описано выше. )См. Маясег Селегасспд Ноиг!пе Гог 2-в ау ЯогС!пд (Ес1сегС-МаисЫу В!х!я!оп оГ НепшгдСоп Нассс1, 1952). Первый набросок этого доклада был озаглавлен "Основная составляющая программа двухпутевого слияния" (МаяСег РгеГаЬпсаСюл Воис!пе Гог 2-сгау Со!!аС!ол)! См.
также Е. Е. Но1ЬегСоп, Бутроя!ит оп Аиготас!с Ргодгаттслд (ОГбсе оГ Хата! НеяеагсЬ, 1954), 34-39.) К 1952 году многие методы внутренней сортировки прочно вошли в программистский фольклор, но теория была развита сравнительно слабо. Даниэль Гольденберг (Ваше! Со!бепЬегд) ) Типе апа!уяея оГ галоия те!Лог!я оГ яогс!пд с!ага, В!д!Са! СотриСес ЬаЬогаСогу тети М-1680 (Мвяя. 1пяС. оГ ТесЬ., 17 ОссоЪег, 1952)) запрограммировал для машины СУЫг1нпсс! сотрисес пять различных методов и выполнил анализ наилучшего и наихудшего случаев для каждой программы.
Он нашел, что для сортировки сотни 15-битовых записей по 8-битовому ключу наилучшие по скорости результаты получаются в том случае, если используется таблица из 256 слов и каждая запись помещается в единственную соответствующую ее ключу позицию, а затем эта таблица сжимается. Однако данный метод имел очевидный недостаток: запись уничтожалась, если последующая имела тот же ключ. Остальные четыре проанвлизированных метода были ранжированы следуюсцим образом: прямое двухпутевое слияние лучше поразрядной сортировки с основанием 2, которая лучше простого выбора, который, в свою очередь, лучше метода пузырька.
Эти результаты получили дальнейшее развитие в диссертации Гарольда Х. Сьюворда (Наго!й Н. Беи агс!) в 1954 году )1лГогспасюл яогблд !и СЛе арр!!саС!оп оГе!ессгогс!с сГ!д!Са! сотрисегя Со Ьия!паяя орегабопя, В!8!Са! Сотрисег ЬаЬ. герогС Н-232 (Маяя.
1пж. оГ ТесЬ., 24 Мау, 1954; 60 радея)). Сьюворд высказал идеи распределяющего подсчета и выбора с замещением. Он показал, что первый отрезок случайной перестановки имеет среднюю длину е — 1, и проанализировал наряду с методами внутренней сортировки методы внешней сортировки, причем не только на магнитных лентах, но и на устройствах внешней памяти других типов. Еще более достойная внимания диссертация — на этот раз докторская была написана Говардом Б. Демутом (Ножагс! В. ВеппьСЬ) в 1956 году )Е!ее!гол!с Васа догСтд (8СапГогс! Еп!гегюсу, ОссоЬег, 1956), 92 радея; 1ЕЕЕ Тгапя. С-34 (1985), 296-310]. Эта работа помогла заложить основы теории сложности вычислений.
В ней рассматривались три абстрактные модели задачи сортировки: с использованием циклической памяти, линейной памяти и памяти с произвольным доступом; для каждой модели были разработаны оптимальные или почти оптимальные методы. (См. упр. 5.3.4 68.) Хотя непосредственно из диссертации Демута не вытекает никаких практических следствий, в ней содержатся важные идеи о том, как связать теорию с практикой. Таким образом, история решения проблемы сортировки тесно связана с большинством этапов развития вычислительной техники; с первыми машинами для обработки данных, первыми хранимыми программами.
первым программным продуктом, первыми методами буферизации, первой работой по анализу алгоритмов и сложности вычислений. Ни один из документов, касающихся ЭВМ и упомянутых выше, не появлялся в "открытой литературе'. Так уж случилось, что почти вся ранняя история вычислительных машин отражена в сравнительно труднодоступных докладах, поскольку относительно немного лкгдей было в то время связано с вычислительной техникой. Наконец, в 1955 и 1956 годах литература о сортировке проникает в печать в виде трех больших обзорных статей.
Первая статья быта подготовлена Дж. К. Хоскеном (,1. С. Ноз!сеп) 1Ргос. Еаэс егп уотС СотриСег СопХегепсе 8 (1955), 39-55]. Он начинает с тонкого наблюдения: "Чтобы снизить стоимость единицы результата, люди обычно укрупняют операции. Но при этом стоимость единицы сортировки не уменьшается, а возрастает". Хоскен описал все оборудование специального назначения, имевшееся в продаже, а также методы сортировки с использованием существовавших на то время ЭВМ. Его библиография включает 54 ссылки и основана большей часгью на брошюрах фирм-изготовителей.
Подробная статья Э. Г. Френда (Е. Н. Рг!епс!) Яогс!сзВ ол Е1ессготс Созприсег Вуэсепж [ХАСМ 3 (1956), 134 168] явилась важной вехой в развитии технологии сортировки. Хотя за время, прошедшее с 1956 года, было разработано множество методов, эта статья все еще необычно современна во многих отношениях. Фрэнд дал тщательное описание весьма болыпого числа ачгоритьсов внутренней и внешней сортировки и обратил особое внимание на методы буферизации и характеристики накопителей на хсагнитных лентах.
Он предложил некоторыв новые методы (например, выбор из дерева, метод двуглавого змия и прогнозирования) и проанализировал некоторые математические свойства старых методов. Третий обзор по сортировке, который появился в то время, был подготовлен Д. У. Дэвисом (Р. 'сч'.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
