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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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


Оставить комментарий

Ваш email нигде не будет показан
Обязательные для заполнения поля помечены *

*

x

Ещё Hi-Tech Интересное!

[Перевод] Введение в ptrace или инъекция кода в sshd ради веселья

Конечно, это несколько искусственная задача, так как есть множество других, более эффективных, способов достичь желаемого (и с гораздо меньшей вероятностью получить SEGV), однако, мне показалось клёвым сделать именно так. Цель, которой я задался, была весьма проста: узнать введённый в sshd ...

Дайджест свежих материалов из мира фронтенда за последнюю неделю №339 (12 — 18 ноября 2018)

Предлагаем вашему вниманию подборку с ссылками на новые материалы из области фронтенда и около него.     Медиа    |    Веб-разработка    |    CSS    |    Javascript    |    Браузеры    |    Занимательное Медиа • Подкаст «Frontend Weekend» #79 – Олег Поляков об основании CodeDojo и о том, как это стало основным местом работы• Подкаст «Пятиминутка React» ...