Doppelstunde 3: Konzept „Abstrakte Datentypen“ [nur LF]

Ziel der Stunde ist, dass die Schülerinnen und Schüler das grundsätzliche Prinzip von Abstrakten Datentypen verstehen: Ein ADT ist ein Verbund von Objekten, der bestimmte Operationen anbietet. Zu diesen Operationen müssen sowohl Syntax als auch Semantik definiert werden. Die Syntax wird bereits durch die Methodensignaturen festgelegt, was man z.B. durch eine abstrakte Oberklasse umsetzen kann. Schwieriger ist, die Semantik für einen ADT eindeutig zu definieren.

Der erste Teil des Aufgabenblatts 03_liste_benchmark.odt befasst sich genau damit: Was sollte man bei einer Liste z.B. unter „vorne einfügen“ verstehen? Die Schülerinnen und Schüler werden aufgefordert, in Kleingruppen eine möglichst eindeutige Beschreibung des Verhaltens einiger angegebener Methoden zu formulieren. Wenn danach in einer Plenumsphase die Ergebnisse gesammelt werden, ist die Aufgabe der Lehrkraft, die Ergebnisse auf mögliche Lücken zu überprüfen und die Schülerinnen und Schüler zu einer möglichst vollständigen und korrekten Beschreibung zu leiten.

Im nächsten Teil werden dem Kurs mit dem BlueJ-Projekt 03_listenvarianten_benchmark verschiedene Implementationen vorgelegt. Es handelt sich dabei um einfach verkettete Listen, einmal in iterativer Form und einmal rekursiv. Zudem eine einfach verkettete Liste mit einem Verweis auf das letzte Element und eine Liste, die intern durch ein Array repräsentiert wird. Eine Eigenschaft von ADTs ist, dass es verschiedene Implementationen geben kann, die sich in Laufzeit- und Speichereffizienz unterscheiden. Daher kann man mit der Benchmark-Klasse die verschiedenen Listenvarianten in unterschiedlichen Anwendungsszenarien verwenden und jeweils untersuchen, wie sich die Laufzeit und der Speicherbedarf entwickeln.

Aufgabe der Kursmitglieder ist, die Ausgabe der Benchmark-Aufrufe z.B. in einer Tabellenkalkulation zu untersuchen (und ggf. zu visualisieren). Es ist dabei von Vorteil, wenn man nicht nur den Gesamtspeicherbedarf bzw. die -laufzeit betrachtet, sondern die Werte durch die Anzahl der Elemente dividiert. Damit zeigen sich die Unterschiede der Größenordnung deutlicher. Es zeigen sich Unterschiede zwischen den verschiedenen Implementationen, die im Anschluss durch einen Vergleich der Quellcodes erklärt werden können.

Technische Anmerkungen: Der Speicherbedarfs-Benchmark wird auf etwas unkonventionelle Art und Weise ausgeführt. Der Grund hierfür ist, dass die Java Virtual Machine mit der Option „‑javaagent“ ausgeführt werden muss, um die SizeOf-Bibliothek einzubinden. Diese verwendet die Java-API „Instrumentation“, die seit Java 5 verfügbar ist. Um eine fehlerträchtige Änderung der BlueJ-Konfiguration zu vermeiden, wurde entschieden, dass stattdessen aus dem Programm heraus ein neuer Java-Prozess gestartet wird, dessen Konsolenausgabe geparst wird.

Das Projekt 04_set enthält kompilierte .class-Dateien, damit der Quellcode der Set-Varianten verborgen bleibt. Unter bestimmten Umständen kann es sein, dass die Java-Version an Ihrer Schule nicht mit den kompilierten Dateien kompatibel ist. In diesem Fall sollten Sie das Projekt 04_set (mit Sourcecode) selbst noch einmal auf den Schulrechnern kompilieren und die dabei entstehenden .class- und .ctxt-Dateien an die Schülerinnen und Schüler austeilen.

Als Erweiterung der Stunde wird der ADT Set besprochen. In der Präsentation 04_set.odp
werden drei unterschiedliche Implementationsansätze erläutert und ihre Vor- und Nachteile beschrieben. Im Anschluss erhalten die Schülerinnen und Schüler ein Projekt mit drei kompilierten Implementationen der Set. Sie sind nur als SetVarianteA, SetVarianteB und SetVarianteC benannt und der Quellcode ist nicht einsehbar, so dass man daran nicht erkennen kann, welche Klasse welche Variante darstellt³ . Die Aufgabe für die Schülerinnen und Schüler ist nun, mit ihrem Wissen über die Unterschiede zwischen den vorgestellten Varianten Benchmarks zu entwerfen, mit denen man herausfinden kann, welche Klasse für welche Variante steht. Bei der Implementation des Benchmarks kann man sich an der Methode „meinTest“ orientieren. Vor dem Aufruf der Methode ist die Set immer leer.

Als mögliche Indikatoren kann man die folgenden Benchmarks verwenden:

• Man fügt erst ein paar Zahlen von 1 bis 10 ein und dann die Zahl 1.000.000 – hier sollte der Speicherbedarf der Bitvektor-Set sprunghaft ansteigen, wodurch man diese identifiziert hat.
  • Alternativ: Man fügt zuerst die große Zahl ein und dann beliebig viele kleinere Zahlen. Der Speicherbedarf wächst jetzt nicht mehr.
• Man fügt z.B. die Zahlen von 1 bis 100.000 ein und misst die Laufzeit. Der Zeitbedarf der Set, die einfach eine ArrayList verwendet, steigt für jedes weitere Element linear an. In der Summe ergibt sich hier eine quadratische Laufzeit, wodurch man diese identifiziert hat.
• Die verbliebene Set-Implementation muss demnach die Hashtable-Implementation sein. Hier sollte man feststellen, dass der Speicherbedarf etwa linear mit der Anzahl der Elemente wächst und die Laufzeit – mit Ausnahmen beim Rehashing – konstant ist.

³ Leider kann man in BlueJ weiterhin Objekte der Klasse auf die Objektleiste ziehen und mit der „Inspizieren“-Funktion die privaten Attribute einsehen. Dies ist aber nicht Sinn der Aufgabe und sollte unterbunden werden.

Unterrichtsverlauf: Herunterladen [odt][187 KB]

Weiter zu DS 4: ADT Stack