Video 8-1: Abstract Data Types & Collections

0:02 Im nächsten Abschnitt wenden wir uns einem ganz anderen Thema zu, nämlich dem zweiten Teil des Titels des Moduls, sehr viel mehr, den Datenstrukturen und im ersten Abschnitt äh letztlich den Listen, wie sie auch im Logo zu finden sind. Äh und das dynamisch bezieht sich darauf, dass ich an an vielen Stellen Änderungen vornehmen kann.

0:29 Sie werden einige der Implementierung, die die ich hier vorstelle, äh kennen aus objektorientierten Programmierungsvorlesung oder vielleicht auch sonst ähm sind die nicht besonders schwierig. Äh, ich möchte aber sozusagen ein bisschen die ähm die Interfaces dazu klar benennen und an paar Stellen gibt's so ein paar Kniffe, die man hervorheben möchte, die vielleicht nicht allen die vielleicht äh tatsächlich nicht so offensichtlich sind und es lohnt sich sozusagen von dem gesammelten Wissen aus der Informatik da auch was weiterzugeben. Aber der Reihe nach ähm bisher haben wir im Wesentlichen alles in Arrays getan. Mit der kleinen Ausnahme von diesem Fallbeispiel von Union Find, wo wir schon äh richtige Datenstrukturen und dynamisch sich ändernde Dinge betrachtet haben, war eigentlich die Eingabe immer ein langes Array von Dingen und dann haben wir den sortiert oder darin gesucht oder vielleicht auch gerechnet. Äh vielleicht kamen auch mal zweidimensionale Sachen vor, wo man irgendwelchen Drachen ausweichen musste und diese Dinge. Äh die Daten waren aber im großen und ganzen statisch und entweder linear oder zumindest so Matrixartig relativ äh starre und fest vorgegeben. Und das wollen wir jetzt ändern. Ganz oft hat man nämlich äh Daten, die sich über die Zeit ändern und die auf interessantere Weise miteinander in Beziehung stehen.

1:57 In diesem Kapitel insbesondere schauen wir uns sozusagen das das Pondor zu Arrays an. Also Folgen von Objekten, die irgendwie eine lineare Ordnung haben im Sinne von total geordnet nach einer Position. Das ist wher der Name letztlich kommt. Ähm ich glaube, es gibt keinen keinen deutschen Begriff, der vollkommen äh nebenbedeutungsfrei ist, um das auszudrücken. Ähm ich bleib bei Listen, aber eine Liste könnte letztlich viel sein, aber eine Liste hat schon irgendwas, was irgendwie ähm ein erstes, ein zweites, ein drittes Element und so weiter hat.

2:38 Um klarer auszudrücken, was wir hier wollen, ähm möchte noch mal einen Schritt zurückgehen und diese abstrakten Datentypen äh noch mal beleuchten. Hatten wir schon bisschen drüber gesprochen, äh aber noch mal etwas ähm noch mal expliziter. Ähm wie spezifiziere ich ein Datenstruktur, ein Datenstrukturproblem oder ein Datenstrukturierungsproblem? Ähm, bisher hatten wir algorithmische Probleme beschrieben, die im Wesentlichen irgendeine Berechnung machen. Da gibt's eine Eingabe und da gibt's eine Ausgabe.

3:17 Das ist so das ganz klassische äh Paradigma und hier drin dann passiert dann irgendwas. Ähm in der Formulierung z.B. vom Sortierproblem hatten wir streng genommen da schon ein bisschen eine Verallgemeinerung angeschaut. Sie werden vielleicht festgestellt haben, ich habe immer geschrieben gegeben, die Eingabe, könnte man sagen, aber dann nicht unbedingt Ausgabe, sondern Ziel, denn manchmal war das Ziel nicht eine neue Kopie der Daten zu produzieren, sondern nur irgendwas äh umzusortieren im Falle von ähm vom Sortierbeispiel. Ähm deswegen war das hier schon so ein bisschen allgemeiner. Streng genommen ist das ja keine Ausgabe, wenn ich nur die Eingabe verändere. Warum es aber tatsächlich hier geht, ist, es gab immer einen definierten vorher und hinterher Zustand und das war's. Äh, für Datenstrukturen ist das nicht unbedingt der Fall, denn ich möchte über die Zeit mehrmals was machen und ich möchte auch sowohl Theseoperationen haben, die mir irgendwelche Informationen liefern, als auch Änderungen vornehmen, Updates vornehmen.

4:20 Also, die äh das Pondant für so eine Spezifikation eines algorithmischen Problems ist dann eben ein abstrakter Datentyp. Abstract Data Tape ADT hat sich ist ein bisschen ein alt mulriff, aber hat sich eingebürgert und ist glaube ich eindeutig, was er meint. Der ist nicht anders vorbelastet. Sie sollten da einfach das als Pondon sehen zu einem algorithmischen Problem, das spezifiziert, was wir möchten. Und für eine Datenstruktur müssen wir angeben, welche Operationen gibt es, was kann ich tun, also Anfragen und Updates. Äh bei Anfragen muss ich angeben, was was ich da hören möchte, was soll die Ausgabe sein. äh abhängig natürlich von dem internen Zustand der Datenstruktur und für Updates muss ich sagen, was sich verändert. In aller Regel möchten wir die Bedeutung von der Datenstruktur auf irgendeine mathematisch definierte Struktur zurückführen. Sie werden gleich äh Beispiele dafür sehen. Und dann ist oft, was man ähm mit den Updates und den Queries machen möchte, kann man abstrakt erklären. Sozusagen die die inhaltlich, was passieren soll, kann man zurückführen auf einen mathematisches Objekt. Das sagt einem dann nicht, wie das schnell geht, aber es sagt einem zumindest, was die korrekte Antwort für alle Queries sein sollte.

5:45 Abgesehen davon, dieser oberflächliche Teil ist durchaus das, was Java mit Interfaces abbildet, aber dieser ähm semantische Teil, der fehlt dabei. Ich kann in Java nicht wirklich sagen, dass äh eine Menge von Zahlen irgendwie die Eigenschaften einer Menge hat, dass ich jedes Element nur einmal drin haben kann oder eben nicht drin und dass ich da vielleicht Elemente hinzufügen kann. Das kann ich in dem Interface nicht ausdrücken. Ich kann zwar die Methoden Insert benennen und dann hoffen, dass mein mein Leser, der Programmierer, der mit dem Interface arbeitet, schon das Richtige da rein repretieren wird. Aber das ist natürlich nicht irgendwie formal festgelegt.

6:25 Der große Kontrast von abstrakten Datentyp ist eine Datenstruktur. Das ist die Implementierung eines Datentyps. Das ist also genau ein Programm, was dann jeweils sagt, hatten wir auch schon mal erwähnt, dass das sind im Prinzip zwei Dinge. Ich muss sagen, wie die Daten strukturiert sind und ich muss sagen, welche Algorithmen diese Queries und Updates implementieren.

6:47 Im Gegensatz dazu sagt der abstrakte Datentyp nur, was passieren soll. Wir hatten ein Beispiel dafür auch gesehen, ähm in dem Fallbeispiel von Union Find. Das war ein abstrakter Datentyp bzw. Unionfind ist ein abstrakter Datentyp. Auf Deutsch könnte man es disjunkte Mengen nennen. Ähm, ich bin versucht noch anzumerken, äh, es sind dynamische disjunkte Mengen. Ich kann die nämlich verändern und in gewissem Sinne sind sie ähm dynamisch nur in eine Richtung. Ähm, ich habe eine Union Operation, aber ich kann Mengen nicht mehr aufteilen. Äh, könnte man sagen, nur dekrementell, dynamische dekrementelle disjunkte Mengen. Ähm, kurz und knackig, deswegen Unionfind. Die Operationen, die wir damals hatten, waren eine Konstruktor, der mir ähm die Anzahl Objekte festlegt. Das war fest äh vorgegeben.

7:50 Also Construct legt eine Instanz an, in der ich dann n verschiedene Objekte habe und die diese Anzahl von Grundobjekten, die kann ich nicht verändern. Die Bedeutung war dann zu jedem Zeitpunkt, dass diese Grundobjekte partitioniert sind in eine Menge von disjunten Mengen. Äh initial war die Anzahl Mengen gleich der Größe des Universums und jedes Element war in seiner eigenen Menge. Sehen sich ähm an die an die Animation vielleicht von damals. Und die beiden Operationen, die arbeiten jetzt eben mit diesen Mengen. Find gibt mir die Menge zurück, in der ein Element drin ist. Es ist so ein bisschen die Frage, was heißt das, eine Menge zurückzugeben? Was wir hier meinen, ist ein ein äh Identifier für die Menge, nicht eine Kopie der Menge. Das wäre zu teuer. Und Union ersetzt eben diese zwei Mengen, die ich da angebe, durch ihre Vereinigung. Das heißt, ich aktualisiere die Datenstruktur und füge zwei Mengen, die bisher getrennt waren, jetzt zusammen.

8:56 Kennen Sie noch? äh müssen sich nur in Erinnerung rufen. Hatten wir gesehen, war ein genau ein klassisches Beispiel von so einem abstrakten Datentyp und äh ein Java Interface, was dazu passt, könnte man könnte man so formulieren. Da gibt's also einen Interface Union Find, dass diese Operation Find und Union anbietet. Aber sie sehen an der Stelle, dass diese diese äh Abbildung von abstrakten Datentypen und Interfaces, die ist nicht ganz Verluste. Ich kann z.B. diese Konstruktoroperation eigentlich nicht darstellen. Äh Interfaes in Java können nicht angeben, wie die Konstruktoren von den Klassen, die das Interface implementieren, aussehen. Eigentlich würden wir gerne sagen, wir hätten hier einen Konstruktor mit einem Parameter n, aber das kann ich höchstens als Kommentar im Code machen.

9:58 Okay. Ä, ich habe eine Frage hier noch vorbereitet, die auf was äh bestimmtes abzielt, aber ich möchte sozusagen nicht vorab beeinflussen. Ähm, das sind alles Klassen aus der Java Runtime Libraries. Ihr kennen das Java Util Package. Äh, mir geht's do darum einfach zu sehen, wie viel damit schon gearbeitet haben, in welchem Kontext auch immer.

10:28 Wenn sie das getan haben, dann haben sie schon mit was arbeiten müssen und wenn nicht, dann ähm ist es vielleicht gut, da ein Moment drauf zu verweilen.

11:11 Gut, ein paar Antworten trickern ja noch rein, aber die überwältigende Mehrheit hat zumindest Arraylist und so weiter mal verwendet. Ähm einige haben tatsächlich noch keine davon verwendet. sollte ich also auch nicht ganz aus äh außen vorlassen. Ähm und gut, dass niemand Vektor verwendet. Sie wissen, dass es letztlich deprecated. Das war eine äh Design Fehlentscheidung in der Bibliothek aus der Anfangszeit. Ähm ich glaube, das war sogar in dem Java Quiz mit drin oder was wir was wir am Anfang gemacht haben. Ich mir nicht mehr sicher, ob die Frage überlebt hat. Äh, wenn Sie das interessiert, können Sie ja nachlesen, warum Vector eine schlechte Idee ist. Ähm ist im Wesentlichen ersetzt durch Array List.

11:57 Was alle diese ähm diese Collections äh gemeinsam haben, ist, dass sie generische Typen verwenden. Und das ist ähm etwas, was sehr natürlich ist für die Art von abstrakten Datentypen, die wir in diesem Kapitel uns auch anschauen. Deswegen ein paar Worte dazu, auch wenn das für viele vielleicht ähm kein großes Thema ist, weil sie es schon äh verwendet haben. Also die ähm besonders natürlich ist es immer dann, wenn meine Datenstruktur eigentlich eine Sammlung von Dingen ist, über die ich recht wenig wissen muss, um die Sammlung äh organisieren zu können. Ähm in Java heißt der Oberbegriff für all diese diese Klassen von der letzten Folie Collection, also eine unspezifizierte Sammlung von Objekten, wo auch Duplikate vorkommen dürfen. Äh Container ist so ein, na ja, Container heißt jetzt heutzutage natürlich auch anderes. Ähm gemeint an der Stelle ist auch das gleiche, also eine Sammlung von Objekten könnte man auch unter dem Namen finden. Äh für diese Art von Datenstrukturen ist üblicherweise dieses Objekt oder diese Sammlung von Objekten komplett äh intransparent. ist eine Blackbox, die wir nicht, wo wir nicht wissen müssen, was drin steckt. Das ist deshalb bequem, weil ich dann all diese Container oder Collections nur einmal implementieren muss, denn die funktionieren für alle Arten von Objekten, die ich da reinstecken möchte, genauso gleich.

13:27 Ähm, nächster Punkt. Ganz oft, wenn man solche äh Collections verwendet, ist es natürlich, dass man da nur Objekte einer bestimmten Art reinpacken möchte. Ich habe sie mal Sorten reingenannt. Sie können natürlich das ersetzen durch eine spezifische Klasse. Das wäre die Variante in Java. Also, wir könnten eine Liste von Strings haben oder eine Menge von Dateien oder eine Matrix von Zahlen und so weiter. Äh und ich möchte selten komplett gemischt beliebige Objekte akzeptieren, gerade weil ich solche ähm solche Collections dann ja auch als Ein oder Ausgabe von weiteren Problemen äh haben können möchte. gibt mir das mehr Ausdrucksstärke, wenn ich da die Typen einschränken kann. Das heißt, ähm man könnte jetzt anfangen, eine Klasse List of String und eine Klasse List of Integer und eine Klasse List of long und so weiter bauen. Sieht dann so ein bisschen aus wie diese Array Start Sold mit den primitiven Typen. Für primitive Typen komme ich nicht drum rum. Für alle anderen, für alle Referenztypen gibt's im Grunde diesen Oberbegriff Object. Das heißt, ich könnte einen List of Object Typ haben. Das ist aber wieder unbequem, weil ich dann nicht mehr ausdrücken kann, dass ich sortenreine Collections haben möchte.

14:41 Ähm, im Prinzip kennen Sie die Idee auch schon. Bei Arrays machen wir das immer so, dass wir den Typ direkt hinschreiben und dann die gegen Klammern hinten dran. Warum also nicht auch für äh diese ähm selbstgebauten Klassen, die die solche Collections implementieren? Und Java erlaubt es mit Typarametern. In Java heißen die heißt das Generics. Ähm letztlich ist es der Ausdruck, ich möchte einen mir unbekannten Typ, aber nur diesen Typ akzeptieren, um gewisse Dinge zu machen. Äh in Java können das äh sowohl Klassen als auch Interfache Methoden und paar andere Sachen können Typarameter haben. Ähm, für die Implementierung dieser Klasse sieht das dann aus, als wäre das einfach irgendein bester Klassenname, den ich nicht genau erkennen muss und ich kann den im Wesentlichen genauso verwenden. Kleines Sternchen, sie kennen Type Eraser und so. Da gibt's so ein paar ähm es gibt so ein paar Dinge, die nicht direkt so natürlich gehen, wie man es erwarten würde, weil es hinterher auf Java drauf gepflanscht wurde als als ein kleiner Hack. Aber um und bei kann man die verwenden, als wäre es einfach ein Klassenname konzeptionell wenigstens.

15:52 Und wenn ich die diese generische Klasse, also machen wir es mal konkret, wir könnten z.B. List of t haben. Das wäre dann der generische Teil. Dann würde ich das implementieren und ich könnte dann eine Variable List of String schreiben und die mit irgendwas initialisieren. Da können Sie dann ihre Array List verwenden. Wir haben das tatsächlich auch schon gesehen beim Sortieren. Die Comparator Objekte, die so ein Sortierkriterium ähm äh Kapseln, die hatten ja auch so ein Typ Parameter. Hatte ich damals so ein bisschen unter den Teppich äh Teppich gewischt. Ähm, wollen wir hier jetzt explizit noch mal beim Namen nennen.