В период 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), а строки с цифрами игнорирует.
- В результате заказанные перфокарты сортировщиком распределяются по трем «зональным» карманам: от А до I помещаются в 12-й карман; от J до R – в 11-м; от S до Z – в 0-м.
- Если вам нужно выполнить сортировку не только по первому символу, а, например, по первым двум или трем, то описанный выше процесс (шаги с первого по четвертый) выполняется последовательно для каждого символа.
Те.
Для каждого символа производится два прохода через сортировщик перфокарт.
Итак, когда не было компьютеров, предприятия обрабатывали большие данные с помощью перфокарт. Несмотря на то, что перфокарты безвозвратно устарели, мы до сих пор сталкиваемся с их влиянием на современное состояние компьютерных технологий — всякий раз, когда нам приходится мириться с форматированием текста в 80-символьные строки.
Нечто подобное наблюдается, например, при работе с Far Manager. Теги: #математика #История ИТ #Устройства хранения данных #Большие данные #Старое оборудование #сортировка #антиквариат #перфокарты
-
Производство Для Всех
19 Oct, 24 -
Билет В Мир Usb 3.0 Недорого
19 Oct, 24 -
Как Npm Обеспечивает Безопасность
19 Oct, 24 -
Коди — Робот, Который Учит Программированию.
19 Oct, 24 -
Google Требует Более Эффективных Серверов
19 Oct, 24 -
Yahoo Не Будет Снимать Цензуру В Китае
19 Oct, 24
