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