Video 9-3: Elementare Symbol Tables

0:03 werden ein paar Beispielanwendung gesehen, wie man diese Symbol Tables verwenden kann. Gibt's noch viel viel mehr. Äh jetzt wollen wir auch mal sehen, wie wir die realisieren können. Und bevor wir uns auf das eigentliche Thema von diesem Abschnitt stürzen, ein paar ganz einfache Versuche, bevor wir ähm weitermachen. Vielleicht kommen wir ja mit einfachen Ideen aus, die wir schon kennen. Was hatten wir äh auswendig gelernt? äh verkettete Listen, lineare Listen. Versuchen wir also erstmal eine verkettete lineare Liste. Jetzt ist ähm bei so einer Liste muss ich mich entscheiden, in welcher Reihenfolge hätte ich denn gerne diese Schlüssel da aufgelistet oder Schlüsselwertpare.

0:42 Hier jede dieser Boxen heißt ja, dass dieser Schlüssel S ist jetzt dem Wert null assoziiert. Und die erste Option ist, wir machen das einfach äh in unsortierter Reihenfolge. So wie die Updates kommen, hänge ich die an die Liste vorne an. Also hier kommt zuerst dieses put S0 packe ich in meine verkehrte Liste vorne dran. Dann kommt E1 packe ich meine Liste vorne dran. Da kommen noch ein paar Put Aufrufe. Wenn ich an irgendeiner Stelle einen Wert auslesen möchte, dann fange ich am Anfang der Liste an und suche ein Element nach der anderen durch, bis ich eins finde, wo der Schlüssel gleich den Wert ist, den ich haben möchte. Das funktioniert sogar, wenn ich mehrmals put aufrufe mit dem gleichen Schlüssel. Dann habe ich zwar mehrere Einträge hier, so wie hier in dem Beispiel mit dem A. Da gibt's da hinten einen Eintrag. ähm der aber schon hier überschrieben wird. Also ich ich laufe ähm an der Stelle machen sie schon die Variante, dass man dass man den Wert überschreibt.

1:58 Die andere Option wäre, man hängt den neuen Wert einfach vorne an, dann würde das Get immer noch funktionieren, aber die Liste wird länger und länger und äh ich habe den Platz hinten verschwendet. Äh, beides geht, beides ist auch ähm ähnlich schlecht, denn wenn Sie sich überlegen, was da passiert, um in der Liste zu suchen, muss ich im schlimmsten Fall die ganze Liste durchlaufen. Vielleicht war der allererste Putaufruf, der den ich jetzt suche. Und Insert, so wie Sie es implementieren, hat auch diese diese Laufzeit, weil ich suche, ob es schon einen Eintrag für diesen Schlüssel gibt. Wenn Sie die andere Variante wählen, dass wir einfach vorne dran hängen, dann ist zwar Insert Konstantzeit, aber Search ist nicht mal mehr nur durch n beschränkt, sondern durch die Anzahl aller Updates überhaupt, also noch schlechter bei der Suche. Und selbst im im Average Case ist das nicht wirklich besser. Ähm im Schnitt muss ich die halbe Liste durchlaufen.

2:54 Wenn Sie das so implementieren und für diese Millionen Wortliste aufrufen, dann warten wir nächstes Jahr noch. Also eine unsortierte Liste ähm kann man eventuell so machen, dass äh put effizient ist.

3:21 Das ist schon die etwas äh optimistischere Variante, aber GET ist in jedem Fall äh langsam, das funktioniert nicht. Andere Idee, warum halten wir die ähm Schlüssel nicht in sortierter Reihenfolge vor, wenn sie ja eh geordnet sind? Das ist aber noch schlimmer, denn die Sortierung hilft mir gar nichts. Wenn ich das als verkettete Liste speichere, kann ich mit der Sortierung gar nichts anfangen, denn ich komme an die Elemente nicht ran. Ich kann nur vom Anfang durchs durchlaufen. Sein sich verkettete Liste hat nur vorwärts, hat nur Nachfolgerzeiger. Das heißt, jetzt sind beide Operationen langsam. Und ich habe eigentlich gar nichts gewonnen. Ist ja ärgerlich. Also es scheint als würde das Sortieren hier überhaupt nicht helfen. Das ist aber seltsam. Ich habe ihn noch sortieren als was praktisches verkauft. Äh, der Grund ist natürlich, dass wir mit der verketteten Liste kein Random Access haben. Das heißt, wir können keine binäre Suche machen. Wenn wir die ähm Schlüsselwertpare in einem Array speichern, dann können wir zumindest die Suche beschleunigen.

4:26 Und ähm hier ist noch mal ein bisschen ähm genauer erklärt, wie binäre Suche funktioniert. Ich kann damit auch die Frage stellen, äh wie viele Schlüssel sind echt sind kleiner als ein bestimmter Wert? ähm hatten wir im Prinzip schon besprochen, möchte ich nicht noch mal im Detail machen. Da ist der der Java Code. Wir hatten damals auf jeden Fall so Pseudo Code auch gehabt für.

4:55 Damit kann ich also eine dritte Version von einem einfachen von einfachen Symbolle Table implementieren. Ich halte meine Schlüssel in einem Array in sortier Reihenfolge vor.

5:05 Ähm, wo könnte da das Problem sein? Na ja, das Einfügen ist jetzt eben langsam, denn wenn ich jetzt neuen Wert einfügen möchte, dann muss ich ähm alle Werte, die die rechts davon stehen, also gerade hier äh z.B. Für das Einfügen von L muss ich all diese diese Werte hier eine Position weiter nach rechts verschieben. Und das ist im Breastcase natürlich auch wieder linear. Wenn ich einen neuen Schlüssel einfüge, der ganz nach vorne kommt, dann schiebe ich die ganze Liste um eine Position nach rechts. Also jetzt habe ich zwar die Suche beschleunigt, aber das Einfügen ist immer noch Linearzeit äh oder wiederlinearzeit. Das heißt, damit können wir immer noch nicht wirklich arbeiten. Und das sieht irgendwie so aus. Ähm ja, hier sind noch die ähm die sortierten ob die Operation von sortierten Symbol Tables, die wir bisher, ich hatte jetzt nicht genau gezeigt, wie die funktionieren. Ähm hier nur der Kürze, man kann viele von denen auch mittels binärer Suche lösen, insbesondere äh, wenn ich die benachbarten Werte im Dictionary finde. Florence Ceiling war ja, ich suche nicht genau einen Wert, sondern ich bin interessiert an, was ist so der nächste Wert, größer oder kleiner von dem Schlüssel, den ich abfrage. Das kann ich auch mit binärer Suche machen.

6:33 Binere Suche findet in dem Fall die Position, wo das Element stünde, wenn es denn in der Liste wäre und dann kann ich eben ein eine Position nach oben oder unten laufen. Äh, das heißt, die Operationen sind eigentlich alle ganz ordentlich gelöst, aber ich habe eben Insert als Bottleneck und damit ist das ganze Ding unbrauchbar, wenn ich es nicht sinnvoll einfügen kann. Es ist keine Sympable, mit der ich arbeiten kann.

7:02 Also, ich bin mit Absicht relativ schnell darrüber gehuscht, weil es dann nicht besonders viel zu sehen gibt. Äh, wenn Sie das noch mal ein bisschen im Detail nachlesen wollen, gerade auch die sortierten Operationen mit binärer Suche finden Sie die in dem im Setrick und Wayne Buch ein bisschen detaillierter aufgeschlüsselt.

7:19 Wir haben scheinbar bei diesen ganzen Implementierung einen inherenten Widerspruch ist vielleicht fast schon zu krass, aber so ein Tradeoff ähm dass wir um schnell suchen zu können eigentlich was sortiertes haben möchten, weil binäre Suche ist exponentiell schneller als dieses linear durchlaufen. Das wollen wir unbedingt. Alles andere ist ist nicht skaliert nicht wirklich. Umgekehrt, um schnell einfügen zu können, können wir uns diese Sortierung nicht erlauben oder insbesondere nicht in dem in dem Array, wo wir Random Access haben. Das heißt, es scheint irgendwie nicht zu klappen, dass wir beides auf einmal bekommen.

7:57 Das möchte ich als Motivation nehmen, um einen kleinen Ausflug zu machen in einen Spezialfall von diesen von diesen sortierten Symbolle Tables, indem es ein bisschen einfacher ist, deutlich Fortschritte zu machen. Ne.