Für Programmieraufgaben gibt es ja nicht nur eine Lösung. Aber wie bunt die Lösungswelt ist, ist andererseits auch nicht ganz klar. Deshalb würde ich mich freuen, wenn Sie mitmachen würden bei der Sammlung von Lösungen.
Zu einem kleinen Programmierproblem möchte ich Lösungen in Form einer kleinen Bilderausstellung veröffentlichen. Dann können wir darüber diskutieren. Allerdings geht es mir nicht um Quellcode, sondern um visuelle Lösungen.
Ich suche Lösungen zum Problem “Ordered Jobs” in Form von Flow-Designs.
Datenflüsse sollen im Mittelpunkt stehen. Aber wer die mit weiteren Bildern garnieren möchte, ist dazu herzlich eingeladen.
Die Ausdrucksmittel des Flow-Designs habe ich in vielen Publikationen beschrieben und über die Jahre verfeinert. Leider bin ich noch nicht dazu gekommen, einen aktuellen Stand an einem Ort zusammenzufassen. Mea culpa. Aber es gibt einen Spickzettel, der größtenteils aktuell ist und die Notation knapp beschreibt. Alternativ beschreiben einige Artikel unter der Überschritz “OOP as if you meant it” nochmal in Kürze meine aktuelle Sicht zu Flow-Design.
Wer mitmachen will, schreibt am besten einen Kommentar zu diesem Artikel mit einem Link zu einem PDF mit seinem Entwurf. Oder es können Links zu yuml.me Grafiken sein; mit den Aktivitätsdiagrammen kann man Flow-Designs recht ordentlich beschreiben. Oder schicken Sie mir eine Email mit einem PDF.
Am Ende bastle ich dann eine Zusammenschau mit ein paar Anmerkungen zu dem, was mir auffällt. Und ich lege auch meine Vorstellung von einer Lösung vor. Dann gibt es eine “Ausstellungseröffnung” hier im Blog :-)
Zu gewinnen gibt es nichts – außer Erkenntnissen.
Wer macht mit? Einsendeschluss ist der 30.11.2013.
Ich bin gespannt auf die Vielfalt der Lösungsansätze.
Und hier nun die Aufgabe in epischer Länge. Sie ist auch im Fundus der Programmier-Katas der CCD School zu finden.
9 Kommentare:
Meinen Ansatz gibt es hier:
http://www.agile-is-limit.de/flow-layout-kurze-retrospektive/
Mein Lösungsansatz
Meine Lösung
Ich persönlich finde es am zweckmäßigsten, ein Flow-Design für eine derartige Aufgabe auf folgendem Abstraktionsgrad zu halten:
https://drive.google.com/file/d/0Bx4hkjB8UXNEWGNPQVl3OVczNU0/edit?usp=sharing
Das dürfte so ziemlich eines der einfachsten Designs sein, die man sich zu dieser Aufgabe denken kann.
Sollte man das noch weiter runterbrechen? M.E. nicht mit Datenflussmitteln. Flow Design habe ich nicht als Mittel dazu verstanden, irgendwelche Elementaralgorithmen für abstrakte Datentypen zu beschreiben.
Mein Implementierungsvorschlag zu dem Problem lautet: Verwendung eines Datentypen für azyklische gerichtete Graphen, incl. Bildung der transitiven Hülle. Bei der Registrierung werden dem Graphen Knoten und/oder Kanten hinzugefügt und jeweils der transitve Abschluss gebildet. Zur Sortierung komplettiert man den Graphen temporär schrittweise durch Registrierung von Job-Paaren, deren Reihenfolge bis dahin noch nicht feststeht.
Sprich, wenn man einen solchen Datentypen verwendet, ist das Problem hinreichend einfach zu lösen, dass eine weitere Verfeinerung nicht notwendig zu sein scheint.
@Michael
Das ist mir zu einfach. Das liefert keinen Mehrwert oder neue Erkenntnisse. Extrem gesagt, da ist kein nutzen.
Zum Beispiel die StringCalculator Kata:
-{string}->(Calculate)-{int}->
Schön, einfach, gut – eine Zelle, eine FU.
Aber was nützt es ?? Ich bin nicht schlauer als vorher.
-{string}->(Calculate:-{string}->(split)-{string*}->(sum)-{int}->)-{int}->
|
Delimiter
Hier hab ich Mehrwert, da gibt es Trennzeichen die verwendet werden, um zu spalten und dann zu summieren.
Ist es die einzige Möglichkeit: NEIN
Aber nun gibt es eine Diskussionsgrundlage, visuell ohne Code.
Aus deinem Text ziehe ich mindestens den Datentyp – azyklischer Graph. Den nennst du selbst als Grundlage. Gehört dieser dann nicht in deine Grafik? Auf die Idee kommt nicht jeder und wenn diese Idee visualisiert ist, dann kann man diskutieren.
@JuergenRB: wenn man nur einen Hammer hat, fängt irgendwann jedes Problem an, wie ein Nagel auszusehen ;-) Sprich, wenn man hier zur Verfeinerung unbedingt Flow-Design anwenden will, findet man sicher einen Weg, es für dieses Problem zu tun. Ob das besonders sinnvoll ist, darüber kann man sicher geteilter Meinung sein.
Meine bevorzugte Vorgehensweise, die ich oben im Text nur angedeutet habe, wäre die:
- abstrakten Datentyp für gerichteten Graphen definieren (z.B. als Interface und Beschreibung des Kontrakts)
- die Operationen "Register" und "Sort" als Pseudocode beschreiben
Man kann sich sicher überlegen, ob es sich lohnt, den "gerichteten Graphen" als eigene FU zu modellieren, intern von SortJobs. Dann braucht man noch mindestens zwei FUs, die die Operationen "Register" und "Sort" auf den gerichteten Graphen mappen. Für mich geht das aber stark in Richtung "Overengineering". Ich schau mal, vielleicht mach ich' es zu Übungszwecken trotzdem mal.
So, jetzt hab' ich JuergenRB's Vorschlag aufgegriffen und die "Internas" meiner Lösung modelliert:
https://drive.google.com/file/d/0Bx4hkjB8UXNEckd5cVVmeGZHdEE/edit?usp=sharing
Aber bringt das jetzt den Nutzen? Ich finde - nicht wirklich. Ich denke, so ein Bild versteht man nämlich nicht mehr - ohne eine vernünftige verbale Beschreibung verwirrt das mehr, als das es das Verständnis fördert. Da bleib ich doch lieber bei der Beschreibungsform, die ich oben skizziert hatte.
Nachdem das obige (im Übrigen auf dem Level unnvollständige) Bild hoffentlich gezeigt hat, wie man FD besser nicht verwenden sollte, hier nochmal ein Modell, welches den gerichteten Graphen ins Modell bringt, ohne FD zu "missbrauchen"):
https://drive.google.com/file/d/0Bx4hkjB8UXNETV8wLTNUTzVXM3c/edit?usp=sharing
Das gefällt mir jetzt schon besser. Die wesentlichen Komponenten sind zu sehen, das Modell ist trotzdem auf einem Abstraktionsgrad geblieben, bei dem es noch "einfach" ist. Ich habe meinen Entwurf zudem auch noch so abgeändert, dass ich "DGraph" als unveränderliche (immutable) Komponente konzipiert habe. Das Bilden des "transitiven Abschlusses" kann hier irgendwo intern in "SortJobs" passieren, oder auch im DGraph, oder als zusätzliche FU innerhalb von SortJobs, das hab' ich zu diesem Zeitpunkt erst mal offen gelassen.
Ich habe hier bewusst nicht versucht, "mit Gewalt" den Lösungsalgorithmus ins Modell zu pressen. Auch das Fehlerverhalten bzw. die Stelle, an der Zyklen erkannt werden, wollte ich an dieser Stelle nicht modellieren.
Ein vollständiger Entwurf kommt meines Erachtens trotzdem hier nicht ohne verbale Beschreibung aus - was da intern bei "Register" und "Sort" passiert, wie der "DGraph" dann verwendet wird, da steckt die eigentliche Essenz der Lösung. Und um diese Details das rüberzubringen, dafür scheint mir FD nicht das richtige Mittel der Wahl.
Ich habe mal Michaels kompliziertere Lösung genommen und etwas abgeändert und dabei gleich mal yuml.me getestet.Hier der Flow
Diese Darstellung könnte auch als Verallgemeinerung meiner eigenen durchgehen - was für ein Zufall :)
Sort - sortiert oder gibt die sortierten Jobs aus - ob der Graph schon sortiert ist oder erst wird - egal
AddNode - fügt einen neuen Job hinzu
AddEdge - fügt abhängige Jobs hinzu
Wie genau nun hinzugefügt wird und ob dann gleich oder später sortiert wird oder Hüllen gebildet werden - egal.
Aber man sieht,dass alle FUs auf dieselben Daten(Graph/Customtyp/Dictionary... auch egal- wichtig ist nur das die Informationen Node/Edge nicht verloren gehen) zugreifen.
Und wir haben eine Grundstruktur, die so bei allen Lösungen bisher vorkam.
(oder?!)
Kommentar veröffentlichen