Video 9-1: (Ordered) Symbol Tables

0:01 Im nächsten großen Abschnitt schauen wir uns sortierte Wörterbücher und Suchbäume an. Die nächste die nächste große Datenstruktur oder nächste große abstrakte Datentyp ähm der fast noch wichtiger ist als die linearen Listen in der Praxis. Eine lange Liste von Dingen ähm gehen wir Schritt für Schritt durch. Für den Moment äh möchte ich Ihnen einfach nur den abstrakten Datentyp vorstellen und der hat, weil er so weit verbreitet ist, so viel verwendet wird, äh eine Vielzahl von Namen, die aber eigentlich alle das gleiche meinen. Ich werde mich hier von der Namensgebung an Symboltabelle Symbol Table halten, denn ähm die Folien sind in großen Teilen von dem Ctrick Wayne Buch übernommen, weil die Animationen oder die die Bilder in dem Teil so schön gemacht sind, das äh macht wenig Sinn, dass ich die einfach nachmale. Deswegen übernehme ich da die Folien und dann auch den Begriff, den Sie dort verwenden. Symbolle Table ist so ein bisschen äh die Bezeichnung, die diese Dinger ursprünglich in Compilern haben. Da ist das Problem sozusagen variablen Namen zu mappen. Ähm, sie heißen aber auch Dictionary. In Python heißt es tatsächlich dann dickt. Dieser feste eingebaute Datentyp. In Java würde dem Map am ersten entsprechen. Manchmal heißen sie auch assoziative Arrays oder Key Value Stores, wenn sie eher Richtung Datenbank denken. Was ist das? Ich habe Schlüssel und Werte und im wesentlichen speichere ich eine Menge von solchen Assoziationen von einem Schlüssel zu einem Wert.

1:34 Dann kann ich solche ähm das ist die die Syntax von von Map. Ich kann eine solche Beziehung einfügen. Also ich kann zu diesem Schlüssel K, zu dem Key K den Wert V assoziieren. Sprich äh in Python würde man das einfach so hinschreiben, als wäre das ein Array. In Java würde der Aufruf bei Map dann wirklich put heißen.

1:58 Get gibt mir das gespeicherte Mapping für einen bestimmten Key zurück, wenn der gespeichert ist. und ich kann prüfen oder löschen, ähm wie man sich das so vorstellen kann. Äh ohne Übertreibung wahrscheinlich der wichtigste Baustein in der Informatik, weil das so unfassbar flexibel ist und wir werden auch sehen, relativ effizient zu implementieren. Nicht ganz so toll wie die linearen Listen für den allgemeinen Fall, aber fast. Und dementsprechend liefert auch quasi jede Programmiersprache, die irgendjemand ernsthaft verwendet, eine Implementierung von Symboltabellen mit.

2:40 Von der Beschreibung, wie ich auch sagte, assoziiert zu Schlüsseln einen Wert, äh gibt's durchaus Ähnlichkeiten zu mathematischen Funktionen. Oberflächlich ähm partielle mathematische Funktionen, weil nicht alle Schlüssel einen Wert haben müssen. Oberflächlich sehr ähnlich. Der wichtige Unterschied, den Sie im Kopf halten müssen, ist, dass eine Funktion im mathematischen Sinn ein Wert ist, den man nicht verändern kann. Wenn ich äh den Wert an einer Bestelle verändere, dann ist es eine neue Funktion. Ähm, das ist die Sichtweise, wie man die üblicherweise hinter dem steckt, wie man auch über mathematisch über solche Objekte redet. Da ist eine Funktion auch nichts anderes als eine Zahl oder eine Menge. Es ist halt einfach eine eine an andere ein anderes Konstrukt auf diesen anderen aufbauend, aber eben statisch.

3:32 Und in der Informatik, wie so oft bei Datenstrukturen, wird's erst richtig interessant, wenn diese diese Zuordnung von Schlüsseln zu Werten dynamisch ist. Sehen Sie auch an den Operationen, ja, Put ändert ja den Wert, Delete. Offensichtlich einfach die beiden Dinger auseinanderhalten. Ansonsten haben die natürlich äh Ähnlichkeit, was vielleicht auch noch mal unterstreicht. Funktionen sind so das das Standardding in der Mathematik, um alles auszudrücken neben Mengen und entsprechend sind Symbol Tables das in der Informatik. In Java gibt's äh hier aus den äh aus der ähm Zwrick Wayli Bibliothek diesen ganz kompakten, das Interface ST für Symbol Table, weil sie es wohl so oft getippt haben, dass sie es nicht mehr ausschreiben wollten. Map in der Java Bibliothek ist ja auch nicht viel länger. Hat also genau diese Operation, die man erwarten würde. Es ist ein generischer Typ mit zwei Typametern für die Schlüssel und für die Werte. Ich kann so ein Wert einfügen. Es sind identisch die äh Operationen, die auf der Folie davor waren. Ähm an der Stelle das gleiche reicht uns erstmal für den Moment.

4:46 Das ist die Basisversion von der Symbol Table oder von dem Dictionary. Wir werden für dieses Kapitel uns aber mit einem einem einem erweiterten Interface auseinandersetzen, nämlich den geordneten Symbol Tables, Ordered Symbol Tables, sortierten Dictionaries, auch da wieder viele Namen. Äh was dahinter steckt, ist, dass es auf den Schlüsseln für diesen ähm erweiterten Fall eine sortierte Reihenfolge geben soll. Das heißt, ich kann bezüglich der Schlüssel von dem kleinsten oder größten aktuell gespeicherten sprechen oder ich kann auch Floor und Seiling berechnen. Die Namen sind ähm deshalb so gewählt, weil das dann dementspricht was passieren würde, wenn die Datenstruktur alle ganzen Zahlen speichert und das Argument hier irgendeine reelle Zahl ist. Also floor gibt mir den größten Schlüssel, der in der Symbolle Table gespeichert ist, der nicht größer ist als das Argument, mit dem ich das aufrufe. Und das ist auch, was die Floor Funktion auf den reellen Zahlen macht, nicht? W ähm ceiling symmetrisch äh Rank und Select sind dann noch mal spannend.

5:52 Rank sagt mir einfach für einen Wert, wie viele in der Datenstruktur sind kleiner, wie viele Schlüssel in der Symbolle Table sind kleiner und Select gibt mir den I kleinsten. Und wir werden sehen, dass äh diese beiden Operationen, die wirken vielleicht erstmal ein bisschen befremdlich oder auch weniger praktisch.

6:12 Äh mit denen kann man aber ganz coole Sachen machen, äh nur als Vorgiefer einzusteigen in den 0 Minuten, den wir verbleiben. Äh wenn wir diese ordered Symle Tables verwenden, dann gehen wir immer davon aus, dass die Keys entweder comparable sind, sie erinnern sich an das Sortierkapitel gleiches Spiel oder ich muss irgendwie im Konstruktor ein Comparator übergeben, der mir sagt, wie ich Schlüssel vergleichen kann. Ansonsten kann ich ähm diese diese Sortierung nicht irgendwie greifen.

6:46 Auch hier ähm das passende Java Interface dazu. Ähm einer der wenigen Kritikpunkte an den Designentscheidungen aus dem Buch, dass sie hier auch einfach Symbolle Table genommen haben. Das heißt, es gibt es gibt da keine che Unterscheidung in den Interfaces zwischen Symbolle Table mit diesen ganzen sortierten Operation und den anderen. Äh, sie können es nur hier dran ablesen, dass hier hier steht, die Keys sollen bitte comparable sein. Diese äh Ausdrucksform in Generics ist ein bisschen sperrig, aber heißt einfach Key ist ein Subtyp von comparable. Und hier haben Sie die ganzen Operationen von oben im Wesentlichen auch identisch. Es gibt noch hier diese Löschoperation.

7:36 Ansonsten genau was wir eben besprochen hatten, das wird das Ziel sein, also Datenstrukturen, die dieses große Interface implementieren, all diese Operation plus die von davor und so eine dynamische mathematische Funktion und dynamisches Mapping realisieren.