EIG: Abstrakter Datentyp Wörterbuch
Harald Selke
https://www.youtube.com/watch?v=mPXi6uTv3og

Transkript (automatisch erstellt)

0:00 willkommen zur Einführung in die Informatik für Geisteswissenschaftler dieses Video ist entstanden im Rahmen der gleichnahigen Veranstaltung an der
0:06 Universität Paderborn in diesem Video wollen wir uns einen dritten abstrakten Datentyp angucken nämlich das sogenannte Wörterbuch ein Wörterbuch soll für uns
0:13 etwas dynamisches sein anders also als ein klassisches Wörterbuch das wir aus dem Regal nehmen und in dass wir nichts schreiben können sollen unsere
0:20 Wörterbücher so aufgebaut sein dass wir in sich jederzeit etwas einfügen können daraus ergibt sich dann auch schon die erste Operation die wir für unsere
0:28 Wörterbücher haben wollen nämlich eine insert diese soll einen Schlüssel und einen Wert bekommen solche Paare aus Schlüsseln und Werten kennen wir schon
0:35 sie sind uns schon mal im Zusammenhang mit Attributen begegnet und hier ist es ganz ähnlich nehmen wir an wir wollten ein deutsch-englisches Wörterbuch haben
0:42 der Schlüssel oder key wäre dann das deutsche Wort und der englische Begriff dazu wäre entsprechend der Wert der Value wir könnten das natürlich auch
0:49 genau umgekehrt machen für ein englischdeutsches Wörterbuch da wäre dann das englische Wort der Schlüssel nachdem wir suchen und der valje dazu
0:56 wäre dann die deutsche Übersetzung solche Wörterbücher sind aber auch allgemeiner einsetzbar es könnte sich beispielsweise auch um ein Lexikon
1:03 Handeln ein Lexikon wäre dann eben so aufgebaut dass der Schlüssel das Wort ist unter dem wir den Eintrag im Lexikon finden würden und der Wert dazu wäre
1:10 dann eben der gesamte Text der zu diesem Stichwort im Lexikon steht oder vielleicht sogar ein noch komplexeres Objekt das nicht nur aus Text besteht
1:17 sondern vielleicht sogar Bilder oder was auch sonst noch immer enthält das heißt also die Schlüssel müssen einfach sein in dem Sinn dass sie schnell
1:23 durchsuchbar sind sie müssen vor allem vergleichbar sein dafür können wir beispielsweise Zeichenketten oder Zahlen nehmen unsere W Werte aber können
1:30 beliebig komplex sein sie können beliebige Objekte sein wir könnten also z.B ein Wörterbuch von den Studierenden unserer Universität verwalten in diesem
1:38 Fall würden wir dann eher von einer Liste als von einem Wörterbuch sprechen dann wären beispielsweise die Matrikelnummer die Schlüssel und alle
1:44 Daten die wir zu einem Studenten oder einer Studentin gespeichert haben wären entsprechend der Wert zu diesem Schlüssel wir könnten beispielsweise
1:51 auch ein Telefonbuch haben in einem Telefonbuch wäre der Name der Schlüssel und die Telefonnummer dazu wäre der Wert da merken wir jetzt allerdings dass wir
1:58 ein kleines Problem haben der Schlüssel wäre nämlich nicht eindeutig es könnte ja mehrere Leute gleichen Namens geben und das kommt gar nicht me mal so selten
2:05 vor das ist natürlich etwas was bei uns nicht zulässig ist der Schlüssel muss eindeutig sein so verlangen wir das in unseren Wörterbüchern jeder Schlüssel
2:12 darf nur genau einmal im Wörterbuch vorkommen man kann modifizierte Wörterbücher schreiben wir es erlauben dass ein Schlüssel mehrfach vorkommen
2:18 darf das machen wir hier aber nicht wir wollen uns das Leben ein bisschen einfacher machen s dass unser Schlüssel immer eindeutig sein muss eben wie
2:26 beispielsweise die Matrikelnummern oder wenn wir beispielsweise einen onlineeshop hätten könnten wir Produktnummern verwenden diese
2:31 Produktnummern wären dann der eindeutige Schlüssel der Wert dazu wäre die komplette Produktbeschreibung und vielleicht nicht nur die Beschreibung
2:37 sondern auch noch ein Bild und Kundenbewertungen und was weiß ich noch alles unsere Werte können also beliebige Komplexität erlangen wenn wir etwas in
2:45 unserer Wörterbuch einfügen wollen müssen wir natürlich festlegen unter welchem Schlüssel unser Objekt das wir da jetzt haben abgespeichert werden soll
2:51 und was der Wert ist der dazu gehört was unsere Werte sind lassen wir wie gesagt offen das ist einer der Gründe warum es sich bei diesem worörterbuch einen
2:58 abstrakten Datentyp handelt wir sagen also nicht was für Objekte wir hier speichern wollen beliebige Werte sollen das sein was wir auch im Moment nicht
3:05 vorsehen wollen ist dass wir den Wert zu einem Schlüssel aktualisieren können zu dem Zweck könnte man noch eine zusätzliche Methode Update einführen die
3:13 es dann beispielsweise erlauben würde dass wir einen Eintrag nachträglich modifizieren also beispielsweise den Preis eines Produkts ändern oder den
3:19 Namen einer Person das wollen wir hier nicht machen wir machen es uns wie gesagt relativ einfach wir wollen nur neue Objekte unter einem gegebenen
3:25 Schlüssel einfügen und wir wollen Sie nachschlagen können nehmen also einfach einmal den einfachen Fall eines wirklichen Wörterbuchs in dem wir
3:33 deutsche Begriffe nachschlagen und die englischen Übersetzungen dazu herausfinden können die Methode insert die wir als erstes betrachten müssten
3:40 wir dann dementsprechend so aufbauen dass wir ein Insert zwei Zeichenketten übergeben nämlich zuerst als Schlüssel das deutsche Wort und als Wert dann das
3:46 entsprechende englische Wort jeweils als Zeichenkette so sollte dann mit insert unser Wort oder unser Eintrag sollte ich vielleicht allgemeiner sagen in unser
3:55 worörterbuch eingefügt werden wir wollen natürlich auch in der Lage sein zu einem gegebenen üs den entsprechenden Wert wieder aus dem Wörterbuch auszulesen es
4:02 wäre ja dumm wenn man nur Sachen in das Wörterbuch einfügen aber nie wieder nachschlagen könnte der Sinn alses Wörterbuchs ist ja vor allem dass wir
4:08 etwas nachschlagen können wir wollen also bei unserem Beispiel eines richtigen deutsch-englischwörterbuchs eben den deutschen Wert eingeben sagen
4:15 wir wir suchen jetzt zu dem Wort Hirsch beispielsweise die Übersetzung dann soll das Wörterbuch natürlich entsprechend die englische Übersetzung zurückliefern
4:22 oder allgemeiner gesprochen zu einem gesuchten Schlüssel soll der entsprechende Eintrag geliefert werden zu einer Matrikelnummer das
4:29 entsprechende studentenobjekt zu einer ISBN-Nummer das entsprechende buchobjekt zu einer Bestellnummer das entsprechende Produkt oder was auch immer wir in
4:35 unserem Wörterbuch gespeichert haben der Wert sollte also zurückkommen unsere Methode lookup zum nachschlagen muss also einen Rückgabewert liefern und der
4:44 Rückgabewert soll der Wert sein den wir zu diesem Schlüssel im Wörterbuch gespeichert haben auch die Methode insert wollen wir übrigens mit einem
4:51 Rückgabewert versehen sie soll nämlich true zurückgeben wenn das Einfügen geklappt hat und fals wenn es nicht geklappt hat und klappen soll das immer
4:58 genau dann wenn zu dem Schlüssel noch kein Eintrag vorhanden ist das bedeutet also dass wir mit dem insert auch feststellen können ob ein Wort schon
5:06 enthalten war dann durften wir sie nicht erneut einfügen weil ein Schlüssel ja wie gesagt nur einmal vorkommen darf wenn wir diese Prüfung nicht machen
5:13 würden wäre es an dieser Stelle ein bisschen einfacher dafür aber an anderer Stelle komplizierter wir wollen daher diese Prüfung machen das heißt wir
5:20 überprüfen grundsätzlich erst einmal ob das Wort schon enthalten ist ob also ein entsprechender Schlüssel schon vorhanden ist wenn das der Fall ist erlauben wir
5:27 das Einfügen nicht ansonsten erlauben wir es und geben das auch nach außen als Rückmeldung zurück indem wir den rückgabewer true bei Erfolg zurückgeben
5:35 oder false wenn das Element nicht eingefügt werden konnte weil zu dem Schlüssel bereits ein Eintrag vorhanden ist lookup wie gesagt erhält einen
5:42 Schlüssel als Parameter und gibt dann entsprechend den Wert dazu zurück dann haben wir noch eine dritte Methode die wir umsetzen wollen das ist die Methode
5:50 remove mit der wir ein Wort aus dem Wörterbuch löschen können also einen Eintrag aus dem Wörterbuch entfernen nehmen wir wieder das Beispiel eines
5:56 Produktkatalogs wenn das Produkt nicht mehr bei uns existiert weil wir es nicht nicht mehr anbieten dann wollen wir es aus unserem Katalog entfernen oder ein
6:03 Student oder eine Studentin an unserer Universität wird exmatrikuliert weil er oder sie z.B den Abschluss geschafft hat und dann natürlich anschließend nicht
6:10 mehr Mitglied der Universität ist dann muss er oder sie also aus den entsprechenden Listen gelöscht werden und das ist genau das was wir mit remove
6:17 machen auch dieser Methode übergeben wir natürlich nur einen Schlüssel also beim Studenten bzw der Studentin die Matrikelnummer und dann wurde das
6:23 entsprechende Objekt gelöscht werden das kann offenbar nur gelingen wenn der Eintrag auch tatsächlich vorhanden ist und dann gibt ihr mit Methode true
6:30 zurück weil es in diesem Fall wirklich gelungen ist dieses Element zu entfernen wenn es dagegen nicht gelingt weil nämlich beispielsweise der Schlüssel gar
6:36 nicht im Wörterbuch enthalten war also der Student bzw die Studentin schon gar nicht mehr in unserer Liste drin war oder wir eine zufällig geratene
6:43 Matrikelnummer verwendet haben die es aber gar nicht gibt dann würde unsere Methode remove entsprechend false zurückgeben und auch hier feststellen ob
6:50 unsere Aktion erfolgreich war wir werden später noch eine vierte Methode dazu haben wollen nämlich eine Methode to String die das komplette Wörterbuch
6:58 ausgibt aber darum kümmern wir uns später auf diese Art und Weise können wir dann also diese ganzen Operationen durchführen und auch wenn das erst
7:05 einmal sehr eingeschänkt klingt haben wir mit diesem wterbuch schon ein sehr umfangreiches Anwendungsspektrum man kann also schon eine ganze Menge mit
7:11 einem solch doch recht einfachen Ding machen deshalb wollen wir uns dieses Ding jetzt genauer angucken wenn wir das nun praktisch umsetzen und ausprobieren
7:19 wollen müssen wir uns einmal kurz Gedanken machen auch wenn uns das hier eigentlich noch am Rande interessiert was wir denn tatsächlich hier in unseren
7:24 Wörterbüchern speichern wollen und das können wir gerade schon beschrieben verschiedenste Dinge sein wir machen es un hier ganz einfach unsere Wörter
7:30 sollen tatsächlich Wörter sein also Übersetzungen von deutschen Wörtern in englische Wörter unsere Wörter sind daher einfach so aufgebaut dass sie zwei
7:38 Komponenten haben nämlich ein Wort ein deutsches als Schlüssel und ein Wort ein englisches als Wert man kann sich das also im Grunde so vorstellen wie das
7:46 hier rechts auf der Folie sehen zu sehen ist also wie ein doppelkästchen bei dem ich hier in fett gedruckt oben den Schlüssel stehen habe und als Wert
7:53 darunter die entsprechende englische Übersetzung so zumindest kann man sich das vorstellen intern ist dann natürlich nicht als Kästchen gespeichert sondern
8:00 wir haben ein wortobjekt mit zwei Eigenschaften und das sehen wir hier links in unserem Quelltext die Klasse Word hat einen Konstruktor dem wir einen
8:08 Schlüssel und einen Wert übergeben können wir würden also dann beispielsweise Hirsch und dir übergeben diese beiden Werte werden dann in den
8:16 Eigenschaften key und value gespeichert der erste Parameter als Key der zweite als value unsere Wörter verfügen außerdem über eine Methode to String mit
8:23 der sie sich ausgeben können wir machen es uns hier wieder ganz einfach sie geben sich einfach als Absätze aus so können wir dann später einfach einzelne
8:31 Wörter oder auch das ganze Wörterbuch ausgeben jedes Wort steht dann in einem eigenen Absatz in dem zunächst der Schlüssel steht also das deutsche Wort
8:38 dann ein Doppelpunkt und dahinter dann der Wert also die englische Übersetzung zu diesem Wort bei diesem beispielwort würde also Hirsch Doppelpunkt dir als
8:45 Absatz auf unserer Webseite ausgegeben werden wenn wir diese Methode aufrufen wir können dann wie wir das ganz unten auf der Folie im Beispiel sehen mit New
8:53 World in Klammern dann Hirsch und der oder New World Feuerwehr 112 beispielsweise einen entsprechenden Wörterbucheintrag bzw Telefonbucheintrag
9:03 vornehmen komplizierter sind unsere Objekte hier nicht wir könnten aber wie gesagt auch ganz andere Dinge haben viel komplexere Objekte und dann tatsächlich
9:11 würde das alles was wir hier gleich machen werden sogar auch funktionieren wenn wir unsere Buchobjekte vom letzten Mal als Werte einsetzen würden das
9:18 könnten wir hier deshalb machen weil auch diese Buchobjekte ja wissen wie sie sich als Zeichenkette ausgeben würden wir müssen das ein kleines bisschen
9:24 modifizieren weil wir damit Tabellen gearbeitet haben aber das ist gar nicht so kompliziert wir werden relativ schnell dabei dass wir auch einen
9:30 Buchkatalog beispielsweise haben könnten da müssten wir uns nur überlegen was wir als Schlüssel verwenden würden das könnten z.B isbnnummern sein die genau
9:37 zu einem solchen Zweck erfunden worden sind so einfach sehen also unsere Wörter aus und jetzt können wir die Wörter in ein Wörterbuch schreiben Wörterbuch
9:46 heißt auf Englisch dictionary und deshalb nennen wir unseren abstrakten Datentyp auch so auch für das Dictionary benötigen wir natürlich einen
9:52 Konstruktor und wenn wir ein neues Wörterbuch erstellen wollen mit new dictionary und das dann in einer Variablen speichern leted d gleich new
9:59 dictionary beispielsweise könnten wir zunächst ein leeres Wörterbuch erzeugen und bei diesem Wörterbuch machen wir das ähnlich wie wir das in den letzten
10:06 beiden Videos gesehen haben wir haben eine interne Eigenschaft die wir wieder data nennen die soll wieder nur intern verwendet werden von außen wird man
10:13 keinen Zugriff auf Sie verwenden wollen man bräuchte da ein spezielles Konstrukt mit dem wir uns hier nicht beschäftigen wollen um einen solchen Zugriff auch
10:20 tatsächlich zu unterbinden hier ist es zwar theoretisch möglich auf die Eigenschaft data zuzugreifen aber wir wollen das auch hier wieder nicht tun
10:27 wir wollen nur mit den Methoden die wir für das dictionary gleich noch definieren werden darauf zugreifen in der nächsten Woche werden wir uns diese
10:33 interne Datenstruktur noch einmal genauer angucken da werden wir uns angucken was die hier von mir gewählte Variante nämlich ein Array zu verwenden
10:40 für Nachteile hat und wir werden Sie dann durch eine komplett andere Datenstruktur ersetzen ohne dass sich aber an dem dictionary nach außen hin
10:46 etwas ändert das heißt dass ich unsere Abstraktion die wir in dem Datentyp vornehmen dann noch einmal zeigen wird da wir nämlich die interne Struktur
10:54 dieses Datentyps zunächst einmal eigentlich gar nicht festgelegt haben erst in dem Moment in den wir ihn implementieren wollen und das ist der
11:00 Punkt an dem wir gerade stehen müssen wir uns überlegen wie wir das konkret machen möchten hier verwenden wir wie gesagt ein Array und dann können wir uns
11:08 das so vorstellen wie ich das da rechts schon einmal angefangen habe hinzumalen das können wir jetzt zunächst einmal z.B für das erste Tier machen wenn wir jetzt
11:17 ein weiteres Tier einfügen würde das entsprechend hinten dran geschrieben werden wir können dann ein drittes Tier einfügen und dann fügen wir noch ein
11:25 viertes Wort hinten an hier sind das immer Tiere also immer deutsch-englische Wortpaare von Tieren aber das ist natürlich nur mehr oder weniger zufällig
11:31 so wenn wir hier nur den Hasen einfügen sehen wir allerdings auch dass unser dictionary eine kleine Merkwürdigkeit aufweist es ist nämlich nicht sortiert
11:38 wir fügen die Elemente einfach immer hinten an die Einträge sind also nicht alphabetisch sortiert wie wir das normalerweise von einem Wörterbuch
11:45 erwarten würden warum nun das einfügen würde viel komplizierter werden wenn wir das machen würden zum Nachschlagen hätte das allerdings auch gewisse Vorteile das
11:54 gucken wir uns aber später noch mal an für den Augenblick machen wir es einfach also einfach so dass wir immer wenn wir ein neues Wort haben dieses einfach
12:02 hinten anfügen und jetzt müssen wir uns natürlich überlegen wie wir diese Methoden umsetzen können also die Methoden lookup insert remove und to
12:09 String ich beginne mit der Methode insert wir wollen uns also überlegen wie wir zunächst einmal einen neues Wort in unser Wörterbuch einfügen nun das
12:17 funktioniert so dass wir einen Key und einen value übergeben bekommen also Hirsch und dir beispielsweise als deutsches und als englisches Wort das
12:24 sind unsere beiden Parameter was müssen wir jetzt machen wir müssen zunächst einmal über prüfen ob das Wort schon in unserem Wörterbuch vorhanden ist dafür
12:32 können wir die Methode lookup verwenden die werden wir noch schreiben müssen zum Glück verfügt unser worörterbuch ja über eine solche Methode aber noch haben wir
12:39 sie nicht trotzdem wir sind ja vorausschauend wir wissen dass wir diese Methode gleich noch schreiben werden werden wir die hier verwenden wir wissen
12:46 auch schon das hatten wir schon festgelegt dass die Methode lookup den wird fals zurückliefern wird wenn der Schlüssel nicht im Wörterbuch enthalten
12:53 ist das heißt also wenn this.lup für den Schlüssel den wir gerade übergeben bekommen haben gleich false ist dann wissen wir dass in unserem Wörterbuch
13:02 bislang kein entsprechendes Wort unter diesem Schlüssel gespeichert ist und das bedeutet wir können dieses Wort nun selber bedenkenlos einfügen dafür bauen
13:10 wir ein neues wortobjekt zusammen mit neww key value key und value haben wir hier als Parameter übergeben bekommen bauen wir jetzt ein wortobjekt zusammen
13:18 und dieses wortobjekt fügen wir dann wo ein na ja in unsere interne Datenstruktur natürlich unsere interne Datenstruktur ist im Moment ein Array
13:25 und an ein Array können wir einfach hinten etwas anfügen indem wir die Methode Push für dieses Array aufrufen dieses interne Array heißt dis. datata
13:34 dann schreiben wir hinter dahinter pun Push und übergeben dem als Parameter unser Wort das wir gerade mit New World key value erzeugt haben wir hätten
13:42 dieses Wort auch erst in einer lokalen Variablen in der Methode speichern können und dann diese Variable an dis.data.push übergeben aber so ist es
13:49 kürzer und funktioniert mindestens genauso gut mit dieser einen Zeile sorgen wir also dafür dass ein neues wortobjekt erzeugt wird und dieses
13:57 wortobjekt in das aray eingeführt wird und zwar an die hinterste Stelle anschließend wissen wir dass das funktioniert hat und deshalb können wir
14:04 jetzt true zurückgeben und sind fertig wenn hingegen this. lookup von Key nicht false ist also true ist dann muss das Insert umgekehrt aber false zurückgeben
14:14 denn wenn das Objekt schon im Wörterbuch gefunden wurde ein Eintrag mit dem entsprechenden Schlüssel also schon vorhanden ist dann bedeutet das dass wir
14:20 auf keinen Fall den neuen Wert einfügen dürfen und wenn wir das übergebene Wort nicht einfügen so hatten wir gesagt dann soll insert den Wert false zurückliefern
14:29 auf diese Art und Weise haben wir also jetzt sichergestellt dass ein neues Wort eingefügt wurde wenn es zu dem entsprechenden Schlüssel noch kein Wort
14:35 gab wir geben mit dem Fall true zurück wenn das funktioniert hat und wir geben false zurück wenn das nicht funktioniert hat jetzt müssen wir natürlich dafür
14:44 sorgen dass wir die Methode lookup implementieren wie gucken wir denn jetzt bitteschön nach ob ein Wort in diesem Wörterbuch schon enthalten ist gut da
14:51 bleibt uns gar nichts anderes übrig als unsere interne Datenstruktur zu durchsuchen im Augenblick ist das ein Array und so müssen wir denn das interne
14:58 Array von vor vorne bis hinten durchlaufen denn wir haben ja keine Ahnung wo in diesem aray der Hirsch vielleicht stehen könnte als ich eben
15:05 den Hirsch eingefügt habe war das wörterbook ja noch sehr klein aber nehmen wir z.B den Hasen als der eingefügt wurde da wussten wir nicht wo
15:11 wir suchen sollen wir können ja nicht sagen dass wir am Anfang gucken müssten oder in der Mitte oder am Ende wir haben ja keine Ahnung wie das Wörterbuch
15:17 aufgebaut ist es ist ja unsortiert bzw die Wörter stehen in der Reihenfolge darin in der die Wörter eingefügt wurden wir haben also keine andere Wahl als das
15:25 was wir bislang auch schon immer gemacht haben also wenn wir beispielsweise ein bestimmt des Elementen der Bücherliste gesucht haben die wir neulich umgesetzt
15:31 haben auch da mussten wir immer das komplette Array von vorne bis hinten durchlaufen das hat gewisse Nachteile und ist oft nicht geschickt aber bislang
15:38 hatten wir uns dann nie einen Kopf drum gemacht und so wie wir hier jetzt angefangen haben haben wir erst einmal gar nicht viele Möglichkeiten das anders
15:44 zu machen aber das werden wir wie gesagt noch thematisieren wir machen es also wieder ähnlich wie wir das neulich bei den Bücherlisten gesehen haben genau wie
15:51 dort nehmen wir uns eine Schleife her die wie wir das nun wahrlich schon oft gesehen haben von Null losläuft und dann durch das gesamte Array läuft wie lange
15:58 ist das Array das interne Array heißt disp datata das hat length viele Elemente also läuft die Schleife solange unser Index i kleiner als disp data pun
16:07 length ist und wir erhöhen i in jeder Runde um eins in der Schleife überprüfen wir in einer Abfrage if abfrage jeweils ob der Key den wir als Parameter über
16:16 übergeben bekommen haben identisch ist mit dem Key des gerade betrachteten Elements im Array das heißt wenn wir beispielsweise den has und suchen gucken
16:23 wir als erstes das nullte Element an das ist der Hirsch gewesen ist das deutsche Wort Hirsch zufälligerweise identisch zu H haben den gesuchten Schlüssel gefunden
16:30 das ist natürlich nicht der Fall also gucken wir uns das nächste Wort an das ist das Schaf dann der Wahl und so weiter bis wir irgendwann beim Hasen
16:37 angekommen sind und wenn die beiden Wörter übereinstimmen also der übergebene Schlüssel Hase mit dem Schlüssel unseres gerade betrachteten
16:44 Wörterbuch eininttrags übereinstimmt Hase dann wissen wir in dem Moment dass wir jetzt den richtigen Schlüssel das richtige Wort gefunden haben und können
16:51 den Wert das entsprechende englische Wort dazu das ja im value dieses Array Elements gespeichert ist zurückgeben unsere Methode liefert in diesem Fall
16:59 also this. data an der Stelle i. value zurück wir erhalten also die englische Übersetzung zum Hasen wenn wir dagegen niemals eine Übereinstimmung finden dann
17:09 läuft unsere Schleife bis zum Ende durch wir haben nie eine Übereinstimmung gefunden und wir wissen also dass der Gesuchte Schlüssel nicht im areay
17:15 enthalten war und in diesem Fall geben wir forszeug weil wir ja nun sagen können tut mir leid zu dem Schlüssel haben wir keinen Eintrag gefunden und
17:23 das ist genau das was luup machen sollte in diesem Fall soll die Methode false zurückgeben wenden wir uns jetzt im Löschen von Einträgen zu wie können wir
17:30 das machen wie können wir einzelne Wörter aus dem Wörterbuch entfernen wir sehen schon dass der Code einigermaßen kompliziert ist woran liegt das nun wir
17:39 hatten neulich ja schon bei einem Beispiel einmal diesen Effekt dass wenn wir aus einer Liste beispielsweise also also aus einem Array irgendwo mittendrin
17:46 etwas herauslöschen Lücken in diesem Ding entstehen das möchte ich hier bei dem Wörterbuch vermeiden deshalb verwenden wir folgenden Trick den ich da
17:53 oben mit diesem kleinen Diagramm das ich da aufgemalt habe illustrieren möchte nehmen wir an dass wir aus dem beispielwörterbuch von eben den Wahl
18:00 löschen wollen unsere Methode kriegt also wieder einen Schlüssel übergeben z.B Wahl wir müssen jetzt wieder unser Array durchsuchen bis wir das
18:08 entsprechende Element gefunden haben in unserem Beispiel befand sich dieser Eintrag an der dritten Stelle des Arrays es soll also das dritte Element gelöscht
18:14 werden jetzt könnten wir es theoretisch einfach entfernen und dann nichts hineinschreiben dann haben wir aber hier ein undefiniertes Element mitten in
18:22 unserem Wörterbuch hätten also sozusagen ein Loch darin wenn man so möchte das möchten wir vermeiden und deshalb gehen wir kurz so vor dass wir einfach das
18:30 letzte Element nehmen und es an diese Stelle packen das letzte Element müssen wir dann natürlich löschen damit es nicht zweimal im Wörterbuch steht das
18:36 darf nicht sein das letzte Element wird also in die gerade frei gewordene Stelle hineinverschoben und wenn wir das so machen vermeiden wir dass ein Loch in
18:44 unserem Array entsteht jetzt kommt allerdings noch eine kleine zusätzliche Komplikation was machen wir denn wenn ausgerechnet das letzte Element gelöscht
18:52 werden soll dann funktioniert der Mechanismus so nicht denn dann darf das letzte Element ja nicht woanders hinverschoben werden oder genauer gesagt
18:59 auf sich selbst verschoben werden schaut euch den Code mal genau an und spielt das mal auf Papier durch in diesem Fall müssen wir direkt das letzte Element
19:06 löschen und dann nichts weitermachen und das macht diese Methode remove jetzt ein kleines bisschen kompliziert das solltet ihr euch einmal ganz detailliert auf den
19:14 Hirnwindungen zergehen lassen was machen wir also nun der Reihe nach wir bekommen einen Schlüssel übergeben Wahl beispielsweise jetzt laufen wir wieder
19:21 durch unser Array genau wie wir das eben bei der Methode lookup gemacht haben wir machen fast genau das gleiche nur können wir die Methode lookup hier nicht
19:28 verwenden weil die uns nicht sagt an welcher Stelle wir das Element gefunden haben wenn wir es denn finden sie sagt uns nur ich habe es gefunden und gibt
19:35 dann den entsprechenden englischen Begriff zurück oder sie sagt einfach ich habe es nicht gefunden hier brauchen wir aber jetzt die Position an der wir das
19:42 Element gefunden haben deshalb müssen wir hier im Grunde genommen dasselbe wie eben bei dem lookup noch einmal machen nur dass wir innerhalb der ifabfrage in
19:49 dem Fall dass wir das Element gefunden haben nun etwas anderes tun wir laufen also wieder durch unser Array V let i = 0 i kleiner dis. datata.length i++ das
19:59 komplette Array wird also von vorne bis hinten durchlaufen für überprüfen in jeder Runde ob der Schlüssel den wir übergeben bekommen haben übereinstimmt
20:05 mit dem Schlüssel des gerade betrachteten Objekt soweit also alles wie eben wenn wir den gesuchten Schlüssel also das gesuchte Element
20:12 gefunden haben müssen wir einmal überprüfen ob wir uns nicht an der letzten Stelle befinden wir prüfen also if I kleiner dis. dat L-1 wenn wir uns
20:21 also nicht beim letzten Element befinden das ist die Situation wie sie in dem Bild oben dargestellt ist sondern irgendwo mittend drin nehmen wir das
20:28 letzte Element in unserem Array wir wissen dass wir das kriegen mit this.data.pop die Methode Pop des Arrays liefert uns das letzte Element des
20:36 Arrays und entfernt das aus ihm jetzt haben wir es quasi in der Hand und was machen wir mit dem Element das stecken wir jetzt genau an die aktuelle Position
20:44 an der wir gerade stehen this. data an der Stelle i wird also dieses letzte Element zugewiesen wir brauchen keine neuen Wörter zu erzeugen sondern wir
20:52 nehmen einfach das wortobjekt dass wir dort an der letzten Stelle des Ars gefunden haben und verschieben es an diese Position das haben wir mit dieser
20:59 Anweisung erreicht jetzt müssen wir uns noch den elsfall angucken wenn also i== this. datap l -1 ist größer als dieser Wert kann i nie werden dafür sorgt
21:09 unsere vorschleife ja i wird niemals größer als disp datap l -1 sein wenn i also gleich diesem Wert ist dann kommen wir in diesen zweiten Zweig hinein und
21:19 dann machen wir einfach nur this.data.p das heißt wir entfernen einfach nur das letzte Element wir wollen das gar nicht zurückgeben und
21:27 damit irgendetwas ma sondern lassen das Element dass die Methode Pop des Ars zurückgibt einfach verpuffen das Wort verschwindet es ist nicht mehr im
21:35 worörterbuch enthalten in beiden Fällen folgt anschließend die Anweisung return true denn wir haben ja in beiden Fällen erfolgreich das gewünschte Element
21:42 entfernt gucken uns das ganze jetzt noch einmal von innen nach außen an ganz innen haben wir also diese If Abfrage mit dem elszweig diese Abfrage überprüft
21:51 nur ob es sich bei dem Gefundenen Element um das letzte Element des Arrays handelt oder nicht also ein inneres Element sozusagen in jedem beiden Fälle
21:59 können wir das Element entfernen müssen dabei aber etwas unterschiedlich vorgehen wir wissen aber auf jeden Fall dass wir einen Schlüssel gefunden haben
22:05 der mit dem Schlüssel des aktuell betrachteten Elements übereinstimmt das ist die äußere ifabfrage gewesen if key= this. data an der Stelle i. key wenn das
22:14 also übereinstimmte können wir auf jeden Fall das Element entfernen und dazu gehört jetzt entsprechend diese Anweisung return true die wir hier sehen
22:22 wir geben also genau in diesem Fall true zurück sagen also ja das Element konnte entfernt werden mit der Anweisung return true endet auch die Ausführung dieser
22:31 Methode sobald wir ein Return erreicht haben wird die Abarbeitung einer Funktion oder Methode abgebrochen und wir gehen an die aufrufende Stelle
22:39 zurück die Kontrolle ist also wieder an der aufrufenden Stelle beispielsweise im Hauptprogramm oder von wo auch immer wir aufgerufen worden sind zu der Anweisung
22:47 return false die ganz unten als allerletztes noch außerhalb der vorschleife steht kommen wir immer nur dann wenn wir das komplette Array von
22:54 vorne bis hinten durchlaufen haben und niemals eine Übereinstimmung des gesuchten Schlüssels mit im Schlüssel eines Eintrags gefunden haben wenn es
23:00 irgendwann eine Übereinstimmung gegeben hätte wären wir irgendwann bei dem return true angekommen und hätten die Ausführung der Methode beendet nur wenn
23:07 es sie nicht gibt kommen wir bei dem return false an und das heißt also dass in dem Fall unsere Methode remove entsprechend den Wert false
23:14 zurückgliiefert also zurückmeldet dass das Element nicht entfernt werden konnte weil es kein Element mit dem entsprechenden Schlüssel dazu gab bleibt
23:22 zu guter letzt noch die Methode to String die ich gerne umsetzen wollte die gehört wie gesagt streng genommen nicht zu dem Wörterbuch dazu aber auch die
23:28 wollte ich hier gerne einmal zeigen wir wollen einmal das komplette Wörterbuch ausgeben können wie machen wir das nun ähnlich wie wir das schon mehrfach an
23:35 anderer Stelle gesehen haben wir müssen im Prinzip nur unser komplettes aray von vorne bis hinten durchlaufen wir bauen uns in einer Ergebnis varariable die ich
23:42 hier result genannt habe einfach eine Zeichenkette zusammen wir initialisieren die Variable result zunächst mit der leeren Zeichenkette wir durchlaufen das
23:50 Array dann wie üblich von vorne bis hinten das ist unsere Schleife die wir das wie so oft haben und hängen jeweils das aktuelle Element an das aktuelle
23:58 Element ist jeweils ein wortobjekt und wie sich ein wortobjekt ausgibt hatten wir vorhin schon gesehen nämlich als Absatz in der Form deutsches Wort
24:04 Doppelpunkt englisches Wort so werden also alle Wörter nacheinander angefügt und das ganze als Zeichenkette zurückgegeben was wir an dieser Stelle
24:12 allerdings auch schon sehen ist dass wir ein unsortiertes Wörterbuch zurückbekommen das ist für den Benutzer gar nicht schön wenn wir das anders
24:18 haben wollten müssen wir uns jetzt erst noch irgendwie ein paar Gedanken dazu machen wie man ein solches Wörterbuch vielleicht auch sortieren könnte das
24:25 machen wir aber nicht an dieser Stelle die Gedanken die ich mir an dieser Stelle gerne noch machen möchte betreffen die Frage wie denn eigentlich
24:30 das Laufzeitverhalten dieses Wörterbuchs aussieht wie aufwendig ist denn das eigentlich was wir da machen überlegen wir dazu einmal was wir für die einzelne
24:38 Operation machen müssen zunächst einmal für das Einfügen eines neuen Wortes was wir machen müssen ist dass wir und das klingt zunächst sehr einfach das neue
24:46 Element nur hinten an das Array anhängen indem wir die Methode Push für das interne Array aufrufen aber tatsächlich ist es so einfach nicht wir müssen ja
24:54 erst einmal nachgucken ob das Wort irgendwo in unserem Wörterbuch schon vorhanden ist das heißt wir müssen erst einmal das komplette Wörterbuch von
25:00 vorne bis hinten durchlaufen im schlimmsten Fall im günstigsten Fall finden wir das Wort schon ganz vorne aber im schlimmsten Fall finden wir das
25:06 Wort erst an der allerletzten Stelle und stellen fest ach das Wort ist ja schon im Wörterbuch der Schlüssel ist also schon vorhanden dann können wir es nicht
25:14 einfügen das heißt wir durchlaufen im ungünstigsten Fall erst einmal das komplette areay und können dann erst sagen so jetzt können wir es einfügen
25:21 dann hängen wir es hinten an das areay an und das eigentlich einfügen selber ist dann gar nicht mehr kompliziert und geht ganz schnell aber das nach schlagen
25:28 am Anfang ob der Schlüssel schon im Wörterbuch vahen ist das ist genau das was es sehr aufwendig macht und wenn wir sehr große Wörterbücher haben stellen
25:35 wir uns jetzt nicht irgendwie ein Wörterbuch mit zehn Einträgen vor sondern stellen wir uns vor unser Wörterbuch steht besteht aus einer
25:40 Million Einträgen dann bedeutet das dass wir eine Million Schritte benötigen bis wir dann tatsächlich erstmal sagen können ja das Wort können wir einfügen
25:48 es ist okay es gibt noch kein Wort mit diesem Schlüssel erst dann können wir mit dem einfügeprozess beginnen der ist dann in ull kom nichts erledigt da
25:55 müssen wir nur einmal hinten an das er ein Element anfügen und das geht sehr schnell die Wortsuche das ist die zweite Methode
26:01 die wir eben geschrieben haben die ist damit also das eigentliche Problem weil wir das ganze Ding das ganze are von vorne bis hinten durchlaufen müssen das
26:08 hatten wir bei dem lookup auch gesehen auch da müssen wir alles von vorne nach hinten durchsuchen die Methode in der Methode insert sah man das nicht so
26:16 direkt an weil dort gar keine Schleife vorkam aber wenn wir genauer hinsehen finden wir natürlich den Aufruf von lookup und wir wissen dann dass wir
26:23 dessen Laufzeit mit berücksichtigen müssen wir könnten also jeweils dafür sorgen dass wir wenn wir ein neues Wort in unser Wörterbuch einfügen das
26:31 komplette Wörterbuch immer sofort sortieren dann könnten wir uns ein clevereres Verfahren für das lookup ausdenken allerdings ist das Sortieren
26:39 ebenfalls sehr aufwendig unter bestimmten Umständen kann sich das lohnen aber dafür müssten wir wissen wie das Wörterbuch verwendet wird werden z.B
26:46 eher selten neue Einträge eingefügt aber häufig nachgeschlagen wäre die Sortierung vermutlich ein Gewinn denken wir noch einmal an eine Uni zurück die
26:53 in einem solchen dictionary die Daten von Studierenden verwaltet da kämen vermutlich nur einmal pro Semester eine ganze Reihe neuer Einträge hinzu aber
27:00 den Rest des Semesters wird man nur nachschlagoperationen haben da könnte es sich also lohnen über entsprechende Verbesserungen nachzudenken das
27:07 Kernproblem dass wir hier bei allen drei Methoden insert lookup und remove haben ist dass wir erst einmal das richtige Wort suchen müssen also einen bestimmten
27:15 Schlüssel in dem Array suchen müssen dafür müssen wir dieses Array von vorne bis hinten durchlaufen weil wir eben keine Sortierung haben deshalb müssen
27:22 wir Element für Element für Element angucken diese Schleifen das hatten wir auch schon gesehen brechen zum Teil früher ab nämlich wenn der Schlüssel
27:29 früh gefunden wird wir haben also keine feste Laufzeit die wir hier angeben können sondern die Laufzeit hängt gewissermaßen davon ab ob wir Glück
27:36 haben oder Pech haben wenn wir Pech haben finden wir nämlich den richtigen Schlüssel erst im letzten oder vorletzten Element dann haben wir
27:43 praktisch das gesamte Worterbuch durchlaufen und eine Million Einträge heißt eben eine Million vergleichsoperation die wir durchführen
27:49 müssen wenn wir Glück haben haben wir immer nur den Hirschen gesucht wollten also immer ein Element das ganz weit vorne steht suchen finden oder entfernen
27:56 das wäre schon ein riesiger Zufall jetzt kann man sich auch überlegen wie lange man denn so im Durchschnitt braucht dazu machen wir uns nächste Woche noch ein
28:03 paar Gedanken das wollen wir in dieser Woche noch nicht angehen die Frage die man sich jetzt aber stellen kann und da kommen wir
28:10 jetzt richtig in die Informatik hinein genau gesagt in das Themenfeld der Algorithmik ist ob es geeignete Algorithmen und Datenstrukturen gibt mit
28:17 denen man so etwas geschickter hinbekommt als wir das jetzt gerade hier angestellt haben und da gibt es in diesem konkreten Fall zwei mögliche
28:23 Strategien die eine besteht darin dass wir eben anders als wir es hier jetzt gerade gemacht haben eben doch eine solche sortierte Liste pflegen und dann
28:32 in dieser Liste geschickt suchen das hat gewisse Vorteile es hat aber auch gewisse Nachteile und über die werden wir uns in der nächsten Woche Gedanken
28:38 machen und das zweite was wir machen können ist dass wir eine ganz andere Datenstruktur verwenden die vielleicht in der Lage ist die Vorteile zu nutzen
28:45 und die Nachteile dennoch zu vermeiden sie wird auch kleine Nachteile haben die nach aber die Nachteile sind vielleicht so geringfügig dass wir sie in Kauf
28:53 nehmen einer der Nachteile wird insbesondere sein dass die Implementierung erheblich kompl erter wird und das ist etwas was wir uns in
29:01 der nächsten Woche angucken wollen da wollen wir uns als krönenden Abschluss Gedanken dazu machen wie man zum einen eben über Effizienz nachdenken kann und
29:08 wie man zum anderen verschiedene Strategien verfolgen kann um eine solche Datenstruktur effizienter hinzekommen damit sind wir mit dem abstrakten
29:16 Datentyp Wörterbuch durch einer Datenstruktur die sehr flexibel einsetzbar ist die sehr umfangreiche Anwendungen hat und eben nicht nur für
29:22 Wörterbücher sondern für alle möglichen Dinge wo man etwas nachschlagen möchte geeignet ist wir steigen in dieser Vorlesung noch nicht in das Thema der
29:28 Datenbanken ein das kommt erst im übernächsten Semester aber eine Datenhaltung mit Hilfe von solchen schlüsselwertparen wo wir nach einem
29:33 Schlüssel suchen wollen und ein Wert dazu zurückgeliefert bekommen wo wir einen Datenbestand dynamisch aufbauen können indem wir neue Elemente
29:40 hinzufügen können wo wir Elemente entfernen können l sich hiermit sehr gut umsetzen dazu brauchen wir wie eben gesehen drei Operationen nämlich die
29:47 drei Methoden die wir eben für das Wörterbuch vorgesehen haben insert lookup und remove man könnte sich noch eine Methode Update dazu vorstellen um
29:54 Einträge aktualisieren zu können und weil wir neugierig sind sind haben wir auch noch eine zusätzliche Methode dur String implementiert um das Ganze
30:01 Wörterbuch auszugeben die muss man nicht unbedingt haben wenn man das Wörterbuch vielleicht gar nicht als Ganzes ausgeben möchte aber wir haben das an dieser
30:07 Stelle mal mit vorgesehen im beispielkode zu dieser Vorlesung könnt ihr euch auch anschauen wie das ganze denn funktioniert und dass man mit
30:13 diesem Wörterbuch durchaus arbeiten kann tschüss bis zum nächsten Video