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.
5.6 ParallelRadixSort
Guten Morgen!
Ich hätte eine kurze Frage zur Bonusaufgabe 5.6 und würde gerne eure Meinung dazu hören:
Für die Bearbeitung der Teilaufgabe b), also bei der Implementierung der Methode
sortByPos(String array[], int n, int threads)habe ich mich dazu entschieden, in der Klasse ParallelRadixSortImpl eine statische innere Klasse zu erstellen, die von Thread erbt.
Diese dient dazu, die angeforderten n Threads zu realisieren. Für diese innere Klasse habe ich Konstruktor, run()-Methode,… implementiert.
Nun zur eigentlichen Frage:
Die in Teilaufgabe a) erstellte Methode
getBucket(String string, int n)ist nicht statisch, also eine Instanz-Methode. Diese Methode würde ich aber logischerweise in jeder run()-Methode benötigen.
Folglich bin ich pragmatisch an die Sache herangegangen und habe in der inneren Klasse eine Klassenvariable
private static ParallelRadixSort ...angelegt, die lediglich dazu dient, dass jeder Thread Zugriff auf eine Instanz von ParallelRadixSortImpl hat und somit getBucket() aufrufen kann.
Funktionieren tut dies soweit einwandfrei. Die Frage ist nur, ob dies erlaubt ist oder aus irgendwelchen Gründen unschön ist.
Alternativ habe ich mir auch überlegt, in der Klasse ParallelRadixSortImpl eine statische Implementierung von getBucket() vorzunehmen.
Wie seht ihr das? 
Vielen Dank für eure Antworten!
Erlaubt ist das schon, aber es gibt egtl. keinen Grund die Thread-Klasse statisch zu machen. Wenn du das static weglässt, kannst du auch auf die Methoden der umgebenden Klasse zugreifen.
Alternativ kannst du auch die ParallelRadixSort-Instanz im Konstruktor übergeben, wenn du unbedingt eine statische Klasse haben willst. Statische Felder sind aber eher unschön und sollte man vermeiden. Einerseits können hier Probleme entstehen, wenn man radixSort() aus unterschiedlichen Threads gleichzeitig aufrufen würde, andererseits können die Objekte, die in statischen Variablen gespeichert werden, nicht vom Garbage Collector bereinigt werden.
Ja. Habe die innere Klasse jetzt einfach non-static gemacht, also das static einfach weggenommen.
Hatte das nur so gemacht, weil ich bei einer anderen Aufgabe mal Probleme mit inneren nicht-statischen Methoden hatte…
Danke für die Antworten.
Jetzt gefällt mir meine Lösung noch besser 
Ich habe auch eine Frage zur Aufgabe. Bei mir funktionieren die Testfaelle soweit und ich bin mir auch sicher, dass ich parallel sortiere.
Mein Problem ist nur, dass der Test fuer vier Threads laenger braucht als der fuer einen. Also habe ich anscheinend sehr ineffizient programmiert. Gibt sowas Punktabzug oder eher nicht, da ich es geschafft habe, parallel zu sortieren, was ja der Aufgabe entspricht?
Hast du dir mal einen Test geschrieben der mehrere Millionen kleine Strings sortiert?
Der vorgegebene Test ist viel zu klein damit sich die Parallelisierung lohnt 
Ja, das habe ich probiert. Aber immer wenn ich das String array mit sehr vielen Strings initialisiere, kommt die Fehlermeldung: [m]the code for the static initializer is exceeding the 65535 bytes limit [/m]…
Hey,
hat jemand vielleicht einen Tipp wie die Buckets sinnvoll zu realisieren sind?
Ich hab schon alle möglichen Varianten von ArrayList<List>, Vector<Vector> etc probiert. Das Problem ist immer, dass ich es nicht hin bekomme 26 “Zellen” vorzudefinieren, an die ich dann die jeweiligen Elemente adden kann.
Probiers mal mit ArrayList[], das erzeugt dir ein Array aus ArrayLists, die Strings beinhalten. (Gibt bestimmt noch andere, kannst auch ne ArrayList aus ArrayLists machen, aber das wird dann etwas unübersichtlich)
1 Like
Danke für den Tipp!
Ich habs jetzt mit einer ArrayList<LinkedList> hinbekommen.
Das Sortieren klappt in 80% der Fälle, aber hin und wieder sind ein paar Strings vertauscht und der Testcase schlägt fehl.
Ich habe das Einfügen in die Buckets synchronized und außer diesem kommt es ja zu keinerlei Parallelität. Daher verstehe ich nicht bei welchem Schritt sich ein Fehler einschleichen kann. (Würde ein Logikfehler existieren, müsste ja jeder Durchlauf fehlschlagen)
Du musst in der Aufgabe eigentlich nichts synchronisieren.
mach dir lieber einen bucket pro thread
Bei mir klappt die Sortierung mit einem Thread, mit mehreren aber nicht… Ich vermute es liegt an meiner Implementierung der [m]buckets[/m]. Ich habe eine [m]ArrayList[/m] von [m]ArrayLists[/m] erstellt und übergebe jedem Thread diese Liste. In den Threads selber sehe ich nur noch nach, an welche Stelle ich das nächste Wort legen muss und füge es den [m]buckets[/m] hinzu. Danach folgt in der [m]sortByPos[/m] ein [m]join()[/m] der Threads. Ich bin jetzt nicht sicher, ob sich die buckets dann irgendwie gegenseitig überschreiben oder so.
Oder liegt es daran, dass es nicht stabil sortiert, wenn man das zu sortierende Array einfach aufteilt? Also, dass das erste Element von Thread1 angeschaut wird, das zweite von Thread2 usw…
Du hast vermutlich mehere Probleme:
-
Das sagt dir die Java-API über Array-Lists: Note that this implementation is not synchronized
Wenn du also Array-Lists über mehrere Threads hinweg verwendest, solltest du dir gut überlegen, was du tust. -
Selbst wenn du eine threadsichere Liste verwenden würdest, dann hättest du das Problem, dass es beim Radix-Sort zur Sortierung durchaus darauf ankommt, in welcher Reihenfolge die Threads ihre Elemente sortieren:
Nehmen wir folgende nach der zweiten Stelle sortierten Zahlen:
21 12 24 15 17 27
Die roten Zahlen werden von Thread 1 sortiert, die blauen von Thread 2.
Wenn nun beide Threads gemeinsame Buckets verwenden, dann kannst du nicht sicher stellen, dass am Ende in den Buckets nicht folgende Aufteilung vorliegt:
1 2
15 27
17 [color=crimson]21
12[/color] 24
Und das ist alles andere als korrekt sortiert. Der Radix-Sort lebt davon, dass die einzelnen Buckets nacheinander ausgelesen werden und die einzelnen Elemente nacheinander abgearbeitet werden.
Das bedeutet zum einen, dass globale Buckets schwer zu verwenden sind, weil du nicht verhindern kannst, dass ein Thread Zahlen, welche erst später bearbeitet werden sollen, schon voher einsortiert. Und gleichzeitig bedeutet es auch, dass deine Aufteilung zusammenhängend sein sollte und nicht jeder Thread nur jedes n-te Element machen sollte.
Man kann den RadixSort parallelisieren, aber damit danach auch noch sortiert wird, muss man sich genau überlegen, welche Aufteilung man wählt und wie die Buckets umgesetzt werden sollten. Sonst fliegt einem das Ganze schnell um die Ohren ;).
1 Like
[quote=[hedgehogs dilemma = 42]]
mach dir lieber einen bucket pro thread
[/quote]
meinst du, dass man sich ein array mit “threads” vielen (z.B.) ArrayList<LinkedList> erstellt? Wie stellt
man das denn an? Eclipse meckert immer, wenn ich so ein Array erstellen will von wegen generic und so.
Würde mich über Hilfe freuen, ich häng da echt grad ganz schön.
@SuppressWarnings(„unchecked“)
ArrayList foo = (ArrayList) new ArrayList[42];
sehr schön, das hilft mir schon mal weiter. dankeschön!
@SuppressWarnings(“unchecked”)
ArrayList foo[][] = (ArrayList[]) new ArrayList[42][42];
wenn ich mir ein 2 dimensionales Array (siehe oben) erstelle und .size() oder .add() aufrufe an der Stelle foo[0][4].size() zum Beispiel, wirft er mir eine NullPointerExeptcion um die Ohren. Und ich verstehe nicht was ich falsch mache… 
!!!
Du hast dir zwar ein Array erstellt, aber noch sind deine ganzen ArrayLists ja mit null vor initialisiert. D.h. bevor du auf eine Liste zugreifen kannst, musst du die konkrete Liste mit [m]new ArrayList()[/m] initialisieren.
Also entweder einmal über das 2D-Array drüber laufen und alle ArrayListen erstmalig erzeugen, oder beim erstmaligen Verwenden, eine neue Instanz an der entsprechenden Stelle erstellen.
Mit ner 2D-ArrayList hab ichs nun endlich hinbekommen. Danke fuer die hilfreichen Ratschlaege hier im Forum und in der Uebung