Disclaimer: Dieser Thread wurde aus dem alten Forum importiert. Daher werden eventuell nicht alle Formatierungen richtig angezeigt. Der ursprüngliche Thread beginnt im zweiten Post dieses Threads.
Aufgabe 7.4: LCS
Hallo miteinander,
ich versuche gerade die methode “longestCommonSubsequenceExchanger” zu implementieren.
leider ist mir der umgang mit dem Exchanger nicht vertraut, ich habe eine Implementierung gemacht wo ich dachte so müsste es funktionieren laut API, aber ich wurde eines besseren belehrt.
Kann mir jemand den genauer erklären und worauf ich da achten sollte?
Außerdem: meine sequentielle implementrierung funktioniert… kann ich die selbe implementierung bei “longestCommonSubsequenceExchanger” auch nutzen mit eben kleinen veränderungen für den einsatz des Exchanger, oder muss ich die implementierung komplett umstellen damit das klappt?
Danke! 
Ich hab eine Frage zur Aufgabenstellung:
Soll das heißen, es reicht die Ziffern parallel in die Matrix zu schreiben?
Das auslesen des längsten Strings kann dann wieder sequentiell - z.B. mit der in der vorherigen Teilaufgabe geschriebenen Methode
[m]public char readMatrix(int matrix, char x, char y)[/m] geschehen?
Etwa nach einem [m]join()[/m]
1 Like
Ich habe auch meine Probleme mit dem Exchanger. Ich habe es so verstanden, dass exchange() die Matrizen von zwei Threads tauscht. Aber was bringt es einem, wenn Thread2 nun weiterarbeiten kann, da er die befuellte Matrix von Thread1 hat, aber Thread1 z.B. eine Zeile weiter unten nicht weiterarbeiten kann, da die eben teilweise von ihm befuellte Zeile nun leer ist, da er mit Thread2 die Matrix getauscht hat?
Benoetigt man eigentlich nur einen Exchanger oder mehrere, da einer ja eigentlich nur fuer zwei Threads gedacht ist und mir nicht klar ist, wie ich mit einem Exchanger mehrere Threads korrekt synchronisieren kann?
Also in meiner Implementierung tauschen die beiden Exchanger nix (sinvolles) aus! [m]exchanger.exchange(null);[/m]
Der Exchanger wird (bei mir) nur als Synchronisationspunkt verwendet. Die Matrix ist global für alle verfügbar, jeder Thread arbeitet auf seinem Teilbereich. Der Exchanger teilt lediglich mit, dass der Wert, den der nachfolgende Thread benötigt nun bereit steht.
Bei mir hat jeder Thread einen [m]Exchanger eingang[/m], und einen [m]Exchanger ausgang[/m]. Wobei der der Ausgang beim anschließenden Thread dem Eingang entspricht.
Bei dem ersten und letzten Thread muss man natürlich aufpassen, da es hier keinen Eingang, bzw Ausgang gibt!
Und das Auslesen des Ergebnisstrings mach ich nun sequentiell, so wie oben in meinem Post angedeutet 
Ungenau Aufgabenstellung halt…
1 Like
Danke fuer die Antwort mmuuuuhh!
Dem Exchanger [m]null[/m] zu uebergeben klingt gut 
Edit: Was ist zu tun, wenn die Testcases durchlaufen, EST aber ein Ausrufezeichen anzeigt? Soll ich das Programm im Huber-CIP ausprobieren, um zu schauen, ob dort vllt ein Testcase fehlschlaegt?
Danke erstmal an mmuuuuhh.
In den Tafelübung hatte ich den Eindruck, dass es verlangt ist, denn zuvor berrechneten Wert zu übergeben. Das klappte bei mir auch nicht so recht. Aber den Exchanger als Barrier zu missbrauchen ist wohl die bessere Idee
sollten wir das Füllen der Matrix rekursiv oder iterativ implementieren?
Kann ich davon ausgehen, dass ich bei der BlockingQueue einfach dummy-Objekte übergebe?
Ob rekursiv oder iterativ, ist erst einmal egal. Wobei eine der beiden Vorgehensweisen wohl ziemlich schmerzhaft zu implementieren sein dürfte. 
Sowohl der Exchanger als auch die BlockingQueue sorgen dafür, dass vor dem blockierenden Aufruf geschriebene Werte nach dem blockierenden Aufruf in anderen, an diesem Aufruf teilnehmenden Threads sichtbar sind (siehe Abschnitt zu „Memory Consistency Effects“ in der Java-API-Dokumentation). Das heißt, dass man in beiden Dummy-Objekte verwenden kann, da die Matrixeinträge nach dem [m]exchange()[/m] / [m]take()[/m] sichtbar sind.
also ich hab das rekursiv implementiert und es war auch relativ schmerzhaft.
Was mich wundert ist das bei Test5 meine Exchanger Variante länger als die Sequentielle braucht.
hier die Zeiten:
testSeq5: 0,084
testEx5: 0,144
testQueue5: 0,063
anbei habe ich noch einmal alle Zeiten als Bild angehängt
kann das so richtig sein?
für mich würde es Sinn machen, dass die Exchanger Methode länger dauert, weil ja nach jeder Zeile gewartet wird.
Attachment:
times_lcs.png: https://fsi.cs.fau.de/unb-attachments/post_132368/times_lcs.png
Bei mir sieht es anders aus. Vielleicht kann sich das ja jemand erklären.
Ich hänge mal meine Zeiten als Anhang ran:
Attachment:
lcs_test.png: https://fsi.cs.fau.de/unb-attachments/post_132372/lcs_test.png
Für eine sinnvolle Zeitmessung sind die Beispiele zu klein.
Ihr könnt euch ja selber welche schreiben ;).
noch eine kurze Frage: Kann ich z.B. in der readMatrix() davon ausgehen,
dass an x[0] bzw. y[0] ein nicht relevantes zeichen steht (z.B. ‘/’ wie in der Uebung),
oder steht dort der erste Char der sequence?
Der erste char.
Kannst ja auch mal in die TestCases schaun, was dir übergeben wird
1 Like
Ich bin zur Zeit noch am rein sequentiellen Part und habe ein Problem:
Bei den Testfällen
… <MJAU[]> but was:<MJAU[
… <HMAN[]> but was:<HMAN[
… <GTCGTCGGAAGCCGGCCGAA[]> but was:<GTCGTCGGAAGCCGGCCGAA[
… <[HLL]> but was:<[LL
… expected <2481> but was: <2484>
Wie kommen die eckigen Klammern bei den ersten Testcases zustande? Ich kann leider auch in meinem Code keinen Grund dafür erkennen, weshalb der ursprünglich letzte Character im vierten Testcase nicht erkannt wird (was auch für den Fehler in (V) sorgen dürfte). Hat zufällig jemand eine Idee?
Du hast ein oder mehrere Zeichen am Ende zu viel. Ein return vielleicht?
edit:
Die eckigen Klammern fügt Junit ein um den Unterschied zu verdeutlichen.
Vielen Dank, das erledigt schon einmal alle Probleme bis auf (4) - ich dachte, die maximale Länge des Arrays wäre für die JUnit-Tests egal. Hier werden konkret HALLO und HOLLA verglichen; füge ich einen Buchstaben vor “HALLO” hinzu, so wird der Testcase bestanden. Keinen Unterschied macht es, wenn ich den Buchstaben stattdessen vor HOLLA hinzufüge. X wird aber eigentlich überall mit 0 initialisiert, d.h. es sollte hier keinen Unterschied geben.
Habe ein problem bei longestCommonSubsequenceQueue:
es funktioniert alles super, nur wenn “threads” 4 oder kleiner ist, bleibt er bei einem exchangerX.exchange(null); hängen.
ich arbeite linear, mit einem fixedThreadpool und immer der gleichen Anzahl an Runnable objekten, die ich einsetze (5)…
zu “Kommunikation” benutze ich 4 Exchanger.
jemand eine Ahnung?
liegt das am Threadpool? 
Würde mal vermuten da findet einer der Threads seinen Partner im Exchanger nicht? zB 5 runnables, t1 schnappt sich r1 und hängt beim out exchanger. Wenn jetzt von den anderen 3 Threads keiner r2 zugewiesen wird um mit r1(t1) zu kommunizieren, wars das mit dem Programm.
Oder werden die runnables garantiert in der Erstellungs-/Submit-Reihenfolge abgearbeitet? Denke nicht.
Versuchs mal mit einer manuellen Aufteilung auf die Threads (wie zB bei der Picasso damals).
Hi Leute,
Kann mir jemand sagen, warum bei meinem Exchanger manchmal das richtige Ergebnis kommt, und manchmal nicht?
Ich erzeuge in meine Thread array ein neues Runnable Objekt, dass als Exchanger input den Output Exchanger des vorherigen Objektes hat, die Run Methode berechnet den Matrix-Part, der dem Thread zugewisen ist, und ruft dann den Exchanger auf.