Д. Кнут - Искусство программирования том 3 (2-е издание) - 2001 (Часть 2) (1119371), страница 5
Текст из файла (страница 5)
Вцгеац о1 т1зе Сепвцэ, 1965): см. также сообщения современников Холлерита: СойзглЫа Сойедс Ясйоо) оЕ 51иеа Яиаггег)у 10 (1889), 238-255; 3. ЬталИт 1пэа 129 (1890), 300-306; ТЬе 53есглса! Елйл1еег 12 (ь(о~е1пЬег. 11., 1891), о21-530: Х Ашег. Ягат1вс)са1 Анап, 2 (1891), 330-341, 4 (1895). 365; .У. Йоуа) Ясацвоса) Яос. 55 (1892). 326-327; Адбешеьлев асаивг(всЬеа Агат 2 (1892), 78 126: о. Яос. Яга1)тмн7це с(е Раг1в 33 (1892), 87-96; П. 8. Расел1в 395781 (1889), 685608 (1901), 77г209 (1904).
Холлернт и другой бывший служагций Вк>ро переписи Джеймс Пауэрс (3ашеэ Рошеса) в дальнейшем основали конкурир1зоп1не компании. кото1зые, в конце ~онцо~,. вошли соответственно в корпорации 1ВМ и В.евнин.оп Ва116 согротас1оп. Сортировальная машина Холлерита базировалась, конечно. на методах поразрядной сортировки, используемых в цифровых ЭВМ. В его патенп упоминается. что числовые элементы, содержащие два столбца, должны сортироваться 'по отдельности для каждого столбца", ио он не говорит.
какой столбец (единиц или десятков) должен рассматриваться первым. Патент за номером 518240, выдзнный Джону К. Гору (3ойп К. Соте) в 1894 году, в котором описана другая машина для сортировки, предполагает начинать со столбца десятков. Далеко не очевидная иден сортировки сначала по столбцу единиц была, по-видимому; открыла каким-то неизвестным оператором и передана остальным (см. раздел о.2.5); она имеется в самом раннем сохранившемся руководстве 1В51 по сортировке (1936 г.). Насколько мне известно, впервые метод "справа, налево"' упоминается в книге ВоЬегс Ре1пс()ег, Паз НоНегВЬ-7.осЬ!шггеп-ЪеНайгеп (Вег1!и: Вейпаг НоЬЬ!п8, 1929), 126 — 130; почти в зто же время он упоминается в статье Л.
Дж. Комри (1.. 3. Сошг!е), Хгапзас!!олз оу гйе О(бс» Мас!олегу Пзегз' Аваос!агюп (1лпдоп, 1930), 25-37. Кстати, Комри оказалгя первым, кто сделал следующее важное наблюдение; табуляторы можно с успехом использовать для выполнения научных расчетов, хотя первоначально они создавались для статистических и бухгалтерских приложений. Его статья особенно интересна, поскольку содержит подробное описание табуляторов, имевшихся в Англии в 1930 году.
Сортировальные машины в то время обрабатывали от 360 до 400 карт в минуту и сдавались в аренду за 9 фунтов стерлингов в месяц. Идея слияния восходит к другому устройству для обработки карт — подборочкой машине (сойагог), которая была изобретена значительно позднее, в 1938 году.
Снабженная двумя подающими механизмами, она могла слить две рассортированные колоды карт в одну всего за один проход; метод выполнения этого слияния хороню описан в первом руководстве 1ВМ по методам подборки (апрель 1939 года). (Сьь Лахпез Ж. Вгусе, П. В. Раселс 2189024 (1940).) Затем на сцене появились ЭВМ и разработка методов сортировки тесно переплелась с их развитием. На самом деле имеются свидетельства того, что программа сортировки была первой из когда-либо написанных для вычислительных машин с запоминаемой программой. Конструкторы вычислительной машины Е1ЗЧАС особенно интересовалнсь сортировкой, поскольку она выступала как наиболее характерный представитель потенциальных нечисловых приложений ЭВМ.
Они понимали, что удовлетворительная система команд должна годиться не только для составления программы решения разностиых уравнений; она должна обладать достаточной гибкостью, чтобы справиться с комбннаторными аспектами в алгоритмах "выбора решений". Поэтому Джон фон Нейман (1оЬп гоп Хепшапп) подготовил и 1945 году программы для внутренней сортировки методом слияния, чтобы убедиться в необходимости некоторых типов команд, предложенных им для машины ЕОУАС.
Существование эффективных специализированных сортировальных машин послужило тем естественным стандартом, в сопоставлении с которым можно было оценить достоинства предлагаемой организации электронной вычислительной машины. Подробно зто интересное исследование описано в статье П. Е. КгшсЬ, Союз!шй Яиггеуз 2 (1970), 247 — 260; первая программа сортировки фон Неймана в окончательном, "отполированном' виде приводится в его сборнике Со!!есге! Ягогкз 5 (Хея Уог!с: Масон!1ап, 1963), 196-214.
Независимо от них в 1945 году К. Пузе (К. Ецзе) в Германии разработал программу для сортировки методом простой вставки. Это был один из самых простых примеров операций с линейными списками в разработанном им языке "Р!апйа!!гцГ: (Эта пионерская работа ожидала публикации почти 30 лет; см.
Вез4сЬ!е дег Севе!1- зсЬаус В1г Магйешабй пЫ Пагепгегагбей ип8 63 (Вопп, 1972), рагс 4, 84-85.) Из-за ограниченного объема памяти в ранних машинах приходилось думать о внешней сортировке наравне с внутренней, и в докладе "Ргойгеяз Верог! оп гЬе ЕРУАС", подготовленном Дж. П.
Эккертом (3. Р. Есйегг) н Дж. У. Мочлн (3. %. МацсЫу) для Школы Мура по электротехнике !Моете 8сЬоо! о( Е!есгбса! Епй!пеег!п8 (30 БергешЬег, 1945)!, укязывачось, что ЭВМ, оснащенная устройством с магнитной проволокой или лентой, могла бы моделировать действия перфокарточного оборудования, достигая при этом большей скорости сортировки. В этом докладе были описаны методы сбалансированной двухпутевой поразрядной сортировки и сбалансированного двухпутевого слияния (там он был назван "подборкой"' (со11асшя)) с использованием четырех устройств внешней памяти на магнитной проволоке илн ленте, читающих или записывающих "не менее 5 000 импульсов в секунду".
Джон Мочли выступил с лекцией о "сортировке и слиянии" на специальной сессии по вычислениям, созывавшейся в Школе Мура в 1946 году. В конспекте его лекции содержится первое опубликованное обсуждение сортировки с помощью вычислительных машин [Тйеогу атЫ 2Ьсйпи1иев Уог йе Пез76п оу Б)ессгошс Ийтса) Сошрпсегв, ео11ео Ьу 6. %. Ра11егзоп, 3 (1946), 22.1 — 22.20]. Мочли начал свое выступление с интересного замечания: "Требование, чтобы одна.
машина объединяла возможности вычислений и сортировки, кое-кому может показаться требованием, чтобы один прибор использовался как ключ для консервов и как авторучка". Затеи он заметил, что машины, способные выполнять сложные математические процедуры, должны также иметь возможность сортировать н классифицировать данные; он показал, что сортировка может быть полезна даже в связи с численными расчетами.
Мочли описал методы простой вставки и бинарных вставок, упомянув, что в первом методе в среднем необходимо около М /4 сравнений, в то время как в последнем их никогда, не требуется более У!5Х. Однако для бинарных вставок нужна весьма сложная структура данных и Мочли затем показал, что при двухпутевом слиянии достигается столь же малое число сравнений., но используется только последовательный просмотр списков. Последняя часть конспекта его лекции посвящена методам поразрядной сортировки с частичными проходами, которые моделируют цифровую карточную сортировку на четырех лентах, затрачивая менее четырех проходов на цифру (см. раздел 5.4.7). Вскоре после этого Эккерт и Мочли организовали компанию, выпустившую некоторые пз самых ранних электронных вычислительных машин В1ХАС (для военных приложений) и СХ1ЧАС (для коммерческих приложений).
Вновь Бюро переписи США сыграло в этом свою роль, приобретя первый 1УМ1ЪАС. В зто время далеко ие всем было ясно, что ЭВМ станут экономически выгодными: вычислительные машины могли сортировать быстрее. но они и стоили дороже. Поэтому программисты ВХ1УАС под руководством Фрэнсис Э. Гольбертон (Ргацсев Е. Но1Ьегтоп) приложили значительные усилия к созданию программ внешней сортировки, работающих с высокой скоросгью: их первые программы повлияли также на разработку оборудования. По их оценкам 100 млн записей по 10 слов могли быть рассортированы на УХ1УАС за 9 000 ч (т.
е. за 375 дней), Вычислительная машина 01ч1ЧАС 1, официально запущеяная в эксплуатацию в июле 19о1 года, имела оперативную память объемом 1 000 12-буквенных (72-битовых) слов. В ией предусматривались чтение и запись на ленту блоков по 60 слов со скоростью 500 слов в секунду; чтение могло быть прямым или обратным, допускалось совмещение операций чтения, записи и вычислений.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
