In der Zeit von 1890 bis 1970 wurde die gesamte Big-Data-Verarbeitung über Lochkarten durchgeführt. Lochkarten wurden wiederum mit den sogenannten verarbeitet "Aufnahmegerät", dessen zentrales Glied der elektromechanische "Lochkartensortierer" war. Lochkarten und zugehörige Ausrüstung wurden verwendet, um eine Vielzahl von Aufgaben zu lösen: Volkszählung, Buchhaltung, Inventar, Gehaltsabrechnung usw.
Wie haben die Leute mit Lochkarten gearbeitet? Welchem Algorithmus folgte der elektromechanische Lochkartensortierer? Wie wurde nach numerischen Datenfeldern sortiert? Und an der Schnur? Über all das - unten.
- Ein auffälliges Merkmal des Aufzeichnungsgeräts aus der Zeit vor dem Computer: Es war ursprünglich vollständig elektromechanisch. Es war noch nicht einmal Lampenelektronik darin. Die "Intelligenz" des Aufzeichnungsgeräts wurde aus Drahtbürsten (zum Erkennen von Löchern in Lochkarten), einem elektromechanischen Relais und mechanischen Rädern (um die Werte zusammenzufassen) aufgebaut. Trotz seiner technologischen Primitivität revolutionierte das „Aufzeichnungsgerät“ einst die Verarbeitung von Big Data.
Wie haben die Leute mit Lochkarten gearbeitet?
- Jede Lochkarte speicherte einen Datensatz (bis zu 80 Ziffern oder Zeichen). Jeder Datensatz bestand aus mehreren Feldern. Der Lochkartensortierer ordnete die Karten in der für den Bediener erforderlichen Reihenfolge (gemäß einem der Datenfelder) an. Anschließend las die Maschine, die als „Tabulator“ bezeichnet wurde, die sortierten Lochkarten, extrahierte die erforderlichen Felder daraus (erneut vom Bediener angegeben) und druckte den Bericht aus.
- Betrachten Sie als Beispiel, wie Lochkarten zur Verarbeitung von Rechnungen verwendet wurden. Unternehmen hatten für jede zur Zahlung ausgestellte Rechnung eine separate Lochkarte (siehe Beispiel in der Abbildung unten). Datenfelder wie die Nummer des Lieferanten, das Zahlungsdatum, der Zahlungsbetrag usw. wurden auf der Lochkarte angegeben.
- Der entsprechende Geschäftsprozess für die automatisierte Datenverarbeitung lautet wie folgt. Der Lochkartensortierer wird angewiesen, die Lochkarten nach Lieferantennummer zu sortieren. Nach Abschluss der Sortierung werden Lochkarten an den Tabulator übergeben, der einen Bericht erstellt, indem die gewünschte Zeile von jeder Lochkarte gelesen wird. Ein im Tabulator eingebauter mechanischer Zähler schlägt den Gesamtbetrag automatisch aus.
- Viele andere Geschäftsprozesse wie Gehaltsabrechnung, Inventarisierung und Abrechnung wurden auf ähnliche Weise in Zeiten vor dem Computer ausgeführt.
Das Funktionsprinzip des elektromechanischen Lochkartensortierers
- Der Sortierer nimmt einen Stapel Lochkarten und sortiert sie nach dem vom Bediener angegebenen Datenfeld. Zum Beispiel durch die Zugehörigkeit von Mitarbeitern zu einer bestimmten Abteilung. Warum? Optional können Sie nach vorheriger Gruppierung der Mitarbeiter nach Abteilungen einen Bericht über die Umsetzung des Verkaufsplans durch die einzelnen Abteilungen des Unternehmens erstellen.
- Um dieses Problem zu lösen, werden Lochkarten zuerst nach dem Feld "Abteilung" sortiert und dann in den Tabulator übertragen, der das Feld "Verkauf" zusammenfasst und die Zwischenergebnisse für jede Abteilung im Bericht druckt.
- Der Bediener legt das Lochkartenpaket, das sortiert werden muss, in ein spezielles Fach, aus dem sie einzeln durch den Sortierer gefahren werden. Der Sortierer liest die Lochkarten und verteilt sie in 13 Taschen: zehn digitale, zwei Zonenkarten (zur Verarbeitung von Zeichenfolgenwerten); und eine für weggeworfene Lochkarten (die keinen Wert angeben, nach dem sortiert wurde).
- Der vom Lochkartensortierer verwendete Algorithmus unterscheidet sich stark von den heute allgemein akzeptierten Algorithmen. Der Hauptunterschied besteht darin, dass Lochkarten nicht miteinander verglichen werden.
Bitweiser Sortieralgorithmus
Wie schafft es dann ein Lochkartensortierer, seine Arbeit zu erledigen? Es implementiert einen eleganten "bitweisen Sortier" -Algorithmus. Fazit: Der Lochkartensortierer verarbeitet jeweils eine Ziffer des Datenfelds. Um nach einem dreistelligen Feld zu sortieren, muss ein Satz Lochkarten dreimal durch den Sortierer geführt werden. Also der Algorithmus:
- Beim Sortieren von Lochkarten nach einem vom Bediener angegebenen numerischen Datenfeld verarbeitet der Sortierer während des ersten Durchlaufs nur das niedrigstwertige Bit dieses Felds. Und entsprechend dem Wert dieser Kategorie entscheidet er, wo die aktuelle Lochkarte abgelegt werden soll: welche der 10 digitalen Taschen (von null bis neun).
- Nachdem der Sortierer die Lochkarten in den Taschen verteilt hat, nimmt der Bediener sie heraus und legt sie in ein gemeinsames Bündel. In der Reihenfolge: Ausgehend von der Nulltasche und endend mit der neunten.
- Der Bediener legt das zusammengesetzte Lochkartenpaket in den Sortierer und wiederholt die Schritte 1 und 2 nacheinander für jede Kategorie.
- Alles, jetzt werden Lochkarten sortiert.
Vorteile des bitweisen Sortieralgorithmus
- Der bitweise Sortieralgorithmus ist elegant und schnell. Seine Rechenkomplexität ist O (n log n). Mit anderen Worten, mit zunehmender Anzahl von Karten nimmt die Dauer des Algorithmus linear und nicht exponentiell zu.
- Der bitweise Sortieralgorithmus kann technisch als einfaches elektromechanisches Design implementiert werden.
- Trotz der Tatsache, dass nicht mehr als 3600 Karten in das Zufuhrfach eines Lochkartensortierers gelegt werden, kann eine viel größere Anzahl von Lochkarten sortiert werden, wenn der Bediener die folgenden zwei Aktionen rechtzeitig ausführt: (1) rechtzeitiges Laden neuer Lochkartenpakete in ein Fach; (2) Leeren Sie die digitalen Taschen rechtzeitig (damit sie nicht überlaufen).
Wie String-Daten codiert werden
- Wie oben erwähnt, sind numerische Werte auf der Lochkarte mit Löchern codiert. Ein Loch in der Säule. Wir haben ihre Sortierung bereits aussortiert. Nun bleibt zu verstehen, wie Zeichenfolgen auf der Lochkarte codiert sind und wie der Lochkartensortierer sie organisiert.
- Um mit Strings im Lochkartensortierer zu arbeiten, gibt es zwei "zonale" Taschen (11. und 12.) sowie 10 digitale. Das Prinzip der Codierung alphabetischer Zeichen lautet wie folgt (siehe Abbildung unten). Jeder Buchstabe ist mit zwei Löchern auf der Lochkarte codiert: einem Loch in der Zahl (von 1 bis 9) und einem Loch in der "Zone" (0, 11 oder 12).
- Bitte beachten Sie: Eine Zeichenfolge mit Nullen wird bei der Verarbeitung numerischer Datenfelder digitalisiert und bei der Verarbeitung von Zeichenfolgendatenfeldern „zonal“.
Algorithmus zum Sortieren von Zeichenketten
Dank dieser Codierung kann der Sortierer die Zeichenfolgendatenfelder alphabetisch sortieren. Dazu benötigt er zwei Läufe. Der Algorithmus ist wie folgt:
- Beim ersten Durchlauf organisiert der Lochkartensortierer die Karten ähnlich wie beim Sortieren numerischer Datenfelder. Der Unterschied besteht darin, dass bei der alphabetischen Sortierung nur neun Taschen betroffen sind: vom 1. bis zum 9 ..
- Nach Abschluss der Sortierung entfernt der Bediener die Lochkarten aus den digitalen Taschen. Wiederum in der Reihenfolge (wie im Fall der Bestellung nach einem numerischen Datenfeld): beginnend mit der ersten Tasche und endend mit der neunten. Der Bediener sendet das gesammelte Kartenspiel zum zweiten Mal zum Sortieren.
- Beim zweiten Durchlauf liest der Lochkartensortierer nur die Zeilen der „Zonen“ (0, 11 und 12) und ignoriert die Zeilen mit Zahlen.
- Infolgedessen werden bestellte Lochkarten vom Sortierer in drei "zonale" Taschen verteilt: von A bis I werden in die 12. Tasche gelegt; von J nach R - im 11 .; von S nach Z - in der 0 ..
- Wenn die Sortierung nicht nach einem ersten Zeichen, sondern beispielsweise nach zwei oder drei zuerst durchgeführt werden muss, wird der oben beschriebene Prozess (Schritte eins bis vier) nacheinander für jedes Zeichen ausgeführt. Das heißt, Für jedes Symbol werden zwei Durchläufe durch den Lochkartensortierer durchgeführt.
Als es noch keine Computer gab, verarbeiteten Unternehmen Big Data mit Lochkarten. Trotz der Tatsache, dass Lochkarten unwiderruflich veraltet sind, stoßen wir immer noch auf ihren Einfluss auf den aktuellen Stand der Computertechnologie - wann immer wir uns mit der Textformatierung mit 80-Zeichen-Zeilen abfinden müssen. Ähnliches wird beispielsweise bei der Arbeit mit Far Manager beobachtet.