| Beide Seiten, vorherige Überarbeitung Vorherige Überarbeitung Nächste Überarbeitung | Vorherige Überarbeitung |
| faecher:informatik:oberstufe:adt:verkettete_liste:benchmarking:start [01.07.2021 10:21] – [Benchmarking] sbel | faecher:informatik:oberstufe:adt:verkettete_liste:benchmarking:start [04.10.2021 16:51] (aktuell) – [Implementationsvarianten] sbel |
|---|
| ====== Benchmarking verschiedener Listenimplementationen ====== | ====== Benchmarking verschiedener Listenimplementationen ====== |
| |
| Ein Beispiel für ein ADT ist die [[..:start|Verkettete Liste]]. Eine Liste enthält beliebig viele Werte eines Typs ''T'', z.B. Integer-Zahlen. Zudem sind Operationen definiert, die mit der Liste durchgeführt werden können, z.B. ''anhaengen(val: T)''. In der objektorientierten Programmierung entspricht das den Methoden. | Die [[..:start|Verkettete Liste]] ist ein Beispiel für einen **Abstrakten Datentyp (ADT)**. Eine Liste enthält beliebig viele Werte eines Typs ''T'', z.B. Integer-Zahlen. Zudem sind //Operationen// definiert, die mit der Liste durchgeführt werden können, z.B. ''anhaengen(val: T)''. In der objektorientierten Programmierung entspricht das den Methoden. |
| |
| Die Namen der Operationen und ihre Signatur (also Parameter und Rückgabewert) können in Java durch eine **abstrakte Oberklasse** oder ein **Interface** festgelegt werden – dies ist die **//syntaktische//** Beschreibung. | Die Namen der Operationen und ihre Signatur (also Parameter und Rückgabewert) können in Java durch eine **abstrakte Oberklasse** oder ein **Interface** festgelegt werden – dies ist die **//syntaktische//** Beschreibung. |
| Allerdings sagen die Methoden und ihre Signaturen nichts über das **//Verhalten//** des ADTs aus, das ist die **//Semantik//**. Wir müssen also beschreiben, was die Methode ''anhaengen(val: T)'' tut. Prinzipiell könnte die Methode ''anhaengen'' einfach einen leeren Rumpf haben – syntaktisch wäre sie damit korrekt, da es sich um eine Methode ohne Rückgabewert handelt. | Allerdings sagen die Methoden und ihre Signaturen nichts über das **//Verhalten//** des ADTs aus, das ist die **//Semantik//**. Wir müssen also beschreiben, was die Methode ''anhaengen(val: T)'' tut. Prinzipiell könnte die Methode ''anhaengen'' einfach einen leeren Rumpf haben – syntaktisch wäre sie damit korrekt, da es sich um eine Methode ohne Rückgabewert handelt. |
| |
| Ein Programmierer, der die Klasse verwendet, stellt sich aber etwas anderes unter "anhängen" vor. Üblicherweise bedeutet "anhängen", dass das neue Element hinter den vorhandenen Werten angefügt wird. Man könnte sich aber auch vorstellen, dass das neue Element vorne angefügt wird oder nur dann, wenn es noch nicht vorhanden ist oder an der richtigen Stelle im Bezug auf eine Sortierung...((Die Bedeutung des Begriffs "anhängen" (englisch „to append“) ist relativ klar. Die Java-Klasse ''ArrayList'' hat dafür die Methode ''add'' („hinzufügen“), die sprachlich offen lässt, wo der neue Wert eingefügt werden soll. Hier muss die Dokumentation konsultiert werden, die klarstellt, dass der neue Wert ans Ende der Liste kommt.)) | Ein Programmierer, der die Klasse verwendet, stellt sich aber etwas anderes unter "anhängen" vor. Üblicherweise bedeutet "anhängen", dass das neue Element hinter den vorhandenen Werten angefügt wird. Man könnte sich aber auch vorstellen, dass das neue Element vorne angefügt wird oder nur dann, wenn es noch nicht vorhanden ist oder an der richtigen Stelle im Bezug auf eine Sortierung...((Die Bedeutung des Begriffs "anhängen" (englisch „to append“) ist relativ klar. Die Java-Klasse ''ArrayList'' hat dafür die Methode ''add'' („hinzufügen“), die sprachlich offen lässt, wo der neue Wert eingefügt werden soll. Hier muss die //Dokumentation// konsultiert werden, die klarstellt, dass der neue Wert ans Ende der Liste kommt.)) |
| | |
| | |
| | {{ :faecher:informatik:oberstufe:adt:verkettete_liste:benchmarking:liste.png |}} |
| |
| ---- | ---- |
| Eine Liste kann man auf verschiedenste Weisen implementieren, wir wollen jetzt testen, ob sich verschiedene Implementationen verschieden verhalten. | Eine Liste kann man auf verschiedenste Weisen implementieren, wir wollen jetzt testen, ob sich verschiedene Implementationen verschieden verhalten. |
| |
| Im Repository https://codeberg.org/Info-Unterricht/verkettete-liste-java-benchmark.git findest du verschiedene Implementationen einer verketteten Liste sowie eine Benchmark-Klasse. | Im Repository https://codeberg.org/qg-info-unterricht/verkettete-liste-java-benchmark findest du verschiedene Implementationen einer verketteten Liste sowie eine Benchmark-Klasse. |
| |
| |
| |
| Visualisiere mit einem Linien- oder xy-Diagramm, wie sich der Speicherbedarf und die Laufzeit verhalten, wenn die Anzahl der Listenelemente anwächst. Schätze ab (O-Notation), wie sich der Speicher- und Zeitbedarf in Abhängigkeit der Elementanzahl n verhält. Beurteile, wie gut die jeweilige Listenvariante für den jeweiligen Anwendungsfall geeignet ist. | Visualisiere mit einem Linien- oder xy-Diagramm, wie sich der Speicherbedarf und die Laufzeit verhalten, wenn die Anzahl der Listenelemente anwächst. Schätze ab (O-Notation), wie sich der Speicher- und Zeitbedarf in Abhängigkeit der Elementanzahl n verhält. Beurteile, wie gut die jeweilige Listenvariante für den jeweiligen Anwendungsfall geeignet ist. |
| | |
| | Untersuche den Quelltext der Klassen und finde eine Erklärung für das unterschiedliche Verhalten. |
| | |
| | ==== Sortieren geht immer ==== |
| | |
| | Ein wichtiger Aspekt abstrakter Datentypen ist, dass sich unterschiedliche Implementierungen nach außen hin logisch gleich verhalten, d.h. ein Programm, das einen bestimmten abstrakten Datentyp verwendet, muss nicht wissen, wie der Typ implementiert wurde. |
| | |
| | In der Klasse ''SortiererTest'' werden verschiedene Sortieralgorithmen (''SelectionSort'', ''InsertionSort'' und ''MergeSort'') auf dem ADT "Liste" durchgeführt. Dabei ist es unerheblich, um welche Listenimplementation es sich handelt – es werden nur Methoden verwendet, die im ADT definiert werden und diese verhalten sich in allen Implementationen gleich. |
| | |
| | ---- |
| | {{:aufgabe.png?nolink |}} |
| | === (A5) === |
| | |
| | Ersetze in der Methode ''testDurchfuehren'' den Ausdruck ''null'' durch den Konstruktor-Aufruf einer Implementation von "Liste" und führe anschließend die Methode ''testDurchfuehren'' mit Anzahlen zwischen 1.000 und 20.000 aus. Überzeuge dich, dass die Sortierverfahren mit allen Implementationen der Liste funktionieren. |
| | |
| | Vergleiche die gemessenen Laufzeiten – wodurch könnten die Unterschiede verursacht sein? |
| | |