Ликбез по работе с перфокартами (или история о том, как с 1890-го по 1970-й «большие данные» обрабатывались)

В период 1890–1970 вся обработка больших данных осуществлялась через перфокарты. Перфокарты в свою очередь обрабатывались при помощи т.н. «регистрирующей аппаратурой», центральным звеном которой был электромеханический «сортировщик перфокарт». Перфокарты и сопутствующую аппаратуру применяли для решения самых разнообразных задач: перепись населения, бухгалтерский учёт, инвентаризация, расчёт заработной платы и т.д.

Как люди работали с перфокартами? Какому алгоритму следовал электромеханический сортировщик перфокарт? Как осуществлялась сортировка по числовым полям данных? А по строковым? Обо всём этом — ниже.

uh4ruj0obuhqf5ta1pozis3uwyy.jpeg


  • Поразительная черта регистрирующей аппаратуры докомпьютерных времён: она изначально была полностью электромеханической. В ней даже ламповой электроники ещё не было. «Интеллект» регистрирующей аппаратуры строился из проволочных щёток (для распознавания отверстий в перфокартах), электромеханического реле и механических колёсиков (для суммирования значений). Несмотря на свою технологическую примитивность, «регистрирующая аппаратура» в своё время произвела революцию в обработке больших данных.

Как люди работали с перфокартами?


  • Каждая перфокарта хранила по одной записи данных (до 80 цифр или символов). Каждая запись данных состояла из нескольких полей. Сортировщик перфокарт располагал карты в нужном оператору порядке (по одному из полей данных), после чего машинка, называемая «табулятором», считывала отсортированные перфокарты, извлекала из них нужные поля (опять же, заданные оператором), и печатала отчёт.
  • Для примера рассмотрим как перфокарты использовались при обработке счёт-фактур. У компаний для каждой счёт-фактуры, выставленной к оплате, была предусмотрена отдельная перфокарта (см. пример на рисунке ниже). На перфокарте указывались такие поля данных как номер поставщика, дата платежа, сумма платежа и т.п.
    thhi2vomvnd_ncji42rpkksroqq.png
  • Соответствующий автоматизированный бизнес-процесс по обработке данных заключается в следующем. Сортировщику перфокарт отдаётся команда упорядочить перфокарты по номеру поставщика. После того как сортировка завершена, перфокарты передаются табулятору, который генерирует отчёт, считывая нужную строчку с каждой перфокарты. Механический счётчик, встроенный в табулятор, автоматически подбивает общую сумму.
  • Многие другие бизнес-процессы, такие как начисление заработной платы, инвентаризация и выписка счетов, — осуществлялись в докомпьютерные времена аналогичным образом.

Принцип действия электромеханического сортировщика перфокарт


  • Сортировщик принимает пачку перфокарт и сортирует их по заданному оператором полю данных. Например, по принадлежности сотрудников к определённому департаменту. Зачем? Как вариант, чтобы, предварительно сгруппировав сотрудников по департаментам, затем сформировать отчёт по выполнению плана продаж каждым из департаментов компании.
  • Для решения этой задачи перфокарты сначала сортируются на основе поля «департамент», а затем передаются табулятору, который суммирует поле «продажи», печатая в отчёте промежуточные результаты по каждому департаменту.
  • Пачку перфокарт, нуждающуюся в сортировке, оператор помещает в специальный лоток, из которого они по одной прогоняются через сортировщик. Сортировщик считывает перфокарты и распределяет их по 13 карманам: десять цифирных, два «зональных» (для обработки строковых значений); и один для отброшенных перфокарт (на которых не задано значение, по которому осуществлялась сортировка).
    ngjlvocjc3mmbgjlqfad8gw5mnu.png
  • Алгоритм, по которому работает сортировщик перфокарт, очень сильно отличается от общепринятых на сегодняшний день алгоритмов. Ключевое отличие в том, что перфокарты не сравниваются друг с дружкой.

Алгоритм поразрядной сортировки чисел

Как же тогда сортировщику перфокарт удаётся справляться со своей работой? В нём реализован изящный алгоритм «поразрядной сортировки». Суть: сортировщик перфокарт обрабатывает по одной цифре поля данных за раз; для сортировки по трёхзначному полю, пачку перфокарт нужно пропустить через сортировщик три раза. Итак, алгоритм:


  1. Упорядочивая перфокарты по заданному оператором числовому полю данных, сортировщик при первом прогоне обрабатывает только младший разряд этого поля. И в соответствии со значением этого разряда принимает решение, куда скинуть текущую перфокарту: в какой из 10 цифирных карманов (с нулевого по девятый).
  2. После того как сортировщик закончил распределение перфокарт по карманам, оператор вынимает их, и складывает в общую пачку. По порядку: начиная с нулевого кармана и заканчивая девятым.
  3. Собранную пачку перфокарт оператор снова помещает в сортировщик, и повторяет шаги 1 и 2 последовательно для каждого разряда.
  4. Всё, теперь перфокарты отсортированы.

Преимущества алгоритма поразрядной сортировки


  • Алгоритм поразрядной сортировки изящен и быстр. Его вычислительная сложность составляет O (n log n). Иначе говоря, при увеличении количества карт, длительность работы алгоритма увеличивается линейно, а не экспоненциально.
  • Алгоритм поразрядной сортировки технически может быть реализован в виде простой электромеханической конструкции.
  • Несмотря на то, что во входном лотке сортировщика перфокарт помещается не больше 3600 карт, он может сортировать и гораздо большее количество перфокарт, если оператор будет своевременно выполнять следующие два действия: (1) своевременно загружать в лоток новые пачки перфокарт; (2) своевременно опустошать цифирные карманы (чтобы они не переполнились).

Как осуществляется кодировка строковых данных


  • Как уже было отмечено выше, числовые значения кодируются на перфокарте отверстиями. По одному отверстию в столбце. С их сортировкой мы уже разобрались. Теперь осталось понять, как на перфокарте кодируются строки и как сортировщик перфокарт упорядочивает их.
  • Для работы со строками в сортировщике перфокарт предусмотрены два «зональных» кармана (11-й и 12-й), в дополнение к 10 цифирным. Принцип кодировки буквенных символов следующий (см. рисунок ниже). Каждая буква кодируется двумя отверстиями на перфокарте: дырка на цифре (от 1 до 9) и дырка на «зоне» (0, 11 или 12).
    w5f5acn19nlcg-tqbwzak5-riqi.png
  • Обратите внимание: строка с нулями при обработке числовых полей данных является цифирной, а при обработке строковых полей данных — «зональной».

Алгоритм сортировки символьных строк

Благодаря такой кодировке сортировщик может упорядочивать строковые поля данных по алфавиту. На это ему требуется два прогона. Алгоритм следующий:


  1. На первом прогоне сортировщик перфокарт упорядочивает карты почти также как и при сортировке числовых полей данных. Отличие в том, что при алфавитной сортировке задействуются только девять карманов: с 1-го по 9-й.
  2. По завершении сортировки оператор вынимает перфокарты из цифирных карманов. Опять же, по порядку (как и в случае с упорядочиванием по числовому полю данных): начиная с первого кармана и заканчивая девятым. Собранную пачку карт оператор отправляет на сортировку второй раз.
  3. На втором прогоне сортировщик перфокарт считывает только строки «зон» (0, 11 и 12), а строки с цифрами — игнорирует.
  4. В результате упорядоченные перфокарты распределяются сортировщиком по трём «зональным» карманам: от A до I помещаются в 12-й карман; от J до R — в 11-й; от S до Z — в 0-й.
  5. Если сортировку нужно выполнить не по одному первому символу, а например по двум или трём первым, то описанный выше процесс (шаги с первого по четвёртый) выполняется последовательно для каждого символа. Т.е. для каждого символа делается по два прогона через сортировщик перфокарт.

tpemu_3ytyvxwvup69g5jhnkoaw.jpeg

Итак, когда компьютеров ещё не было, предприятия обрабатывали большие данные при помощи перфокарт. Несмотря на то, что перфокарты безвозвратно устарели, с их влиянием на современное состояние компьютерной техники мы сталкиваемся и по сей день, — всякий раз, когда нам приходится мириться с ограничением длины строки в 80 символов (например, при работе с Far Manager).

© Habrahabr.ru