Kapitel 11 - Ordnung im Chaos PDF

11. Ordnung im Chaos Viele Chefs glauben, dass Chaos auf dem Schreibtisch der Mitarbeiterinnen und Mit- arbeiter für Chaos in deren Kopf steht. Verschiedene Abhandlungen über Karrierepla- nung empfehlen daher dringend, Ordnung zu halten. Albert Einstein und Sigmund Freud waren beide eher Befürworter...

11. Ordnung im Chaos Viele Chefs glauben, dass Chaos auf dem Schreibtisch der Mitarbeiterinnen und Mit- arbeiter für Chaos in deren Kopf steht. Verschiedene Abhandlungen über Karrierepla- nung empfehlen daher dringend, Ordnung zu halten. Albert Einstein und Sigmund Freud waren beide eher Befürworter des Chaos: Laut Berichten von Zeitgenossen hat- ten sie den typischen „Krater“ aus Dokumenten und angefangenen Schriftstücken auf ihrem Arbeitsplatz. Für Einstein war dieses Chaos der beste Beweis für die Sätze der Thermodynamik, nach denen Chaos der natürliche Zustand ist. Sigmund Freud ver- trat sogar etwas weitergehende Theorien, was den psychologischen Hintergrund eines # 01 Ordnungsliebhabers angeht, aber das möchte ich hier gar nicht vertiefen. Wichtig ist, dass es offenbar zwei Geisteshaltungen bezüglich des Arbeitsplatzes gibt – die der offensichtlichen Ordnung und die des offensichtlichen Chaos. Die Infor- matik ist bereits auf vielen anderen Gebieten Vermittler zwischen unterschiedlichen Disziplinen und vielleicht kann sie auch in diesem Fall eine Brücke bilden. Eine der wichtigen Methoden, um Daten im Computerspeicher abzulegen und schnell wieder # 02 darauf zuzugreifen, führt nämlich zu einer chaotischen Anordnung! Trotzdem kön- nen einzelne Datensätze in Windeseile wieder hervorgeholt werden. Trügt hier also der Schein? Im folgenden Kapitel werden wir uns dieser Thematik näher widmen. Es wäre übrigens günstig, wenn Sie das Kapitel „Sortieren“ vorher durcharbeiten, da das Folgende größtenteils daran anknüpft. # 04 # 05 # 06 Warum Ordnung? Im zweiten Kapitel haben wir uns zunächst mit dem Sortieren beschäftigt, ohne wirk- # 08 # 09 # 10 # 11 # 12 lich darüber nachzudenken, warum das eigentlich sinnvoll ist. Eine Begründung folg- te dann am Ende des achten Kapitels. Hier wollen wir nun gezielt anknüpfen. Wir versetzen uns ein weiteres Mal in die Lage des Computers. Packen Sie den Papier- speicher aus und 16 Kärtchen mit Zahlen darauf. Mischen Sie die Karten und verteilen Sie diese auf den ersten 16 Speicherpositionen wie in Abbildung 11.1. Die Zeiger „An- # 16 # 17 # 18 # 19 # 20 # 21 # 22 # 23 # 24 # 25 Abbildung 11.1 Speicherzeiger Papierspeicher mit chaoti- schem Inhalt 0-20 21-29 30-32 33-35 36-39 40-42 43-44 45-46 47-48 49 50 51-52 53-54 55-56 57-58 59-61 62-64 65-70 71-78 79-99 # 32 # 33 # 034 # 35 # 36 # 37 # 38 # 39 # 40 # 41 # 42 # 43 # 44 # 45 # 46 # 47 # 48 # 49 # 50 # 51 # 52 A B C D E F G H I J K L M N O P Q R S T 187650 302782 503710 861867 212088 522107 38897 955099 96588 424261 747690 44948 581176 133986 467199 145423 aber Ablage absurd Acker Anbau Anlage Anteil Arbeit Aufruf auftun Ausland Auslauf Auster Ausweg Bank Beere 276637 338210 425565 471452 544520 582278 260249 562184 444082 409121 559505 495493 163105 124890 448463 677562 Anfang Ende 153  fang“, „Ende“ und „Speicherzeiger“ erleichtern das Nachspielen der Vorgehensweise des Computers. Denken Sie daran: Der Computer kann immer nur die Karte unter einem der Zeiger „sehen“ und muss den Zeiger neu setzen, um eine andere Karte an- zuschauen. Finden Sie als Computer eine bestimmte vorhandene Karte (zum Beispiel die mit der blauen 38897). Versuchen Sie dabei möglichst geschickt vorzugehen. Schrei- ben Sie auf, wie viele „Rechenschritte“ Sie benötigt haben, und wiederholen den Versuch ein paar Mal. Auf diese Weise können Sie abschätzen, wie lange die Suche im Mittel dauert. ▶ ▶ ▶ ◀ ◀ ◀ Egal, wie Sie es drehen und wenden, letztendlich bleibt bei einem chaotischen Spei- cherinhalt immer nur die Möglichkeit, eine Karte nach der anderen zu überprüfen, bis man die gesuchte gefunden hat – zum Beispiel nach dem Algorithmus in Abbildung 11.2. Man nennt das auch „sequentielle Suche“, weil man der Reihe nach sucht. Im Mittel muss man etwa die Hälfte der Karten anschauen, bis man fündig wird, denn die gesuchte Karte kann sich ja zufällig ganz am Anfang oder auch ganz am Ende be- finden. Bei 16 Karten wird man also durchschnittlich etwa nach 8 Karten fertig sein. Als Nächstes sortieren Sie bitte die Karten, zum Beispiel nach der blauen Zahl. Ver- wenden Sie zum Üben am besten eines der Verfahren aus dem zweiten Kapitel. Selbst- verständlich dürfen Sie die Karten auch „einfach so ordnen“. Abbildung 11.3 zeigt eine sortierte Folge. Versuchen Sie nun wiederum, in möglichst wenigen Schritten eine bestimmte Karte zu finden. Das Verfahren haben wir am Ende von Kapitel 8 bereits verwendet. Kleiner Tipp: Fangen Sie mit dem Speicherzeiger auf der Position #39 an, also etwa in der Mitte. Vielleicht erinnern Sie sich noch an das Zahlenratespiel: Ein Spieler denkt sich eine Zahl zwischen 0 und 100 aus und ein anderer soll die Zahl in möglichst wenigen Ver- suchen raten. Nach jedem Versuch sagt der erste Spieler, ob die gesuchte Zahl größer oder kleiner ist. Abbildung 11.2 Algorithmus für sequentielle Anfang und zeigen auf die erste bzw. die letzte Karte Ende Suche des zu durchsuchenden Bereichs Setze Speicherzeiger auf die erste zu sortierende Karte 0. Solange Karte unter Speicherzeiger nicht die gesuchte Karte ist 1. und zwischen Speicherzeiger Anfang und Ende ist...... verschiebe Speicherzeiger um eine Position nach rechts 2. Falls Karte unter die gesuchte Karte ist: gefunden, Speicherzeiger 3. sonst: Karte nicht vorhanden 154 11. Ordnung im Chaos  # 08 # 09 # 10 # 11 # 12 # 16 # 17 # 18 # 19 # 20 # 21 # 22 # 23 # 24 # 25 Abbildung 11.3 Speicherzeiger Papierspeicher mit sortierter Kartenfolge 0-20 21-29 30-32 33-35 36-39 40-42 43-44 45-46 47-48 49 50 51-52 53-54 55-56 57-58 59-61 62-64 65-70 71-78 79-99 # 32 # 33 # 034 # 35 # 36 # 37 # 38 # 39 # 40 # 41 # 42 # 43 # 44 # 45 # 46 # 47 # 48 # 49 # 50 # 51 # 52 A B C D E F G H I J K L M N O P Q R S T 38897 44948 96588 133986 145423 187650 212088 302782 424261 467199 503710 522107 581176 747690 861867 955099 Anteil Auslauf Aufruf Ausweg Beere aber Anbau Ablage auftun Bank absurd Anlage Auster Ausland Acker Arbeit 260249 495493 444082 124890 677562 276637 544520 338210 409121 448463 425565 582278 163105 559505 471452 562184 Anfang Ende Hier beginnt man am besten in der Mitte und halbiert dann immer die Anzahl noch möglicher Zahlen. Genau das gleiche Prinzip können wir auch mit dem Papierspei- cher zum Suchen einer Karte benutzen, falls die Karten im Speicher sortiert sind: Wir beginnen in der Mitte und kontrollieren, ob die Karte die gesuchte ist. Wenn nein, schauen wir, ob die Zahl größer oder kleiner als die gesuchte ist. Ist die gesuchte Zahl größer, muss sie sich rechts vom Speicherzeiger befinden. Ist sie kleiner, muss sie links sein. Das ergibt sich direkt aus der Sortierung! Auf diese Weise haben wir bereits die Hälfte der vorhandenen Karten ausgeschlossen und brauchen nur noch in der anderen Hälfte zu suchen. Wir setzen den Speicherzei- ger wiederum in die Mitte und wenden das gleiche Verfahren an, um erneut die Hälfte der Karten auszuschließen. Schaffen Sie es, dafür den Algorithmus zum Beispiel in der Art von Abbildung 11.2 zu formulieren und aufzuschreiben? ▶ ▶ ▶ ◀ ◀ ◀ Einen entsprechenden Algorithmus sehen Sie in Abbildung 11.4. Das Verfahren heißt auch „binäre Suche“ in einer sortierten Liste, weil man den Suchbereich immer in zwei Hälften teilt. Auch dieser Algorithmus funktioniert übrigens nur korrekt, wenn sich die gesuchte Karte auf jeden Fall im Speicher befindet. Wenn Sie die binäre Suche ein paar Mal durchführen, stellen Sie fest, dass Sie hier durchschnittlich vier, maximal fünf Vergleiche benötigen, um die Karte zu finden. Das Verfahren bringt uns also schneller ans Ziel. Das macht sich bei größeren Datenmengen noch viel stärker bemerkbar: Die binäre Suche schließt pro Schritt die Hälfte aller Daten aus. Umgekehrt ausgedrückt benöti- gen wir also für die Suche in einer doppelt so großen Datenbank nur einen einzigen Schritt mehr. Bei der sequentiellen Suche bräuchte der Algorithmus auch tatsächlich doppelt so viele Schritte. Die Experten wissen natürlich bereits aus Kapitel 2, dass sich der Suchaufwand bei n Karten formal durch log2n ausdrücken lässt. Warum Ordnung? 155  Abbildung 11.4 Algorithmus zur binären Anfang und zeigen auf die erste bzw. die letzte Karte Ende Suche des zu durchsuchenden Bereichs Setze auf die Mitte zwischen Speicherzeiger und Anfang Ende 0. (falls es keine „genaue” Mitte gibt, nimm die Karte links davon) Ist die gesuchte Zahl größer als die Zahl auf der Karte 1. unter ? Speicherzeiger Wenn JA: Lege Anfang auf die Karte rechts von Speicherzeiger 2. Wenn NEIN: Lege Ende auf die Karte links von Speicherzeiger 3. Wiederhole das ab Schritt (0.), bis die Karte unter Speicherzeiger 4. Das Chaos im Wandel der Zeit die gesuchte Karte ist oder links von Ende Anfang steht Das Wort kommt aus dem Griechischen und meint „den Falls Karte unter die gesuchte Karte ist: gefunden, Speicherzeiger unendlichen leeren Raum“ 5. sonst: Karte nicht vorhanden oder „die gestaltlose Urmasse des Weltraums“. Biblisch wur- de die Welt aus dem Chaos geschaffen. Früher verstand Ordnung oder Chaos? man also etwas Ursprüngli- ches, noch nicht Geformtes Wir haben damit nochmals bestätigt, dass Ordnung nicht nur einen ästhetischen Wert unter dem Chaos. für uns Menschen darstellt, sondern selbst für Maschinen und deren Algorithmen Heute bezeichnet man jede Form von Unordnung – echte Vorteile bringt. Als Nächstes möchte ich Ihnen die Frage stellen, was Ordnung besonders auch die von uns eigentlich ist. Hierfür machen wir ein kleines Spiel: allen geschaffene – als Chaos. Die Chaostheorie beschäf- Die Spalten in Abbildung 11.5 enthalten immer die gleichen zehn Zahlen in unter- tigt sich hingegen eher mit schiedlicher Reihenfolge. Welche Spalten sind sortiert, welche nicht? Können Sie dem Gegenteil: Ordnung den Grad der Unordnung in den Ihrer Meinung nach unsortierten Spalten beur- soll in scheinbar chaotischen teilen? Systemen gefunden werden. Bekanntestes Beispiel aus der Informatik sind die selbstähn- ▶ ▶ ▶ ◀ ◀ ◀ lichen Fraktale – zum Beispiel die aus einer sehr einfachen Formel gewonnene Mandel- Selbstverständlich erkennen Sie die gelbe Reihe A als sortiert, die anderen scheinen brot-Menge („Apfelmänn- dagegen auf den ersten Blick etwas chaotisch zu sein. Vielleicht haben Sie aber doch chen“), die auch beliebig fein bereits eine Ordnung ausmachen können. dargestellt immer wieder die gleichen, sich wiederholenden Schlüssel hierfür ist das Sortierkriterium. Bei der gelben Reihe ist das ganz offensicht- Grundfiguren enthält. lich – die Zahlen sind der Größe nach von der kleinsten zur größten aufgeführt. Die rote Reihe ist da schon etwas subtiler: Betrachten Sie nur die drei hinteren Stellen der Zahlen, also die letzten drei Ziffern. Stimmt nun die Sortierung wieder? Ich behaupte jetzt, dass auf die gleiche Weise auch für die blaue und die grüne Reihe je ein Sortierkriterium existiert. Es ist allerdings eine ziemlich harte Nuss, darauf zu kommen. Wenn Sie Lust haben, versuchen Sie die Regel herauszufinden, sonst lesen Sie einfach weiter. Solche Bilder kann man leicht mit ein paar Zeilen Pro- ▶ ▶ ▶ ◀ ◀ ◀ grammcode selbst herstellen. 156 11. Ordnung im Chaos  0 727 932018 973412 Abbildung 11.5 Jede Spalte enthält die gleichen zehn Zahlen. Welche 1 213121 213121 213121 727 davon ist geordnet? 2 545955 832213 903512 961347 3 832213 961347 961347 545955 4 903512 973412 979834 945630 5 932018 903512 932018 903512 6 945630 945630 545955 7 961347 727 727 213121 8 973412 979834 973412 832213 9 979834 545955 945630 979834 10 832213 932018 In der blauen Reihe steckt jeweils die doppelte Quersumme: Nehmen Sie die Ziffern der Zahlen einzeln und addieren Sie sie. Das Gleiche machen Sie nochmals mit dem Ergebnis. Die Resultate liegen bei den gegebenen Zahlen zwischen 1 und 10 und ge- nau danach sind sie sortiert. Beispiele: Die Quersumme von 945630 ist 9 + 4 + 5 + 6 + 3 + 0 = 27 Die Quersumme von 27 ist 2 + 7 = 9 Daher ist 945630 in Zeile 9 eingeordnet. Um das Geheimnis der grünen Reihe zu knacken, denken Sie an die schriftliche Di- vision mit Rest aus der Grundschule zurück. Dort rechnet man nicht mit Brüchen, sondern nur mit ganzen Zahlen. Dabei kann immer ein Divisionsrest übrig bleiben. 27 geteilt durch 12 ergibt 2, Rest 3 In der Informatik braucht man häufig nur den Rest dieser Division und gar nicht das Ergebnis, daher hat man die Berechnung des Restes zur eigenen Rechenart gemacht, genannt „modulo“ oder abgekürzt „mod“. Man schreibt zum Beispiel: 27 mod 12 = 3 Damit gleich Verwechslungen vermieden werden: Dies ist ein sehr verwandter, aber trotzdem etwas anderer Gebrauch von „mod“ als in der Mathematik! Ordnung oder Chaos? 157  Resteverwertung So wie für das Enträtseln der grünen Spalte benötigen wir den Divisionsrest noch häufiger in diesem Kapitel und auch insgesamt für verschiedene Verfahren in der In- formatik. In Zeiten des Taschenrechners verlernen wir sehr schnell die schriftliche Di- vision mit Rest, wie man sie in der Grundschule betreibt. Das ist völlig normal – selbst bei den Studierenden der Informatik oder Mathematik gibt es sehr viele, die sich diese Technik erst wieder aneignen müssen. Daher hier eine kleine Wiederholung für alle, die sich nicht mehr genau daran erinnern... Prinzipiell nutzen wir unser Dezimalsystem aus, um größere Divisionen der Form Dividend : Divisor = Ergebnis in kleinere, leichter zu beherrschende Operationen zu unterteilen – ein sehr Infor- matik-nahes Vorgehen, wie zum Beispiel auch die Äthiopische Multiplikation weiter vorne im Buch! Am Beispiel lässt das sich immer am besten lernen, daher versuchen wir es mit: 498737894 : 13 = ? Zunächst nehmen wir so viele der ersten Ziffern des Dividenden, dass die entstehende Zahl gerade größer wird als der Divisor – in diesem Fall also „49“. Wir teilen diese Zahl durch den Divisor und schreiben das (einstellige) Ergebnis hinter das Gleich- heitszeichen. Dabei beachten wir nur ganze Anteile des Ergebnisses. 498737894 : 13 = 3 Die Zahl ist aber meistens nicht glatt teilbar. In diesem Fall bedeutet die 3 also, dass der Divisor 13 genau 3-mal glatt in 49 unterzubringen ist. Da 3 mal 13 jedoch 39 ergibt, bleibt ein Rest. Diesen ermitteln wir formal, indem wir die gerade errechnete Ziffer mit dem Divisor multiplizieren (= 39) und direkt unter die ersten Ziffern des Dividenden schreiben. Per Subtraktion ermitteln wir dann den Divisionsrest dieser ersten Operation und schreiben ihn hin. Mit diesem Rest muss dann die Division noch weiter betrieben werden. 498737894 : 13 = 3 39 10 Allerdings haben wir ja noch einen weiteren „Rest“, nämlich die Ziffern, die wir bisher gar nicht betrachtet hatten. Sie sind in der folgenden Formel nochmals grau wieder- holt, weil man sie normalerweise nicht hinschreibt, aber trotzdem mit ihnen rechnet: 498737894 : 13 = 3 39 108737894 : 13 = 3... Jetzt geht es wirklich à la Informatik weiter: Wir verfahren mit dieser neuen Berech- nung (fast) ebenso wie am Anfang mit der kompletten Division, nur dass die bereits ermittelten Anteile (in diesem Fall die 3) einfach stehen bleiben. Statt wieder zu er- mitteln, wie viele Ziffern notwendig sind, damit sie größer als der Divisor werden, nehmen wir jetzt immer nur die nächste Ziffer zum Rest hinzu – in diesem Fall also 158 11. Ordnung im Chaos die 8. Danach wird wieder geteilt sowie der Rest und damit eine neue Rest-Berech- nung ermittelt. 498737894 : 13 = 3 39 108737894 : 13 = 38 104 4737894 : 13 = 38... Das machen wir, bis der entstandene Divisionsrest so klein ist, dass er kleiner als der Divisor ist – die Zahl lässt sich nicht mehr weiter teilen und wir schreiben den Rest, als solchen gekennzeichnet, einfach daneben: 498737894 : 13 = 38364453 Rest 5 39 108737894 : 13 = 3... 104 4737894 : 13 = 38... 39 837894 : 13 = 383... 78 57894 : 13 = 3836... 52 5894 : 13 = 38364... 52 694 : 13 = 383644... 65 44 : 13 = 3836445... 39 5 : 13 = 38364453 Rest 5 Die grauen Teile schreibt man normalerweise nicht mehr auf, sie dienen hier nur der Verdeutlichung, dass im Prinzip immer wieder der gleiche Algorithmus durchgeführt wird. Für die modulo-Rechnung, wie sie in diesem Kapitel häufig verwendet wird, benötigen wir nur den Rest, nicht das eigentliche Ergebnis. Um herauszufinden, wie die Zahlen der grünen Spalte geordnet sind, berechnen Sie einfach immer den Divisionsrest beim Teilen durch 11. Beispiel: 945630 mod 11 = 4, daher ist 945630 in Zeile 4 einsortiert. Es sind also wirklich alle der oben angegebenen Spalten geordnet, allerdings nur in der gelben Spalte nach einem uns Menschen offensichtlichen Kriterium. An die Ord- nung der roten Spalte könnten wir uns vielleicht noch gewöhnen, aber Berechnungen anstellen, um Zahlen zu sortieren, so wie in den restlichen Spalten – das geht zu weit. So werden Computer auch immer die „menschlichen“ Sortierkriterien verwenden, wenn es darum geht, den Benutzern etwas zu präsentieren. Beispiele hierfür sind Te- lefonverzeichnisse, Kundendateien, eine Hand voller Spielkarten bei einem Skatpro- gramm usw. Resteverwertung 159  Ordnung ist nicht gleich Ordnung Wie sieht es allerdings aus, wenn die Daten ausschließlich im Computer gespeichert werden und dort auch verbleiben? Wenn jeder, der einen bestimmten Datensatz sucht, einfach den Computer danach fragt? Computer rechnen sehr schnell, haben also kein Problem mit „seltsamen“ Sortierkriterien. Das heißt, prinzipiell spricht nichts dage- gen, Daten im Computerspeicher nach etwas anderem als der Größe zu sortieren. Die nächste Frage ist allerdings: Spricht etwas dafür? Um sie zu beantworten, schauen wir uns nochmals die Abbildung 11.5 an. Um einen Eintrag aus der gelben Spalte zu finden, kann man die binäre Suche anwenden. Ge- nauso kann man auch suchen, um mit dem entsprechenden Kriterium einen Eintrag aus den anderen Spalten zu finden. Aber es geht auch schneller: In den hinteren Spalten bestimmt das Sortierkriterium nicht nur die relative Position der Einträge untereinander (so wie „832213 kommt vor 973412“), sondern es legt die absolute Position in der Tabelle fest. Um einen Eintrag in der roten Spalte zu finden, nehmen Sie einfach die dritte Ziffer von rechts – sie ist identisch mit der Zeilennummer. Bei der blauen Spalte ist das die doppelte Quersumme und in der grünen Spalte der Divisionsrest beim Teilen durch 11. Das erklärt auch das Rätsel, warum in dieser Spalte Zeile 6 keinen Eintrag enthält: Unter den zu speichernden Zahlen gibt es einfach keine mit Rest 6 bei der Division durch 11. Erkennen Sie den Vorteil? Statt nach einem Eintrag suchen zu müssen, berechnet der Computer einfach dessen Position. Zum Speichern genügt ein einzelner Schreibvor- gang. Um die Daten wieder abzurufen, genügt ein einziger Lesevorgang. Dieses Ver- fahren setzt man daher tatsächlich immer dann ein, wenn es wichtig ist, Daten sehr schnell abzuspeichern und sehr schnell wieder abzurufen. Wie oben in den hinteren Spalten werden die Daten dabei oft in einer für den Men- schen chaotisch aussehenden Weise angeordnet. Daher nennt man das Verfahren „Hashing“ von englisch „Hash“ – zu Deutsch „Durcheinander, Kuddelmuddel“. Wenn Sie genau darüber nachdenken, kennen Sie Hashing auch sicherlich aus Ihrem Loci Die sogenannte Loci-Methode Alltag – hier schließe ich mal von mir auf andere: Wie oft gibt es die Situation, in zur Steigerung der Merkfä- der man irgendein Objekt wegsortiert, ohne darüber nachzudenken. Auf diese Weise higkeit macht sich übrigens landet die Einkaufsquittung im Bücherregal oder der Lieblingskugelschreiber in der zunutze, dass wir uns recht Werkzeugkiste. Überraschenderweise finde ich diese Gegenstände (meistens) sehr gut daran erinnern können, wo wir bestimmte Dinge ver- leicht wieder. Indem ich in Gedanken so tue, als würde ich den Kugelschreiber erneut stauen. Möchten Sie sich etwa weglegen, komme ich erneut auf die gleiche Idee „Werkzeugkiste“ und werde dort fün- die Liste für den nächsten dig! Einkauf merken, legen Sie die gewünschten Objekte in Ungleich schwieriger wird die Sache manchmal, wenn ich beim Aufräumen eine ganz Gedanken in Ihrem Büro oder bewusste Entscheidung getroffen habe: Den Pass für die Reise nächste Woche habe ich Wohnzimmer ab. Im Laden an einen Ort gelegt, wo ich ihn garantiert sicher wiederfinde – nur fällt mir zwei Tage müssen Sie sich dann nur noch das Zimmer vorstellen, um später absolut nicht mehr ein, wo dieser Ort ist. Natürlich weiß ich noch ganz genau, sich wieder an die Einkaufslis- wo ich den Pass gefunden hatte, bevor ich ihn am vermeintlich sicheren Ort deponier- te zu erinnern. te... hätte ich ihn nur dort gelassen! So weit zumindest die Theorie. Bitte probieren Sie Kommt Ihnen das irgendwie bekannt vor? das besser nicht gerade am Abend vor einem Feiertag Genau dieses „intuitive“ Prinzip wird beim Hashing genutzt. Aufgrund einer Formel aus … wird der Speicherort für einen Datensatz festgelegt, und wenn wir diesen später wie- 160 11. Ordnung im Chaos der suchen, finden wir ihn aufgrund der gleichen Formel wieder. Bevor ich nun ge- nauer darauf eingehe, wie das Verfahren günstig umgesetzt werden kann, möchte ich eine andere Frage aufwerfen: Wo ist der Haken? Warum benutzt man überhaupt noch eine konventionelle Sortierung? Das können wir experimentell beantworten: Nehmen Sie 16 beliebige Sortierkarten mit Buchstaben, mischen diese und legen dann eine nach der anderen auf einem gro- ßen Schreibtisch ab. Schauen Sie sich dabei jeweils den Buchstaben an und legen die Karte verdeckt so ab, dass Sie sie wahrscheinlich wiederfinden. Suchen Sie nun die Karte mit dem „F“ (oder eine andere aus Ihrem Satz)! Wahrschein- lich finden Sie diese recht schnell. Jetzt machen Sie das Gleiche noch einmal, allerdings diesmal mit einer sehr kleinen Fläche: Die Karten müssen alle auf einer Postkarte Platz haben. Versuchen Sie nun die Karte mit dem „L“ zu finden! Ist das ebenfalls so einfach? Wahrscheinlich sind Sie bei diesem Experiment eher geneigt, die Karten beim Hinlegen zu sortieren. Führen Sie den Versuch mit verschiedenen Testpersonen durch. Wahrscheinlich ha- ben die meisten kein Problem, eine Karte auf der großen Fläche wiederzufinden, brau- chen allerdings mehrere Versuche, um dies auf der kleinen Fläche zu schaffen. Genau- so fällt es uns deutlich leichter, Gegenstände in einem großen Raum einfach „intuitiv“ zu platzieren und dann wiederzufinden als in einem kleinen. Hashing benötigt Platz! Das ist im Computer nicht anders als beim realen Versuch mit den Karten. Daher benutzt man das Verfahren immer dann, wenn der schnelle Zugriff auf die Daten wichtiger ist als geringer Speicherverbrauch. Das wird im Folgenden noch klarer, wenn wir das eigentliche Verfahren besprochen haben! Die nächste Frage ist: Warum kann das Kriterium für Hashing nicht so gewählt wer- den, dass letztlich auch eine sortierte Folge herauskommt? Die Antwort haben wir im Wesentlichen im Kapitel über das Sortieren bereits unter dem Stichwort „Prox- map-Sort“ gegeben: Leider haben Zahlen und andere Schlüsselbegriffe, die von Men- schen erzeugt wurden, die Tendenz, sich in kleinen Bereichen zu häufen. Wenn man zum Beispiel die literarischen Neuerscheinungen des Jahres 2017 nach ihren Standard-Buchnummern (ISBN) sortiert, werden wahrscheinlich viele kleine Zahlenbereiche dicht gefüllt sein und große Bereiche fehlen (Nummern, die Verlage bereits 2016 und früher vergeben haben, sowie solche, die noch zu vergeben sind). # Zahl Das liegt daran, dass die meisten Verlage ihre Buchnummern aufsteigend lückenlos 0 727 vergeben. 1 Ein anderes Beispiel ist die Datei einer Krankenkasse, in der die Mitglieder nach Ge- burtsdatum angeordnet sind – auch hier werden bestimmte Jahreszahlen besonders 2 213121 häufig vorkommen, weil es einfach mehr Menschen mit einem Alter von 45 gibt als 3 solche mit 100. Betrachten Sie nochmals Abbildung 11.5 und versuchen Sie die gegebenen Zahlen mit 4 dem Kriterium „Zeilennummer = erste Stelle (Hunderttausender)“ korrekt einzuord- 5 545955 nen. Das funktioniert mit den kleineren fünf Zahlen tatsächlich. Die nebenstehende Tabelle zeigt das Ergebnis. Allerdings müssten die nächsten fünf Zahlen alle in die 6 bereits besetzte Zeile 9! Wie das aber mit Speicherstellen so ist: Sie bieten nur Platz für 7 einen einzigen Wert. 8 832213 Beim Proxmap-Sort hatten wir uns durch dynamische Anpassung der Skala für die Tabelle beholfen: In Fall des Beispiels würden nur wenige Zeilen für die Zahlen zwi- 9 903512 Ordnung ist nicht gleich Ordnung 161  schen 0 und 900000 reserviert und mehr Zeilen für Zahlen zwischen 900000 und # Zahl 999999, so wie in der nächsten Tabelle. Um diese Einteilung zu finden, muss man je- 00 – 20 727 doch erst eine statistische Analyse der einzusortierenden Zahlen durchführen. Das ist manchmal sehr aufwendig, oft sogar unmöglich, weil man zu Beginn noch gar nicht 21 – 41 213121 weiß, mit welchen Zahlen man rechnen muss. 42 – 62 545955 Effektiv wird mit dieser veränderten Einteilung die Gleichverteilung über dem Spei- 63 – 83 832213 cherplatz bewirkt: Wenn man eine Anzahl von Zahlen einsortiert, werden diese unge- fähr immer gleichmäßig aufgeteilt. Auf diese Weise ist es am wenigsten wahrschein- 84 – 90 903512 lich, dass zwei Zahlen die gleiche Speicherstelle belegen. 91 – 93 932018 Wie an den hinteren Spalten von Abbildung 11.5 zu sehen war, können wir diese Gleichverteilung jedoch auch anders herstellen: indem wir das Sortierkriterium ver- 94 – 95 945630 ändern. Wie, das wollen wir jetzt im Experiment herausfinden. 960 – 969 961347 Sie benötigen die Sortierkarten mit den roten Zahlen und den Papierspeicher unten 970 – 975 973412 (für die Karten aus der Kopiervorlage im Buch) bzw. ganz rechts (für die Karten aus dem Bastelbogen) mit Speicherstellen #0 bis #9. Mischen Sie die Karten und nehmen 976 – 999 979834 Sie dann immer zehn Karten, um sie auf zehn Speicherpositionen zu verteilen. Dabei nutzen Sie bitte zunächst die Hunderttausender-Stelle der roten Zahlen als Kriterium. Die Zahl 544520 kommt zum Beispiel auf die Speicherstelle #5 und die Zahl 66.580 auf die Speicherstelle #0 (da die Zahl kleiner als 100000 ist und damit an der entspre- chenden Stelle quasi eine 0 hat). Führen Sie diesen Versuch 10- bis 20-mal durch und schreiben jeweils auf, wie viele Karten nicht mehr auf eine Speicherstelle gepasst haben, weil dort bereits eine Karte lag. So etwas nennt man übrigens „Kollision“, weil die gewünschte Einordnung einer Wussten Sie übrigens? Wenn 30 Menschen zufällig Karte mit der dort bereits liegenden Karte „kollidiert“. zusammenkommen (zum Bestimmen Sie die mittlere Anzahl der Kollisionen, indem Sie die Summe durch die Beispiel in einer Schulklas- se), dann ist es sehr wahr- Anzahl der Versuche teilen. Zum Beispiel bin ich bei 20 Versuchen auf 97 Kollisionen scheinlich, dass zwei oder gekommen, was durchschnittlich 4,85 Kollisionen entspricht. mehr davon am gleichen Tag Geburtstag feiern. Genau Jetzt machen Sie den gleichen Versuch nochmals – allerdings nehmen Sie nun die genommen liegt die Wahr- letzte Stelle, also die 1er-Stelle, um die Karten auf die Speicherstellen zu sortieren. Die scheinlichkeit ungefähr bei Zahlen 544520 und 66580 kämen nun also beide auf die Speicherstelle 0 – was bereits 70 %. Bei 40 Personen sind zu einer Kollision führte, wenn wir diese Karten in einem gemischten Paket fänden. das bereits ca. 90 %. Sie sehen an diesem Beispiel, dass es Bestimmen Sie wieder die durchschnittliche Anzahl der Kollisionen. Ist dieses Er- fast unmöglich ist, Kollisionen ganz zu vermeiden. gebnis besser oder schlechter als das Ergebnis mit den Hunderter-Stellen? ▶ ▶ ▶ ◀ ◀ ◀ Natürlich ist das mit statistischen Versuchen immer so eine Sache, aber wahrschein- lich haben Sie ein ähnliches Ergebnis wie ich erzielt: Bei 20 Versuchen waren das 75 Kollisionen, also durchschnittlich 3,75. Man kann demnach unter sonst gleichen Vor- aussetzungen mit diesem Kriterium ungefähr eine Karte mehr speichern. Abbildung 11.6 Hashfeld für Sortierkarten aus #0 #1 #2 #3 #4 #5 #6 #7 #8 #9 der Kopiervorlage im Buch 162 11. Ordnung im Chaos Offenbar geht es beim Hashing also hauptsächlich darum, ein gutes Sortierkriterium zu finden. In diesem Fall scheint zum Beispiel das Kriterium „1er-Stelle“ besser geeig- net zu sein als „100.000er-Stelle“, weil es eine gleichmäßigere Verteilung der Karten auf die Speicherstellen ergibt. Trotzdem sollte man selbstverständlich eine Karte auch einordnen können, wenn ihr Abbildung 11.7 Hashfeld für Sortierkarten aus eigentlicher Platz bereits belegt ist. Denken wir wieder an das Zimmer-Beispiel zu- dem Bastelbogen rück: Wenn Sie einen Gegenstand in eine Schublade legen möchten, diese ist aber be- reits bis zum Rand gefüllt, fällt Ihnen sicherlich noch ein „zweitbester“ Ort ein, etwa die nächste Schublade darunter. Wenn Sie beim Suchen nach dem Gegenstand dann #9 am ersten Platz keinen Erfolg haben, ziehen Sie wahrscheinlich auch ganz intuitiv die nächste Schublade auf, um den Gegenstand dann zu finden. Beim Hashing nennt man dies „Kollisionsbehandlung“. Eine Kollisionsbehandlung wird durchgeführt, sobald ein Datensatz nicht an seiner eigentlichen Stelle in den #8 Speicher geschrieben werden kann, weil diese bereits belegt ist. Die einfachste Stra- tegie dazu erinnert an unser Vorgehen beim Aufräumen im Zimmer: „Nimm einfach die nächste Schublade“, oder im Fall des Computers: „Nimm einfach die nächste freie Speicherstelle.“ #7 Versuchen Sie nun einfach einmal einen neuen Satz aus zehn gemischten Karten auf die zehn Speicherstellen zu hashen. Bitte beachten Sie, dass man wieder von vorne anfängt, wenn man beim Suchen der nächsten freien Speicherstelle am Ende angekommen ist! #6 ▶ ▶ ▶ ◀ ◀ ◀ Nehmen wir an, Sie hashen die folgenden Zahlen nach der „Einerstelle“ in der Rei- #5 henfolge: 124890, 425565, 582278, 444082, 471452, 544520, 562184, 409121, 677562, 276637 Die Hashtabelle ist danach folgendermaßen gefüllt: #4 #0 #1 #2 #3 #4 #5 #6 #7 #8 #9 124890 544520 444082 471452 562184 425565 409121 677562 582278 276637 #3 Beim Suchen nach einer Karte darf man sich nun natürlich ebenfalls nicht darauf be- schränken, an der ihr zugeteilten Speicherstelle zu schauen. Falls sich dort eine andere Karte befindet, muss man auch die nächsten Speicherpositionen durchsuchen. Suchen wir in der Tabelle oben beispielsweise die Karte mit der roten Zahl 409121. #2 Eigentlich würden wir sie auf Position #1 vermuten, da die letzte Stelle 1 ist. Dort befindet sich allerdings eine andere Karte. Also versuchen wir es eine Position weiter. Auch dort werden wir nicht fündig. Insgesamt müssen wir sechs Karten anschauen, bis wir die gesuchte Zahl erreichen! Mit der binären Suche in einer sortierten Folge #1 hätten wir maximal vier Vergleiche benötigt, das Hashing ist also sogar ungünstiger! Weiter oben hatte ich bereits beschrieben, dass das intuitive Aufräumen in einem sehr kleinen Zimmer nicht funktioniert. Hier können Sie nun das Pendant beim Hashing erkennen: Wenn der Speicherplatz zu dicht belegt ist, nimmt man besser die klassi- #0 sche Sortierung der Daten, zusammen mit der binären Suche. Das innovative Hashing benötigt mehr Platz! Ordnung ist nicht gleich Ordnung 163  Das impliziert sofort die Frage, wie viel Speicherplatz eigentlich notwendig ist. Als Nächstes wollen wir daher durch Probieren ermitteln, wie gut das Hashing mit ver- schiedenen Belegungsfaktoren abschneidet. Bitte mischen Sie den Kartenstapel wieder. Nehmen Sie nun zehn Karten und hashen diese in die zehn Speicherstellen – genau wie oben. Diesmal führen Sie jedoch eine Strichliste: Für jede Speicherposition, die Sie ansprechen müssen (also auch belegte), machen Sie einen Strich. Falls also eine Karte erst in die vierte Speicherstelle abgelegt werden kann, weil die drei ersten Positionen belegt sind, ergibt das vier Striche. Zur Kontrolle: Im Beispiel oben müssten beim Hashing 24 Striche gemacht werden. Pro Karte waren also durchschnittlich 24 geteilt durch 10, also 2,4 Speicherzugriffe notwendig. Führen Sie diesen Versuch 10- bis 20-mal durch, um zufällige Ergebnisse auszu- schließen. Teilen Sie dann die Anzahl der Striche durch die Anzahl der Versuche und dann nochmals durch 10. Auf diese Weise erhalten Sie die mittlere Anzahl von Speicherzugriffen, die pro Karte benötigt wird. ▶ ▶ ▶ ◀ ◀ ◀ Das Beispiel oben scheint statistisch bereits ziemlich durchschnittlich zu sein, denn wenn man sehr viele Versuche durchführt, kommt man tatsächlich auf ungefähr 2,4 Speicherzugriffe pro Element. Führen Sie nun den obigen Versuch mit der Strichliste noch ein paar Mal durch. Sortieren Sie nun aber nur 9, 8, 7, 6, 5, 4 und 3 Karten auf einmal in den Speicher. Natürlich müssen Sie dann die Anzahl von Strichen am Ende auch durch die An- zahl der Versuche und die Anzahl der Karten (also zum Beispiel 9) teilen, um auf die durchschnittliche Zugriffszahl pro Karte zu kommen. ▶ ▶ ▶ ◀ ◀ ◀ Wahrscheinlich kommen Sie auf ähnliche Ergebnisse wie ich, die in folgender Tabelle zusammengefasst sind: Anzahl Karten 3 4 5 6 7 8 9 10 Zugriffe pro Karte 1,1 1,2 1,3 1,4 1,6 1,8 2,0 2,4 Sie konnten also nachvollziehen, dass das Hashing immer besser wird, je weniger Karten man in den Speicher einsortiert. Allerdings sollte es einen guten Kompromiss zwischen Speicherausnutzung und Anzahl der Zugriffe geben, zum Beispiel eine Kar- tenzahl zwischen 7 und 8. Das entspricht einem Belegungsgrad von 70 % bis 80 %. Der Belegungsgrad gibt an, wie viel Speicher prozentual ausgenutzt ist. Nun wäre ja eventuell möglich, dass unser kleiner Versuch mit zehn Karten nicht au- thentisch für große Hashtabellen ist. Daher habe ich für Sie das Experiment schon mit deutlich mehr Karten durchgeführt, die in einen Speicher mit 10.000 Stellen einsor- tiert werden. Das Ergebnis können Sie in folgender Tabelle ablesen. 164 11. Ordnung im Chaos  Anzahl Karten Zugriffe pro Karte Anzahl Karten Zugriffe pro Karte 10.000 63,1 5.000 1,5 9.500 10,1 4.500 1,4 9.000 5,5 4.000 1,3 8.500 3,8 3.500 1,3 8.000 3,0 3.000 1,2 7.500 2,5 2.500 1,2 7.000 2,2 2.000 1,1 6.500 1,9 1.500 1,1 6.000 1,8 1.000 1,1 5.500 1,6 500 1,0 Belegen wir also die 10.000 Speicherstellen vollständig, benötigen wir pro Suche durchschnittlich etwas über 63 Speicherzugriffe. Zum Vergleich: Die binäre Suche würde in einer sortierten Liste mit durchschnittlich 13 Speicherzugriffen auskommen. Allerdings wird das Hashing bereits attraktiv, wenn wir den Speicher zu 95 % füllen: Bei 9.500 Datensätzen benötigt man nur noch gut 10 Speicherzugriffe, was besser als mit der binären Suche ist. Ein Belegungsgrad von 80 % senkt diese Zahl sogar noch auf durchschnittlich 3. In der Praxis versucht man tatsächlich, den Belegungsgrad beim Hashverfahren unter 85 % zu halten. In Programmen, bei denen es auf noch schnelleren Zugriff ankommt, kann man den Speicherplatz auch noch ausufernder nutzen. So liegt die durchschnitt- liche Anzahl von Zugriffen nur noch knapp über 1, wenn man nur 20 % des verfügba- ren Speichers in Anspruch nimmt. Was steckt dahinter? Die wichtigsten Grundsätze des Hashings konnten Sie bereits selbst herausfinden: Es kommt hauptsächlich darauf an, ein Kriterium für die Verteilung der Datensätze auf die Speicherpositionen zu finden, das den Speicherplatz gleichmäßig ausnutzt. Um hier weiter in die Tiefe zu gehen, benötigen wir noch ein paar Fachausdrücke: Den Wert oder die Zeichenfolge, nach dem bzw. der sortiert wird, nennt man auch „Schlüssel“. Im Beispiel oben war der Schlüssel einer Karte also die rote Zahl. Aus dem Schlüssel wird dann direkt über eine Berechnung die Speicherposition be- stimmt. Diese Berechnung war in unseren bisherigen Versuchen immer recht einfach – meistens wurde schlicht die erste oder letzte Ziffer genommen. Hier könnte jedoch auch eine komplizierte Formel verwendet werden. Die Berechnungsvorschrift nennt man auch „Hashfunktion“. Wenn wir den Schlüssel mit „s“ abkürzen und die Hashfunktion mit „h“, ergibt sich also für die Speicherposition eines Datensatzes bzw. einer Karte: Position = h (s) Was steckt dahinter? 165  Im Beispiel nach Abbildung 11.5 ist die Hashfunktion die letzte Ziffer. Diese ist iden- tisch mit dem Divisionsrest beim Teilen durch 10. Es gilt also: h (s) = s mod 10 Die Karte mit der 425565 kommt also auf die Position h (425565) = 425565 mod 10 = 5 Ebenfalls im Experiment ausprobiert haben wir, dass die Hashfunktion sowohl zum Einordnen der Datensätze bzw. Karten dient als auch dazu, einen bestimmten Daten- satz wieder aufzufinden. Wenn wir also irgendwann zum Beispiel wissen möchten, welches Wort auf der Karte mit der roten Zahl 425565 steht, müssen wir die Karte finden. Dazu nutzen wir wieder die Hashfunktion, kommen auf die Speicherposition 5 und können dort das Wort „absurd“ lesen. Wie ermittelt man nun aber eine sinnvolle Hashfunktion? Ein Kriterium dafür haben wir bisher bereits implizit angewendet. Vom Wertebereich der Hashfunktion ist die Größe des Speichers abhängig, der zur Verfügung gestellt werden muss: Die Hashfunktion „h (s) = letzte Ziffer von s“ kann Zahlen zwischen 0 und 9 her- vorbringen. Daher muss auch ein Speicherbereich mit zehn Positionen (#0 bis #9) reserviert werden. Für die Hashfunktion „h (s) = letzte drei Ziffern von s“ müsste ent- sprechend ein Speicherbereich von 1000 Positionen zur Verfügung stehen, denn drei Ziffern können Werte zwischen 000 und 999 annehmen. Natürlich müssen Sie dafür sorgen, dass der Werte- und damit der Speicherbereich groß genug ist, um alle Schlüssel aufzunehmen und zusätzlich großzügig Platz zu las- sen: Nur bei einem Belegungsfaktor unter 0,8 ist das Hashing effektiv. Wie erreicht man darüber hinaus, dass die Zahlen über den Speicherstellen möglichst gleich verteilt sind? Natürlich ist das von den jeweiligen Daten abhängig, die man erwartet. Die folgende Tabelle enthält drei unterschiedliche Sätze von Beispielschlüsseln. Versuchen Sie für jeden der Sätze eine günstige Hashfunktion für eine Speicher- größe von 100 Plätzen zu bestimmen. Kleiner Tipp: Wenn Sie darüber nachden- ken, wofür die Zahlen stehen könnten, wird die Auswahl leichter. Satz 1 Satz 2 Satz 3 19031980 3398776 8,99 21121979 3398777 1,98 09081981 3398778 5,89 06061981 3398779 7,98 14011980 3398780 4,00 29081981 6981154 9,79 11031981 6981155 2,19 17061980 6981156 4,98 ▶ ▶ ▶ ◀ ◀ ◀ 166 11. Ordnung im Chaos Fangen wir einmal mit Satz 2 an: Hierbei könnte es sich zum Beispiel um die Buchnummern von Neuveröffentlichungen eines Verlages handeln. Die einführenden Ziffern stehen dabei eventuell für das Fachgebiet und danach werden die Zahlen fort- laufend vergeben. Es scheint vernünftig, die letzten beiden Ziffern als Hashfunktion zu nutzen. Falls dann zufällig zwei Buchreihen die gleichen Endziffern haben, kommt es allerdings zu recht vielen Kollisionen. Dagegen lässt sich aber auch nicht sonderlich viel machen, selbst mit komplizierteren Hashfunktionen nicht. Satz 1 enthält Zahlen, die alle als Datum interpretiert werden könnten und so zum Beispiel die Geburtsdaten eines Abiturjahrgangs repräsentieren. Man sieht bereits, dass es ziemlich schwierig ist, einfach zwei Ziffern herauszuschneiden, die dann die Speicherstelle angeben: Die unterschiedlichen Jahreszahlen beschränken sich auf drei (wie das in einer Schulklasse meistens der Fall ist). Bei den Monaten hat man nur Zah- len zwischen 01 und 12, die Tage liegen zwischen 01 und 31. Würden wir aufgrund dieser Ziffern hashen, hätten wir nicht den gesamten Speicher ausgenutzt. Am ehesten käme man noch auf eine vernünftige Verteilung, wenn man die zweite und die vierte Ziffer zu einer neuen Zahl zusammensetzt, also die 1er-Stelle des Tags und des Monats. Allerdings ist dies auch keine besonders gute Lösung: Die Ziffern 1 und 2 kommen bei der 1er-Stelle des Monats doppelt so häufig vor wie alle anderen Ziffern – sie sind im Januar und Februar, aber auch im November und Dezember enthalten. Die gleiche Problematik zeigt sich auch bei Satz 3. Die Zahlen könnten zum Beispiel die verschiedenen möglichen Preise eines Einzelhandels darstellen. Da die Cent-Be- träge meistens auf 9 oder 8 enden, kann man hier ebenfalls schlecht eine Verteilung bilden. Allgemein gibt es offenbar ziemlich viele Fälle, in denen die Sortierschlüssel sehr stark von unserem Denken im Dezimalsystem geprägt sind: Bestimmte Ziffern stehen für bestimmte Funktionen (Jahreszahl, Mitgliedsnummer oder Ähnliches). Daher kommt es sehr oft zu Häufungen bestimmter Werte. Günstig wäre, mit der Hashfunktion gegen das Dezimalsystem zu steuern und damit gegen unsere menschlichen Gewohnheiten. Das Gleiche gilt für das binäre System, da viele Größen im Computer hiervon sehr abhängig sind. Betrachten wir die Di- visionsrestmethode: Verwendet man den Rest bei der Division durch 10, schneidet man quasi nur die letzte Stelle des Dezimalsystems ab, bei der Division durch 100 die letzten beiden Stellen usw. Genau das Gleiche gilt etwa für das binäre Zahlensystem, wenn Sie durch 2 teilen. Um bei der Divisionsrestmethode unabhängig von jeglichen Zahlensystemen zu werden, sollten Sie daher durch eine Primzahl teilen. Probieren Sie das doch gleich einmal mit den Daten von Satz 1 und Satz 3 aus (das feste Komma der Zahlen in Satz 3 können Sie dabei einfach ignorieren). Ordnen Sie die Zahlen nach den folgenden Hashfunktionen in den Speicher: h (s) = s mod 11 h (s) = s mod 103 ▶ ▶ ▶ ◀ ◀ ◀ Was steckt dahinter? 167  s s mod 11 s mod 103 19031980 0 52 21121979 10 78 09081981 7 59 06061981 2 19 14011980 2 44 29081981 5 34 11031981 4 63 17061980 1 30 899 8 75 198 0 95 589 6 74 798 6 77 400 4 91 979 0 52 219 10 13 498 3 86 Die Primzahlen sorgen hier für eine Entkopplung der Speicherpositionen von ihren dezimalen Abhängigkeiten. Selbst sehr ähnliche Schlüssel können komplett unter- schiedliche Hashwerte aufweisen. Selbstverständlich wird automatisch die Größe des verwendeten Speichers durch die Primzahl des Divisors bestimmt. Man tut durch das beschriebene Verfahren das Bestmögliche, um Häufungen zu ver- meiden, ausschließen kann man sie jedoch keinesfalls. So wird ein guter Hash nicht nur durch seine Hashfunktion, sondern auch durch die Kollisionsbehandlung be- stimmt. Im Beispiel mit dem Papierspeicher bestand diese einfach in der Regel: „Gehe so lange eine Position weiter, bis ein Speicherplatz frei wird.“ Um das formal auszu- drücken, erweitern wir die Hashfunktion. Diese heißt nun nicht mehr h (s), sondern h0 (s). Die 0 steht dabei für den 0. Versuch, den Schlüssel im Speicher unterzubringen. (Sie erinnern sich: Informatiker fangen gerne bei 0 an zu zählen...) Die Funktion zur Kollisionsbehandlung wird dann mit h1 (s), h2 (s), h3 (s) usw. be- zeichnet, wobei 1, 2, 3 für den 1., 2. und 3. Versuch stehen. Meistens möchte man eine einzige Funktion zur Kollisionsbehandlung haben und verwendet eine weitere Varia- ble für den Versuch: hi (s) steht für den i-ten Versuch. Auf diese Weise kann nachein- ander h0, h1, h2 usw. durchgeführt werden, bis man eine freie Stelle in der Hashtabelle findet. Nehmen wir etwa die oben bereits benutzte Hashfunktion (schon in neuer Schreib- weise): h0 (s) = s mod 103 Eine Kollisionsbehandlung, die einfach immer einen Platz weiter sucht, wäre dann: hi (s) = (h0 (s) + i) mod 103 168 11. Ordnung im Chaos Zu lesen einfach: „Für den i-ten Versuch, s unterzubringen, gehe vom Speicherplatz, den die Hashfunktion ausgesucht hat, i Plätze nach rechts. Fange nach dem Erreichen des Endes wieder von vorne an.“ Die Suche nach einer vernünftigen Kollisionsbehandlung ist noch schwerer als die Suche nach einer guten Hashfunktion. Die höchste Anforderung ist dabei, dass alle Plätze des Speichers irgendwann „gefunden“, also adressiert werden. Ansonsten könn- te es vorkommen, dass erst die Hälfte des Speichers gefüllt ist und ein Schlüssel trotz- dem nicht eingeordnet wird, weil die schlechte Kollisionsbehandlung genau die freien Stellen gar nicht adressiert. Mit der einfachen Kollisionsbehandlung „Gehe immer eine feste Anzahl von Speicher- positionen nach links oder rechts“ erfüllt man diese Bedingung im Regelfall. Leider kann das aber zu anderen Problemen führen: Kommt es doch einmal zu Häufungen bei der Hashfunktion, werden die Kollisionen auch immer wieder auf den gleichen Speicherstellen stattfinden. Daher wäre es besser, auch die Kollisionsbehandlung vom Schlüssel abhängig zu machen. Hier ist es jedoch äußerst schwierig, eine Funktion zu finden, die zusätzlich alle Speicherplätze erreicht. In der Praxis verwendet man tatsächlich fast ausschließlich sehr einfache Hashfunk- tionen nach der Divisionsrestmethode mit gleichfalls einfachen Kollisionsbehandlun- gen. Im Experiment haben wir ja auch gesehen, dass diese im Allgemeinen sehr gut funktionieren. Ordnung im Chaos! Um auf die Frage vom Anfang dieses Kapitels zurückzukommen: Was ist denn nun besser – Ordnung oder Chaos? Ich denke, dieses Kapitel hat gezeigt, dass Ordnung ein sehr gutes Mittel ist, effektiv und schnell auf Daten zuzugreifen und sie damit auch effektiv und schnell verarbeiten zu können. Allerdings hat es ebenfalls gezeigt, dass so manche Anordnung, die auf den ersten Blick wie ein Chaos aussieht, letztlich sehr geordnet sein kann – dem Betrachter fehlt lediglich der Zugang in Form einer mehr oder weniger komplexen Hashfunktion. Das gilt meiner Meinung nach für Daten im Computerspeicher ebenso wie für den Büro- schreibtisch: Oft ist der Besitzer eines scheinbar chaotischen Papiergrabs in der Lage, ein gewünschtes Dokument in Sekundenbruchteilen zwischen den Schichten hervor- zuzaubern – das Hashing funktioniert. Schwierig wird es mit diesem Verfahren, wenn viele Menschen zusammen arbeiten und auf den gleichen Datenbestand zugreifen. Meistens gelingt es in der wirklichen Welt nicht, die Hashfunktion für einen Schreibtisch auch anderen zu vermitteln – hier hilft nur traditionelles Sortieren und Ablegen. Im Computer ist das dagegen kein Pro- blem: Es können auch mehrere Prozesse auf einen gehashten Speicherinhalt zugreifen – sie müssen lediglich die gleiche Hashfunktion benutzen. Die Frage ist also weniger, ob Ordnung oder Chaos besser ist, sondern für jede An- wendung – im Computer wie im Alltag – muss betrachtet werden, welche Art der Ordnung sinnvoll und nützlich ist. Manchmal wirkt es dabei ordentlich, manchmal eher unordentlich – aber eigentlich kommt man immer auf eine Ordnung! Bleibt noch die Frage, welche Anwendungen es für Hashing im Computer gibt. Im Prinzip ist es überall gut einzusetzen, wo man Daten sehr schnell ablegen und wieder Ordnung im Chaos! 169  hervorholen muss. Das ist etwa bei Datenbanken der Fall – denken Sie an elektroni- sche Wörterbücher, bei denen ein bestimmtes Wort sehr schnell gefunden werden soll. Hashing wird auch in Betriebssystemen gebraucht, um den verfügbaren Hauptspei- cher zu verwalten und einem Programm, das Speicher anfordert, schnell freien Platz zuzuweisen. Auch in Echtzeitsystemen können bestimmte Formen des Hashings verwendet wer- den. Echtzeitsysteme sind Anwendungen, bei denen es darauf ankommt, in einer be- stimmten, definierten Zeit eine Entscheidung zu treffen. Beispiel dafür ist ein Fließ- band, auf dem Produkte zur Qualitätskontrolle an Sensoren vorbeilaufen. Innerhalb von Sekundenbruchteilen muss ein Computer anhand der Messdaten entscheiden, ob er das Produkt mit einem Luftstrahl vom Band befördert oder nicht. Hier können Hashverfahren helfen, die darauf getrimmt sind, eine minimale Zugriffszeit zu garan- tieren, indem ihr Algorithmus dafür sorgt, dass es nicht mehr als zum Beispiel zwei Kollisionen hintereinander gibt. Zufällig Am Ende dieses Kapitels möchte ich noch kurz auf ein Thema eingehen, das eng mit dem Hashing verwandt ist, auch wenn dies auf den ersten Blick nicht so scheint: die Erzeugung von Zufallszahlen. Zufällige Ereignisse im Computer assoziieren wir normalerweise eher mit Computer- spielen, in denen der Benutzer immer wieder mit für ihn nicht vorhersehbaren Ereig- nissen konfrontiert wird. Eine andere Zufallskomponente ist eher unerwünschter Na- tur: die Zeit, die zwischen Systemabstürzen oder Programmfehlern vergeht (trotzdem werden in England Wetten darauf abgeschlossen). Dass man Zufallszahlen auch nutzen kann, um ganz konkrete Berechnungen an- zustellen, soll das folgende Experiment zeigen. Die berühmte Zahl π kann man mit komplizierten mathematischen Reihenentwicklungen bestimmen oder man kann sie anhand ihrer geometrischen Definition ermitteln. Abbildung 11.8 zeigt einen Kreis mit dem Radius 1. Dieser hat laut Definition einen Flächeninhalt von π, in jedem Quadranten also π/4. Ein solcher Quadrant ist noch- mals sehr groß in Abbildung 11.9 dargestellt. Dieser ist in kleine Quadrate eingeteilt, mit deren Hilfe wir einen Schätzwert für die belegte Fläche auszählen können. Der Flächeninhalt F entspricht näherungsweise der Anzahl der Kästchen mit Mittelpunkt im blauen Bereich, geteilt durch die gesamte Anzahl Kästchen. Abbildung 11.8 Der Kreis mit Radius 1 hat den Flächeninhalt π. 1 1 1 170 11. Ordnung im Chaos 6 6 Abbildung 11.9 6 5 Ein Viertel des Kreises mit 6 4 Würfelwerten in Zeilen und 6 3 Spalten 6 2 6 1 5 6 5 5 5 4 5 3 5 2 5 1 4 6 4 5 4 4 4 3 4 2 4 1 3 6 3 5 3 4 3 3 3 2 3 1 2 6 2 5 2 4 2 3 2 2 2 1 1 6 1 5 1 4 1 3 1 2 1 1 1 1 1 1 1 1 2 2 2 2 2 2 3 3 3 3 3 3 4 4 4 4 4 4 5 5 5 5 5 5 6 6 6 6 6 6 1 2 3 4 5 6 1 2 3 4 5 6 1 2 3 4 5 6 1 2 3 4 5 6 1 2 3 4 5 6 1 2 3 4 5 6 Wenn wir alle Kästchen durchgehen, das sind genau 362 = 1296 Stück, kommen wir auf 1018 mit Mittelpunkt im blauen Bereich (bei einigen muss man sehr genau hin- schauen, wo sich der Mittelpunkt befindet). Unsere Berechnung für π ergibt also: 1018 π = F ⋅4 ≈ ⋅ 4 ≈ 3,1420 1296 Das ist bereits ein ziemlich guter Näherungswert für die Zahl π – das „echte“ π ist auf fünf Stellen genau 3,1416. Um diesen guten Wert zu erhalten, mussten jedoch 1296 Kästchen ausgezählt werden. Mit deutlich weniger Zählen kommen Sie aus, wenn Sie nicht jedes Kästchen betrach- ten, sondern nur solche, die Sie per Würfel zufällig bestimmt haben. Hierzu benötigen Sie zwei unterschiedliche, sechsseitige Würfel, zum Beispiel einen schwarzen und ei- nen beigen. Um ein Kästchen zu bestimmen, würfeln Sie zunächst für die Zeile und dann für die Spalte. Falls der Mittelpunkt im blauen Bereich liegt, vermerken Sie eine 1, sonst eine 0. Wenn Sie 50 Kästchen ausgezählt haben, ziehen Sie eine Zwischenbi- lanz. Setzen Sie die Zahl der Einsen und die Gesamtzahl der Würfe in die Formel oben ein. Haben Sie zum Beispiel 40 Einsen erwürfelt, ergibt das für die Fläche einen Nähe- 40 rungswert von π = F ⋅ 4 ≈ ⋅ 4 ≈ 3, 2 Das ist für π auch schon recht ordentlich! 50 Zufällig 171  Jetzt wenden Sie sicherlich ein, dass es deutlich mehr Aufwand bedeutet, 50 Kästchen auszuwürfeln, als schnell alle Kästchen durchzuzählen. Nicht so für einen Computer – der bestimmt die nötigen Zufallszahlen im Handumdrehen. Tatsächlich wirkt sich das besonders bei Anwendungen mit sehr vielen Dimensionen aus. Beim Bestimmen des Volumens einer Kugel zeigt sich der Effekt also noch besser als bei der Kreisfläche. Noch prägnanter wird die Sache, wenn wir den Rauminhalt einer sogenannten „Hy- persphäre“ mit 100 Dimensionen berechnen – hier liefert Würfeln deutlich genauere Ergebnisse als das gleichmäßige Auszählen einer entsprechenden Zahl an Stichpro- ben. Sie fragen sich wahrscheinlich, wozu man so etwas überhaupt berechnen möchte. Zu Recht! Selbstverständlich ist das – genau wie die Bestimmung von π oben – ein rein akademisches Beispiel. Denken Sie aber etwa an die Entwicklung einer neuen Fahr- zeugkarosserie, bei der 100 verschiedene Werte computergestützt fein justiert und optimiert werden müssen. Keine Maschine der Welt ist in der Lage, alle möglichen Kombinationen durchzuprobieren. Durch die Verwendung von Zufallszahlen kann man sich aber schnell dem optimalen Ergebnis annähern. Voraussetzung für das Gelingen des Experiments oben sind Würfel, die tatsächlich zufällige Ergebnisse produzieren und nicht etwa durch Herstellungsfehler eine Zahl häufiger zeigen als eine andere. Auch sehr gut müssen die „Computer-Würfel“ sein, genannt Zufallszahlengeneratoren, besser noch Pseudozufallszahlengeneratoren, denn eines können Computer im Normalfall tatsächlich nicht liefern: Zufallszahlen! Woran liegt das? Computer sind Maschinen, deren Hauptzweck darin besteht, Abläufe immer und im- mer wieder so zu wiederholen, wie sie einmal von den Programmierern vorgegeben wurden. Hier wäre es fatal, wenn der gleiche Algorithmus mit den gleichen Eingabe- werten zu unterschiedlichen Zeiten unterschiedliche Ergebnisse hervorbrächte. Com- puter sind daher in dieser Hinsicht sehr zuverlässig! Zufall bedarf jedoch eines anderes Konzeptes! Zufall ist sozusagen kultivierte Unzu- verlässigkeit, und das widerspricht dem braven Computer. Das haben wir bereits beim Hashen gesehen, wo ja auch kein echtes Chaos zustande kommt, sondern nur eine ganz besondere Ordnung. Aus diesem Grund simulieren Computer den Zufall nur – sie müssen alle Zufallszah- len berechnen und weil diese dann lediglich zufällig aussehen, nennt man sie Pseu- dozufallszahlen. Um dieses sehr lange Wort zu vermeiden, werde ich im Folgenden allerdings überwiegend einfach weiter von Zufallszahlen reden. Im Normalfall werden solche Pseudozufallszahlen rekursiv bestimmt: Man fängt mit einer festen Zahl als „Zufallszahl 0“ an und berechnet jeweils die folgende Zufallszahl anhand einer Funktion aus der letzten Zufallszahl. Sehr einfach wäre zum Beispiel eine Funktion wie: Z (i) = (Z (i − 1) + 5) mod 11 Die resultierende Zufallszahlenfolge mit „1“ als Zufallszahl 0 wäre dann 1, 6, 0, 5, 10, 4, 9, 3, 8,... Auf den ersten Blick sieht das bereits zufällig aus, aber bei genauerem Hinsehen fällt dann der Summand 5 sehr deutlich auf, wenn man aufeinanderfolgende Zahlen be- trachtet. 172 11. Ordnung im Chaos Die folgende Zahlenreihe wurde nach einem sehr einfachen und in den 1980er-Jahren sehr häufig eingesetzten Verfahren berechnet. John von Neumann hat es bereits 1949 vorgestellt. Als Startwert habe ich 42 genommen. 42 - 76 - 77 - 92 - 46 - 11 - 12 - 14 - 19 - 36 - 29 - 84 - 5 - 2 Kommen Sie auf die Berechnungsvorschrift? ▶ ▶ ▶ ◀ ◀ ◀ Es handelt sich um den sogenannten „Mid-Square-Generator“: Man nehme die Zahl, quadriere sie (multipliziere sie mit sich selbst) und benutze die mittleren Ziffern als neue Zahl. Beispiel: 42 ∙ 42 = 1764. Die mittleren Ziffern sind 76, das ist die nächste Zufallszahl. Echt zufällig Dieser Generator ist jedoch in der Praxis nicht besonders gut geeignet. Um das ex- In einigen Anwendungen perimentell zu belegen, berechnen Sie bitte die entsprechende Zufallszahlenfolge reichen Pseudozufallszahlen mit 24 als Startwert. nicht aus. Denken Sie zum Beispiel an die Liste von Transaktionsnummern, die Sie ▶ ▶ ▶ ◀ ◀ ◀ von Ihrer Bank bekommen. Kommt diese aus einem Pseu- dozufallszahlengenerator und Es ergibt sich eine sehr kurze Folge 24 - 57 - 24 - 57 usw. Prinzipiell kommen also nur bekommt jemand die Funkti- zwei Zahlen abwechselnd heraus. Auch mit vielen anderen Startwerten kommt man onsweise heraus, kann er aus jeweils auf sehr kurze Folgen. einer Handvoll Eingaben alle weiteren geheimen Zahlen Für ein computergestütztes Roulette-Spiel wäre dieser Generator daher sicherlich selbst ausrechnen. Für solche Anwendungen nicht geeignet, denn es würden immer nur einige Zahlen erscheinen und andere gar sollte man daher auf „echte“, nicht. Eine wichtige Anforderung an einen Zufallszahlengenerator ist also, dass er ir- also physikalische Zufallszah- gendwann einmal alle möglichen Zahlen hervorbringt! Auch im Beispiel der π-Be- lengeneratoren zurückgrei- rechnung von oben wäre das Ergebnis nicht akkurat, wenn bestimmte Zeilen oder fen. Die schnellsten nutzen quantenphysikalische Vorgän- Spalten ganz ausgespart würden, weil die virtuellen Würfel die entsprechenden Zah- ge aus. len nie zeigten. Das alles erinnert sehr stark an die Forderungen beim Hashing: Auch dort sollte mög- lichst der gesamte Speicher ausgenutzt werden, Die entsprechende Hashfunktion, die alle Adressen der Tabelle anspricht, war sehr einfach: h(s) = s mod m Diese Funktion als Zufallszahlengenerator würde direkt noch keine gute Folge erge- ben, wie wir an folgendem Beispiel sehen: Z (i) = Z (i −1) mod 40 Hier kommt immer wieder die Zahl heraus, die man als Startwert festlegt – probieren Sie es selbst einmal aus! Zufällig 173  Wir benötigen noch etwas, das diesen Startwert verändert. Daher multiplizieren wir ihn mit einem festen Faktor und addieren dann noch etwas dazu: Z (i) = (Z (i − 1) ⋅ 21 + 17) mod 40 Mit 1 als Startwert erhalten wir: 1 - 38 - 15 - 12 - 29 - 26 - 3 - 0 - 17 - 14 - 31 - 28 - 5 - 2 - 19 - 16 - 33 - 30 - 7 - 4 - 21 - 18 - 35 - 32 - 9 - 6 - 23 - 20 - 37 - 34 - 11 - 8 - 25 - 22 - 39 - 36 - 13 - 10 - 27 - 24 - 1 Der Generator liefert also alle 40 Möglichkeiten, bevor er von Neuem mit der gleichen Zahl anfängt. Die resultierende Zahlenfolge sieht außerdem trotz der einfachen Be- rechnungsvorschrift sehr zufällig aus. Es gibt einfache mathematische Regeln, um bei einem solchen sogenannten „linearen Kongruenzgenerator“ die Werte so zu setzen, dass tatsächlich alle möglichen Zahlen durchlaufen werden. Sie benötigen gar keine Zufallszahl zwischen 0 und 39, sondern nur eine zwischen 0 und 9? Gar kein Problem: Nehmen Sie einfach nur die hinterste Ziffer. Auf diese Weise entstehen aus den großen Zufallszahlen, die von den Standardgeneratoren der Computer erzeugt werden, die kleineren Zufallszahlen, die man für eine Anwendung benötigt – etwa für ein Spiel mit einem Würfel. Die meisten der „eingebauten“ Ge- neratoren arbeiten mit Zahlen zwischen 0 und 18.446.744.073.709.551.615 (über 18 John von Neumann (1903– Trilliarden). Hier dauert es also eine Weile, bis der Zyklus von Neuem beginnt. 1957) hat sich als Mathema- tiker sehr früh mit grundle- Vielleicht fragen Sie nun, wie es kommt, dass im bevorzugten Skatprogramm doch genden Fragen der Informatik nach jedem Start eine unterschiedliche Hand ausgeteilt wird, das Computer-Schach- beschäftigt. Unter anderem gilt er als Schöpfer des hier spiel meistens einen anderen Eröffnungszug vollzieht. Das passt doch nicht zusammen erwähnten, in der Praxis mit dem beschriebenen, vorbestimmten Zufall. Und Sie haben recht! Der Computer nicht besonders brauchbaren verwendet zur ersten Initialisierung seines Zufallszahlengenerators eine „echte“ Zu- Mid-Square-Generators. fallszahl. Meistens nimmt er hierfür die Zeit, die seit dem Einschalten des Computers Seine bedeutenden Beiträ- ge zur Informatik sind die vergangen ist, in Millisekunden oder sogar Mikrosekunden. Da diese Zeit maßgeblich Formulierung der von-Neu- nicht von der Technik bestimmt wird, sondern vom Bediener, ist sie mit einer starken mann-Architektur, die Zufallskomponente behaftet – je nachdem, ob Sie sich vor dem Start des Spiels noch prinzipiell noch heute den am Kopf gekratzt haben und wie lange dies gedauert hat, wird der Zufallszahlengene- prinzipiellen Aufbau aller Computer beschreibt. Damit rator anders initialisiert. verbunden ist der Begriff des Warum generiert der Computer danach in der Regel nur noch Pseudozufallszah- „von-Neumann-Flaschenhals“, der beschreibt, dass alle Kom- len, statt echter Zufallszahlen auf Zeit-Basis? Sobald das Spiel gestartet wurde und ponenten eines Computers der Benutzer nicht eingreift, benötigt der Computer normalerweise immer die glei- Daten austauschen müssen che Zeitspanne für die gleichen Programmteile – Sie erinnern sich: Computer sind und die dafür genutzte sehr verlässliche Maschinen. Auf diese Weise ist etwa beim Skatprogramm die Zeit Schnittstelle, der sogenannte „Bus“ eine kritische Engstelle zwischen dem Austeilen der ersten und der zweiten Karte sehr genau definiert. Hier – den Flaschenhals – darstellt. liefern daher die Pseudozufallszahlengeneratoren wesentlich bessere und „scheinbar Einer der wichtigsten Preise zufälligere“ Ergebnisse. für Errungenschaften in der Informatik ist die Sie sehen: Selbst bei einem Thema, das eigentlich per Definition chaotisch sein sollte, John-von-Neumann-Medaille. nämlich Zufallszahlen, bleibt der Computer ordentlich und nachvollziehbar. Das Cha- os ist auch hier – genau wie beim Hashing – lediglich ein Pseudo-Chaos... Viel weiter möchte ich hier in die Thematik auch gar nicht einsteigen. Interessierte können unter den Stichworten „Hashing“ und „Pseudozufallszahlen“ oder „linearer Kongruenzgenerator“ selbst recherchieren. 174 11. Ordnung im Chaos Resümee Die Ausgangsfrage für dieses Kapitel „Ordnung oder Chaos“ konnte – zumindest im Sinne der Informatik – ganz eindeutig für die Ordnung beantwortet werden! Aller- dings hat der Leser nun auch jedes Recht, das scheinbare Chaos auf seinem Schreib- tisch einfach als Ordnung zu deklarieren – genau wie in modernen Computern scheinbar chaotisch angeordnete Daten als Hashtabelle eine der schnellsten Zugriffs- methoden darstellen und genau wie scheinbar chaotische Zufallszahlen eigentlich doch auf ganz ordentliche Weise entstehen... Sie konnten auch nachvollziehen, dass Informatik nicht immer nur eine Wissenschaft ist, die ihre Methoden durch konstruktive Herangehensweisen bildet. In einigen Fällen muss auch hier empirisch gearbeitet werden. Im Klartext heißt das Ausprobieren! So bleibt neben allen formalen Kriterien für die Formulierung einer guten Hashfunktion oder eines guten Pseudozufallszahlengenerators als letzte Sicherheit nur das Testen. Resümee 175