В период 1890-1970 вся обработка больших данных осуществлялась через перфокарты. Перфокарты в свою очередь обрабатывались при помощи т.н. «регистрирующей аппаратурой», центральным звеном которой был электромеханический «сортировщик перфокарт». Перфокарты и сопутствующую аппаратуру применяли для решения самых разнообразных задач: перепись населения, бухгалтерский учёт, инвентаризация, расчёт заработной платы и т.д.
Как люди работали с перфокартами? Какому алгоритму следовал электромеханический сортировщик перфокарт? Как осуществлялась сортировка по числовым полям данных? А по строковым? Обо всём этом – ниже.
- Поразительная черта регистрирующей аппаратуры докомпьютерных времён: она изначально была полностью электромеханической. В ней даже ламповой электроники ещё не было. «Интеллект» регистрирующей аппаратуры строился из проволочных щёток (для распознавания отверстий в перфокартах), электромеханического реле и механических колёсиков (для суммирования значений). Несмотря на свою технологическую примитивность, «регистрирующая аппаратура» в своё время произвела революцию в обработке больших данных.
Как люди работали с перфокартами?
- Каждая перфокарта хранила по одной записи данных (до 80 цифр или символов). Каждая запись данных состояла из нескольких полей. Сортировщик перфокарт располагал карты в нужном оператору порядке (по одному из полей данных), после чего машинка, называемая «табулятором», считывала отсортированные перфокарты, извлекала из них нужные поля (опять же, заданные оператором), и печатала отчёт.
- Для примера рассмотрим как перфокарты использовались при обработке счёт-фактур. У компаний для каждой счёт-фактуры, выставленной к оплате, была предусмотрена отдельная перфокарта (см. пример на рисунке ниже). На перфокарте указывались такие поля данных как номер поставщика, дата платежа, сумма платежа и т.п.
- Соответствующий автоматизированный бизнес-процесс по обработке данных заключается в следующем. Сортировщику перфокарт отдаётся команда упорядочить перфокарты по номеру поставщика. После того как сортировка завершена, перфокарты передаются табулятору, который генерирует отчёт, считывая нужную строчку с каждой перфокарты. Механический счётчик, встроенный в табулятор, автоматически подбивает общую сумму.
- Многие другие бизнес-процессы, такие как начисление заработной платы, инвентаризация и выписка счетов, – осуществлялись в докомпьютерные времена аналогичным образом.
Принцип действия электромеханического сортировщика перфокарт
- Сортировщик принимает пачку перфокарт и сортирует их по заданному оператором полю данных. Например, по принадлежности сотрудников к определённому департаменту. Зачем? Как вариант, чтобы, предварительно сгруппировав сотрудников по департаментам, затем сформировать отчёт по выполнению плана продаж каждым из департаментов компании.
- Для решения этой задачи перфокарты сначала сортируются на основе поля «департамент», а затем передаются табулятору, который суммирует поле «продажи», печатая в отчёте промежуточные результаты по каждому департаменту.
- Пачку перфокарт, нуждающуюся в сортировке, оператор помещает в специальный лоток, из которого они по одной прогоняются через сортировщик. Сортировщик считывает перфокарты и распределяет их по 13 карманам: десять цифирных, два «зональных» (для обработки строковых значений); и один для отброшенных перфокарт (на которых не задано значение, по которому осуществлялась сортировка).
- Алгоритм, по которому работает сортировщик перфокарт, очень сильно отличается от общепринятых на сегодняшний день алгоритмов. Ключевое отличие в том, что перфокарты не сравниваются друг с дружкой.
Алгоритм поразрядной сортировки чисел
Как же тогда сортировщику перфокарт удаётся справляться со своей работой? В нём реализован изящный алгоритм «поразрядной сортировки». Суть: сортировщик перфокарт обрабатывает по одной цифре поля данных за раз; для сортировки по трёхзначному полю, пачку перфокарт нужно пропустить через сортировщик три раза. Итак, алгоритм:
- Упорядочивая перфокарты по заданному оператором числовому полю данных, сортировщик при первом прогоне обрабатывает только младший разряд этого поля. И в соответствии со значением этого разряда принимает решение, куда скинуть текущую перфокарту: в какой из 10 цифирных карманов (с нулевого по девятый).
- После того как сортировщик закончил распределение перфокарт по карманам, оператор вынимает их, и складывает в общую пачку. По порядку: начиная с нулевого кармана и заканчивая девятым.
- Собранную пачку перфокарт оператор снова помещает в сортировщик, и повторяет шаги 1 и 2 последовательно для каждого разряда.
- Всё, теперь перфокарты отсортированы.
Преимущества алгоритма поразрядной сортировки
- Алгоритм поразрядной сортировки изящен и быстр. Его вычислительная сложность составляет O(n log n). Иначе говоря, при увеличении количества карт, длительность работы алгоритма увеличивается линейно, а не экспоненциально.
- Алгоритм поразрядной сортировки технически может быть реализован в виде простой электромеханической конструкции.
- Несмотря на то, что во входном лотке сортировщика перфокарт помещается не больше 3600 карт, он может сортировать и гораздо большее количество перфокарт, если оператор будет своевременно выполнять следующие два действия: (1) своевременно загружать в лоток новые пачки перфокарт; (2) своевременно опустошать цифирные карманы (чтобы они не переполнились).
Как осуществляется кодировка строковых данных
- Как уже было отмечено выше, числовые значения кодируются на перфокарте отверстиями. По одному отверстию в столбце. С их сортировкой мы уже разобрались. Теперь осталось понять, как на перфокарте кодируются строки и как сортировщик перфокарт упорядочивает их.
- Для работы со строками в сортировщике перфокарт предусмотрены два «зональных» кармана (11-й и 12-й), в дополнение к 10 цифирным. Принцип кодировки буквенных символов следующий (см. рисунок ниже). Каждая буква кодируется двумя отверстиями на перфокарте: дырка на цифре (от 1 до 9) и дырка на «зоне» (0, 11 или 12).
- Обратите внимание: строка с нулями при обработке числовых полей данных является цифирной, а при обработке строковых полей данных – «зональной».
Алгоритм сортировки символьных строк
Благодаря такой кодировке сортировщик может упорядочивать строковые поля данных по алфавиту. На это ему требуется два прогона. Алгоритм следующий:
- На первом прогоне сортировщик перфокарт упорядочивает карты почти также как и при сортировке числовых полей данных. Отличие в том, что при алфавитной сортировке задействуются только девять карманов: с 1-го по 9-й.
- По завершении сортировки оператор вынимает перфокарты из цифирных карманов. Опять же, по порядку (как и в случае с упорядочиванием по числовому полю данных): начиная с первого кармана и заканчивая девятым. Собранную пачку карт оператор отправляет на сортировку второй раз.
- На втором прогоне сортировщик перфокарт считывает только строки «зон» (0, 11 и 12), а строки с цифрами – игнорирует.
- В результате упорядоченные перфокарты распределяются сортировщиком по трём «зональным» карманам: от A до I помещаются в 12-й карман; от J до R – в 11-й; от S до Z – в 0-й.
- Если сортировку нужно выполнить не по одному первому символу, а например по двум или трём первым, то описанный выше процесс (шаги с первого по четвёртый) выполняется последовательно для каждого символа. Т.е. для каждого символа делается по два прогона через сортировщик перфокарт.
Итак, когда компьютеров ещё не было, предприятия обрабатывали большие данные при помощи перфокарт. Несмотря на то, что перфокарты безвозвратно устарели, с их влиянием на современное состояние компьютерной техники мы сталкиваемся и по сей день, – всякий раз, когда нам приходится мириться с форматированием текста 80-символьными строками. Нечто подобное наблюдается, например, при работе с Far Manager.
Комментарии (27)
pavlushk0
15.10.2018 22:28+3Может, конечно, совсем тупой вопрос, но разве О(n logn) — это линия?
Lertmind
16.10.2018 01:32Если кто не понял: ошибка в нотации, поразрядная сортировка выполняется за O(nw), где n — количество ключей (карт), w — средняя длина ключа (цифр в поле). В данном случае количество цифр в поле постоянное, значит можно записать O(n).
InvisibleLight
15.10.2018 23:10+1PL/1 на перфокартах, было время ) Куча терминалов для студентов и один ВЦ в подвале. «Перфоратор» тоже один. Очередь. Одна строка программы — одна перфокарта. Заменить одну строку (одну перфокарту) не составляло труда. Иногда не считывались некоторые из перфокарт. Заново суешь их в «считыватель» и вуаля! Прошли времена!
saipr
15.10.2018 23:26+2Отдельная история была с проверкой правильности пробивки перфокарт. А какое искусство требовалось при исправлении ошибки на перфокарте (без замены перфокарты): вход шли бритвы для прорезания нужной позиции, а отходы от пробивки перфорты порой шли на закрытие ошибочно пробитой позиции. О, это была магия!!!!
Iwanowsky
16.10.2018 03:55+1У меня была раритетная вещица — дырокол для 45-колонных перфокарт (для исправления ошибок, массивная железяка размером примерно с перфокарту, которая фиксировалась поперек устройства и пробивалась через ряд дырочкек специальным стилом), но потерялся к сожалению при переезде. Но есть еще 2 разных дырокола для перфолент.
Iwanowsky
16.10.2018 03:12+1С перфокартами в свое время поработал очень много. Помню, как когда-то (в середине 1980-х) нашу школу по информатике прикрепили к НИИ Геофизики, и мы писали программы на Фортране и сами потом набивали перфокарты на перфораторах, а после вводили пачки перфокарт на ЕС-1022. Хорошие были времена! А потом во время учебы в вузе работали на ЕС 1033 и ЕС 1045 (вуз имел свои компьютеры) — сначала на перфокартах, а потом появились и дисплейные классы на Видеотонах. В то время мы сдавали тексты программ (написанные от руки на бумаге в клетку, в т.ч. задание на языке JCL) в службу прогона программ, и там операторы набивали на перфокарты и прогоняли ночью, а с утра мы приходили с выданным номерком за распечаткой работы программы или листингом с ошибками. Помню, как операторши частенько допускали ошибки, и приходилось отдавать на перепечатку отдельных перфокарт. Нули нужно было обязательно перечеркивать, иначе оператор (часто сам далекий от понимания компьютеров) вбивал букву «О» (и до сих пор устойчивая привычка — нули в рукописном тексте перечеркивать); а единички д.б. с хвостиком, иначе могли стать буквой «I»; и т.д. Сам я тоже тогда, бывало, оставался на ночные дежурства в машинном зале (ночные прогоны), в т.ч. подменяя заболевших операторов. Потом появились один за др. 2 класса с терминалами Видеотон. Также появились и СМ ЭВМ (СМ-3/4) и др. большие и не очень большие компьютеры. А потом вдруг резко начали появляться персональные компьютеры — сначала иностранные, а потом ЕС-1040/1041; и я уже переключился на них. И описанная смена поколений компьютеров произошла за 5 лет учебы в вузе, по окончанию кот. я остался в нем работать и работаю до сих пор. Интересна также еще эволюция персональных компьютеров и ноутбуков у меня дома, а также эволюция операционных систем на них, но это уже др. тема.
saag
16.10.2018 07:08+1Я тоже с перфокартами столкнулся впервые в 1985, это было на телефонно-телеграфной станции, там биллинг был на перфокартах — междугородные разговоры так тарифицировались, и сортировщик видел в действии, это тогда выглядело как магия:-) И с ЕС1022 тож пришлось столкнуться, правда в 1988, тоже ввод осуществлял с них, а до них на барроуз-7000 с перфолент:-) Тихой работу на них не назовешь…
Iwanowsky
16.10.2018 10:25У меня даже осталась коллекция перфокарт: 80- и 45-колонные (45 — с круглыми дырочками), разных производителей (в т.ч. зарубежных), разных цветов и размеров, с прямыми и скругленными углами, есть также одна для ткацкого станка. Есть также колода чистых перфокарт — удобно использовать для заметок. Также есть магнитные карты (были и такие, размером со стандартную перфокарту).
jzha
16.10.2018 10:40Перфокарты устарели в компьютерной технике. Но по-прежнему используются в бытовых программируемых вязальных машинах. Можно сказать, процесс не изменился еще с 18 века. Перфоратором задается 'программа' на перфокарте. Следуя инструкциям 'программы', машина выполняет вязку изделия.
balexa
16.10.2018 11:24А почему так? Мне кажется в наше время уже дешевле вставить туда полноценный компьютер с выходом в интернет.
iig
16.10.2018 11:45+1Отработанная веками конструкция, почему не использовать, если сам процесс вязания остался тот же, что и 200 лет назад?
jzha
16.10.2018 15:02Думаю, это будет дороже. Помимо самого компьютера, потребуются, наверное, дополнительные элементы управления иглами машины и специализированное ПО для взаимодействия с машиной. А этот рынок, как понимаете, не массовый и, вполне возможно, инертный. Да и 'язык программирования' на перфокартах для вязальных машин вполне себе занимательный.
Современные профессиональные вязальные машины, наверняка, все компьютеризированы. Но это уже другая ниша.
Exchan-ge
17.10.2018 00:24+1А почему так? Мне кажется в наше время уже дешевле вставить туда полноценный компьютер с выходом в интернет.
В каком-то старом каталоге типа Neckermann или Otto, лет 20 назад — была вязальная машинка с подключением к ПК. Это был самый дорогой вариант вязальной машины.
Не взлетело, очевидно по той причине, что вязальщицам проще было использовать перфокарты, чем ПК (ну и цена, естественно сыграла своию роль)
roofcat
16.10.2018 11:15В середине 90х нашел ошибку в американской модели радиационных поясов Земли AP8 (начала 60х), оказалось, часть строк (перфокарт) в массиве данных в фортрановской программе были переставлены в другое место массива. Никакого контроля корректности массива в программе не было, поэтому моделью не пользовались, разработав взамен новую, упрощенную. Переставил строки на место и все заработало. Помню даже коротенький препринт написал :)
sshikov
>всякий раз, когда нам приходится мириться с ограничением длины строки в 80 символов (например, при работе с Far Manager).
Интересно, когда вы последний раз работали в FAR?
begemot_sun
Когда сидел в виндусе, регулярно работал в FAR (во время девелопмента). Сейчас у меня Убунта\Дебиан, и я работаю в MC также. Это я один такой мастодонт (35 лет)?
P.S. Никогда не видел в FAR проблемы 80 символов. А вот в Dos Navigator было по моему такое :) но то были другие времена.
sshikov
Не знаю, не знаю… мастодонты должны бы знать, что в FAR давно уже нет никакого так называемого ограничения в 80 символов. Открываете настройки консоли, ставите любую ширину и высоту окна, выбираете юникод шрифт — и вуаля. По-моему его и не было никогда — в windows версии это всегда было можно. У меня стоит 160*40 например. Или вы про что?
:)
Кстати, размер так «называемых больших данных» в моей практике был ограничен размером колоды карт, которую перфоратор М-222 умел пробить без ошибок. И это примерно 200 карт всего-навсего. Я как-то целую субботу угрохал в попытках вывести (и потом считать) объектный модуль после компилятора Алгол-60.
Iwanowsky
А если в FAR добавить плагин Console Control, то размер окна можно изменять мышкой или клавиатурными командами.
Nick_Shl
Alt + F9 разворачивает Far на полный экран устанавливая ширину и высоту окна консоли по максимуму.
CrashLogger
80 символов — это ширина экрана в текстовом режиме DOS. Соответственно в досовских редакторах обычно текст выравнивался чтобы не пересекать эту границу, иначе неудобно читать — нужно скроллить по горизонтали.
VolKarev Автор
Кстати да, «выравнивание» в данном случае более подходящее слово, чем «ограничение». Спасибо за идею. Хотя… Даже ещё более подходящий вариант: форматирование. Так что на него поправил.
Iwanowsky
FAR — лучший клон Нортон Коммандер для Виндовс, и для него есть огромное количество плагинов на практически любые области применения. И ДОС Навигатор в свое время был революционным НортонКоммандер-подобным для ДОС. МС — стандарт для Юникс/Линукс.