Probleme mit output
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 8.4
Hallo,
ich habe ein Problem bei der CountingSort. In der sort()-Methode erstelle ich ein Byte-Array output, dass ich den einzelnen Threads übergebe und in das die Threads die Werte eintragen.
Am Ende möchte ich output zurückgeben, allerdings lese ich da ein veraltetes Array (mit teilweise uninitialisierten Werten). Output als volatile zu deklarieren bringt in diesem Fall ja auch nichts… wie schaffe ich es die aktuellen Werte dieses Arrays auszulesen?
Ich habe versucht, mir innerhalb der SortingRunnable-Klasse ein internes AtomicReferenceArray anzulegen, in dem ich zuerst die Werte speichere und es dann am Ende nach output kopiere, aber da habe ich das gleiche Problem.
Irgendwie stehe ich gerade auf dem Schlauch 
Hast du join auf allen Threads aufgerufen (außer natürlich auf dem Hauptthread)?
Bei funzt das auch ohne irgendwelche sichbarkeitsoperationen (join sollte denk ich dafür sorgen, dass der Hauptthread die ergebnisse der Threads bekommt)
Vielen Dank, Problem gelöst: Am join lag es nicht, sondern daran, dass ich ein barrier.await vergessen habe…
Ich versteh das alles nicht ganz. Man übergibt den Runnables beispielsweise “output” und da sollen sie das Ergebniss reinschreiben. Aber in Java geschieht das ganze Zeug mit den Funktionsparametern doch über Call by Value und nicht über Call by Reference. Das kann doch so gar nicht funktionieren, oder was hab ich verpasst?
//Edit: Hab doch noch gecheckt 
"Byte[] ist ja kein primitiver Datentyparray, sondern ein Array aus Objekten.
Grüße.
Kann mir mal bitte jemand erklären, was writing genau machen soll, oder besser, was unter prefix_i,j entspricht dem Index … bedeuten soll???
Mir ist auch nicht so ganz klar, wie ich das in writing() machen soll bzw. was ich da wirklich tun soll.
Bei folgendem Input ( {0, 1, 0, 1, 0, 1, 0, 2}), 3 Threads, sequentialPrefix und der Threadaufteilung [0,2), [2,4), [4,8) ergibt sich in meinem counts- und prefixes-Array folgendes:
counts dürfte ja so richtig sein und der Rest ist ja schon vorimplementiert, da die sequentielle Variante verwendet wird.
Mit den Werten in prefixes weiß ich jetzt aber nicht so recht umzugehen. Für mich sind die Einträge, die Thread 0 sieht, die einzig “richtigen”, weil ja von output[0] bis [3] "0"en kommen, von [4] bis [6] "1"en und in [7] eine “2”. Jetzt ist es aber nicht Sinn der Sache, dass ich Thread0 die ganze Arbeit machen lasse. Was also sollen die anderen Threads tun? Beispielsweise weiß doch Thread2 gar nicht, bis wohin "0"en eingetragen müssen, weil er nur “weiß”, dass sie spätestens ab output[6] stehen.
Die Idee ist dieselbe wie bei der counting Methode. Jeder Thread läuft erneut über seinen Zahlenbereich und liest die Eingangszeichen. In prefixes kann jeder Thread nachsehen an welche Stelle er diese Ziffer als nächstes schreiben muss.
Es geht also nicht darum nacheinander die vorkommenden Zahlen zu schreiben, sondern parallel die Zeichen aus dem Eingangsarray an die richtige Stelle des Ausgangsarrays zu übertragen.
Danke! So hat es jetzt auf Anhieb funktioniert. Wenn man sich ersteinmal die Wikipedia-Seite dazu durchgelesen hat, ist es schwer, umzudenken.
Naja, ich habe halt beispielsweise beim ersten TestCase das Problem, dass mein Array sortiert wird und die Nullen stehen dann auch vor den Einsen und wenn man sich die System.identityHaschCode’s von allen ausgeben wird, steht die Null ganz vorn und die 2 Null dahinter (also stabil sortiert), trotzdem schlägt beim TestCase immer das “if(expected != actual)” fehl, woran kann das liegen???
ich meine um das Array zu sortieren wird es ja erst mal im TestCase geklont, ist es dann nicht klar, dass die HashCodes nicht mehr stimmen???
Also ich lese die zu schreibenden Werte direkt aus dem Input-Array, dann klappt es mit der Identifikation.
Danke, jetzt klappt es, glaube ich ^^
Ich habe 2 Probleme mit der Aufgabe:
-
die [m]prefixesSequential()[/m] welche ja schon vorgegeben ist führt bei mir zu [m]IndexOutOfBoundsException[/m] in Zeile 96 weil columns immer bis 256 zählt… aber zB bei dem stable sort test sind doch nur 8 elemente im Array → nur 8 columns vorhanden… ist das ein fehler in der referenzimplementierung oder habe ich was falsch verstanden?
-
in dem [m]testRandomArrays()[/m] kommt es teilweise vor, dass auch negative Werte im Array stehen, was laut definition ja nicht erlaubt ist?
du meinst bis: (< 256)? ansonsten hast du da etwas rumgepfuscht 
this:
normalerweise: != Anzahl Elemente des Inputarrays.
Ja klar zählt es nur bis 255 =P
Hmm und was soll mir das jetzt sagen? Dass ich erstmal noch ne Maximumssuche vorher machen muss über mein input Array?
Wenn ich das zB beim stable sort test mache habe ich aber nur 2 Spalten, da 2 unterschiedliche Elemente? Mit anderen worten das geht noch weniger mit den <255? o.O
Und was ist mit den negativen Zahlen?
Dein Wertebereich ist ja durch den gegebenen Datentyp beschränkt(unabhängig vom übergebenen Array). Jetzt schau mal nach, wie groß der Wertebereich für den gegebenen Typ ist und überlege dir, ob es nicht ausreicht ein so großes Array zu erstellen(und möglicherweise wird dir dann auch klar, warum die sequentielle prefix-Methode bis 255 zählt ;)).
Und zu den negativen Zahlen: Da es keine negativen Indizes gibt und in Java aber alle Zahlen [m]signed[/m] sind, musst du dafür sorgen, dass die kleinste negative Zahl vielleicht an Index 0 liegt.