В период 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.
