Lehrzeit

Schule & Informatik

Prioritätswarteschlange – Teil 2

Im nächsten Teil soll es jetzt um das Umsetzen der Prioritätwarteschlange mit Hilfe Strategie-Entwurfmusters gehen. Wer dieses Entwurfmuster noch nicht kennt, kann sich zunächst mal auf der Internetseite von Philipp Hauer  die Beschreibung mal durchlesen. Anschließend gibt vielleicht noch den folgenden Film bei youtube und man ist fit…

…. dachte ich zumindest. Ich musste aber merken, dass das nicht so einfach ist und ohne eine fast vollständige Neuprogrammierung nicht mit der bestehende Datenstruktur zu machen ist.

Im Moment sieht mein Projekt so aus:

Bildschirmfoto 2014-12-07 um 12.30.55

Oben rechts kann man das Interface I_Append erkennen, von dem ich die zwei speziellen Varianten bzw. Strategien NormalQueueBehaviour und PriorityQueueBehaviour abgeleitet habe. Aber wem gebe ich jetzt diese Information? Den Listenelementen? Macht eigentlich Sinn. Diese bekommen ein Attribut I_Append einfuegeStrategie, wobei die Strategie dann passend zur Warteschlange angepasst wird.

Da sich weiter Abschluss und Knoten unterschiedlich verhalten müssen, sollte man die Strategien noch nach weiter aufteilen:

NormalQueueBehaviour_Abschluss, NormalQueueBehaviour_Knoten

PriorityQueueBehaviour_Abschluss, PriorityQueueBehaviour_Knoten

Da die Behaviour-Klassen aber nicht auf die Attribute von Knoten und Abschluss zugreifen können, muss die append-Methode die jeweiligen Knoten als Parameter bekommen. Das hat dann bei mir zu folgenden fehlerhaften Ansatz geführt:

public class PriorityQueueBehaviour implements I_Append {
    public void append(
        Listenelement prevListenlenlement,
        Listenelement curListenlenlement, 
        Listenelement nextListenelement, 
        Inhalt neuerInhalt, 
        int priority) {
            Listenelement neuerKnoten = new Knoten(neuerInhalt,priority);
            if (nextListenelement == null) { //Der Abschluss hat keinen Nachfolger
                prevListenlenlement = neuerKnoten; //da first übergeben wurde
            } else { //Ich bin in einem Knoten
               int nextPriority = nextListenelement.getPriority(); 
               if (priority <= nextPriority) { 
                   //Ein neuer Knoten muss eingefügt werden
                   neuerKnoten.setNext(nextListenelement);
                   curListenlenlement.setNext(neuerKnoten);
                } else {
                    //Aufruf an next weitergeben.                
                    nextListenelement.append(prevListenlenlement, neuerInhalt, priority, this); //this gibt die Einfuegestrategie weiter
                }                                                
            }
    }
}

Da die Informationen aber perValue und nicht perReferenz übergeben werden, funktionieren die Zuweisungen der Form

curListenlenlement.setNext(neuerKnoten);

zum Beispiel nicht.

Ein neuer Ansatz ist aus meiner Sicht, dass ich zum einen die Liste als doppeltverkettete Liste implementiere und so von jedem Knoten auf den Vorgänger und Nachfolger zugreifen kann. Und zum zweiten werde ich nur die Vergleichsfunktion als Strategie umsetzen und nicht den ganzen Einfüge-Ablauf.

Wenn ich Zeit finde, werde ich das noch umsetzen. Ich werde das Zusammen mit den Generics dann umsetzen.

5 Kommentare

  1. Hallo Ingo*,

    ich weiß nicht so genau, was dein Ziel bei diesem Projekt ist…

    Nur zur Sicherheit: Weißt du, dass es seit Java 7 eine PriorityQueue-Klasse gibt? Du bzw. deine Schüler könnten also einfach diese verwenden, falls gewünscht. Du kannst dabei entweder die natürliche
    Sortierung der gespeicherten Objekte verwenden (d.h. falls Comparable implementiert ist) oder einen Comparator übergeben, der die Reihenfolge festlegt. Intern ist das implementiert als Heap, sollte also im Normalfall wesentlich effizienter sein, als eine Liste sortiert zu halten.

    In deinem Fall hättest du also eine PriorityQueue und einen Comparator (oder du lässt Wunsch das Interface Comparable implementieren). Ich würde im Normalfall immer für den Comparator plädieren, denn dann kannst du, je nach Anwendung, mal so, mal anders sortieren.

    Recht anschaulich gezeigt wird der Umgang mit PriorityQueue z.B. hier: http://openbook.galileo-press.de/java7/1507_03_005.html#dodtpd56ab822-a743-4232-90a2-f78fbe044ef5

    P.S. Ehrlich gesagt: Beim Anblick des UML-Diagramms bekomme ich Angst!

    *Ich beende hiermit mal meine einjährige allgemeine Blog-Abstinenz!

    • Oh, ich sehe gerade, dass da etwas unterschlagen wurde, nämlich die spitzen Klammern bzw. Größer-/Kleinerzeichen mit den Generics. Liegt wohl daran, dass das für WordPress aussieht wie unsinniges HTML. Ich versuch’s also nochmal, diesmal ausnahmsweise mit runden Klammern – bitte ersetzen:

      „In deinem Fall hättest du also eine PriorityQueue(Wunsch) und einen Comparator(Wunsch) (oder du lässt Wunsch das Interface Comparable(Wunsch) implementieren).“

    • Danke für den Hinweis. Aber es war mir natürlich bekannt, dass Java solche Datenstrukturen schon mitgibt. Das Ziel dieses Projekts war auch etwas anderes: Die Schüler müssen ja das Implementieren von Warteschlangen und Stacks mit dem Kompositum-Muster lernen – was ich im Übrigen für völligen Käse halte. Da ist es dann nur noch ein kleiner Schritt zum Ausbau Warteschlange zur Prioritätwarteschlange.
      Ich fänd es sinnvoller in 11/1 erstmal nur einfach/doppelte verkettete Listen zu machen und in 11/2 dann Graphen und Bäume mit dem Kompositum. Dann hätte ich auch mehr Zeit die Leistungsstärken der Schüler ein wenig auszugleichen.

      • Ja, so hatte ich mir das auch gedacht. Ich falle ja nur immer aus allen Wolken, was ihr in Bayern da so alles machen dürft/sollt. Das sind ganz normale 11. Gymnasialklassen im naturwissenschaftlichen Zug, oder? Wahnsinn! Wie lange programmieren die schon? Sind das alle oder nur besonders Intereressierte?

        Auch, dass ihr offensichtlich Design Patterns derart breit thematisiert und einsetzt, verblüfft mich. Ich habe bei den meisten Schülern das Gefühl, dass diese Art von Abstraktion weit, weit über das hinausgeht, was sie leisten können. (Aber ich habe auch eine andere Schülerklientel.) Aber ich finde das natürlich super! Auf das einzelnen Pattern käme es mir dabei gar nicht so sehr an: entscheidend ist zu begreifen, was für eine mächtige Idee die *Polymorphie* ist.

        Übrigens: Viele der klassischen Design Patterns sind jetzt mit Java 8 wenn nicht überholt, so doch grundsätzlich umgekrempelt worden. Gerade solche Sachen wie Strategy oder Command sind ja eigentlich nichts anderes als der Ersatz für „Funktionen als Parameter/Variablen“ (first-class functions). Dieses Manko ist ist mit den Lambda-Ausdrücken und Methoden-Referenzen beseitigt worden. Ich brauche kein spezielles Pattern mehr, wenn ich einfach eine Referenz auf diejenige append-Methode übergeben kann, die ich verwenden will!

        Mal sehen: Ihr glücklichen Bayern werdet das bestimmt bald unterrichten. Hier in BW wird am Gymnasium stattdessen die Informatik endgültig abgeschafft und durch „Medienkompetenz“ ersetzt werden. Ich am *beruflichen* (aber nicht technischen) Gymnasium darf noch ein bisschen weitermachen mit dem, was die BWLer unter Informatik verstehen… (Ende rant. Wo hatte der eigentlich angefangen?)

        • Die Schüler haben in der Oberstufe quasi die Wahl zwischen Bio/Chemie/Physik/Informatik, wobei die Informatik leider nicht als voller Ersatz einer Naturwissenschaft dasteht. Wer Informatik wählt, ist also besonders interessiert, oder besonders wenig interessiert an den Alternativen.

          Entwurfsmuster: Ich glaube auch, dass das Kompositum bei den Listen oder Bäumen nicht sehr zum Verständnis von Patterns beiträgt. Ein einfacher Adapter, MVC, und ganz vielleicht Listener, das bringt dann später im Projekt eher etwas.

          Medienkompetenz, ich weiß. Traurig.

Schreibe einen Kommentar

Deine E-Mail-Adresse wird nicht veröffentlicht.

*

© 2016 Lehrzeit

Theme von Anders NorénHoch ↑