SWT[4]#4

[Thomas]

bei der klasse mit der ihr parallel sortiert erweitert man doch threads oda? und zum sortieren nutzt man natürlich die methoden aus der sequentiellen implementierung z.b. mergeSort() welche das array rekursiv immer in 2 hälften teilt und am schluss dann merge aufruft. wenn ich das jetzt parallelisiere müsste ich ja in run mergesort aufrufen mit einem der subarrays, run kann ich ja aber gar keine parameter übergeben, also müsste ich statische array benutzen. ich kann ja aber in run() nur ein parameter benutzen für mergesort. oder lieg ich da ganz falsch und man muss das alles anders aufteilen?
zum thema schablonenmethode: würde ich auch so machen wie silent, man muss aba nicht auch noch ne möglichkeit einbauen um die sortiermethode zu wechseln oda?

[Tankwart]

zum thema schablonenmethode: würde ich auch so machen wie silent, man muss aba nicht auch noch ne möglichkeit einbauen um die sortiermethode zu wechseln oda?

Ne.

Eine Wahlmöglichkeit ist nicht nötig. Sie können es fest verdrahten.
Wenn Sie es dennoch wünschen, können Sie es über einen
Kommandozeilenparameter lösen.

(Mail)

Zum Ersten leider keine Ahnung, bin auch noch am rumrätseln.

[|silent]

bei der klasse mit der ihr parallel sortiert erweitert man doch threads oda? und zum sortieren nutzt man natürlich die methoden aus der sequentiellen implementierung z.b. mergeSort() welche das array rekursiv immer in 2 hälften teilt und am schluss dann merge aufruft.

richtig, also du teilst beim ersten Aufruf deiner Parallel-Methode (also MSPaeallel.sort(...)) in zwei ca. gleichgroße Arrays. Ich hab' da einfach zwei neue Arrays mittels System.arraycopy(); erstellt. Danach habe ich mir die Thread-Methode implementiert, die mir dann mit dem ersten Thread arrayleft und mit dem zweiten Thread arrayright sortiert. Jeweils mit dem rekursiven Algorithmus den wir aus Algo haben. Jetzt häng ich nur grad am letzten Schritt. Ist das richtig, dass ich dann einfach nachdem die Threads fertig sind, nochmals mergeSort() ausführen muss?

Wann weiss ich, ob die Threads fertig sind?

wenn ich das jetzt parallelisiere müsste ich ja in run mergesort aufrufen mit einem der subarrays, run kann ich ja aber gar keine parameter übergeben, also müsste ich statische array benutzen. ich kann ja aber in run() nur ein parameter benutzen für mergesort. oder lieg ich da ganz falsch und man muss das alles anders aufteilen?
zum thema schablonenmethode: würde ich auch so machen wie silent, man muss aba nicht auch noch ne möglichkeit einbauen um die sortiermethode zu wechseln oda?

du musst dem run keine Parameter übergeben, du kannst ja direkt in der run eine Funktion/Methode aufrufen oder direkt Quellcode eingeben, das wird dann ausgeführt. Sprich: du brauchst nur zwei Threads, das entspricht ja gerade meinem angehängten Bild.

[Baloo]

also das mit der Schablonenschnittstelle ist mir auch noch ein Rätsel. Ich denke aber, dass es einfach so gedacht ist, dass man eine abstrakte Klasse (bei mir "MergeSort") hat, von der die konkreten Klassen "MergeSortParallel" und "MergeSortSequentiell" erben. "MergeSort" hat als Methode nur "sort(int[] seq, int from, int to)", diese ruft wiederum eine Methode in der Unterklasse auf. Laut Aufgabenstellung soll das ja standardmäßig der Parallel-Algorithmus sein.

Wenn ich das richtig verstehe, willst du Referenzen auf die zwei Kindklassen in der Elternklasse haben. Klingt für mich irgendwie en bisschen komisch wobei ich dir zustimmen muss, dass das sowohl die Anforderungen der Schablonenmethode als auch die Aufruf anforderungen erfüllt.
Ich glaube aber das mit letzterem eher die Main Klasse gemeint ist. Sprich so: Starte die Jar, les ein Array ein, starte Standardmäßig die Parallele Sortierung. Vlt über Programmparameter die andere... Das wäre einfach (<10 Zeilen) und man erfüllt alle Wünsche. (Okay Tankwart war schneller)

Nur weiß ich selber nicht, ob es in Ordnung ist, wenn ich in meiner Main-Klasse folgendes mache (da ich meine Threads nur innerhalb der MergeSortParallel-Klasse habe):

Code: Alles auswählen

IOHelper helper = new IOHelper();
array = helper.getNextIntegerArray();
MergeSort.sort(...)
helper.printResult(array);

scho wieder einer schneller... egal

@Thomas:
Um einen Thread zu starten (das ist ein Weg, mehr auf den Folien) muss man ein Objekt einer Klasse die das Interface Runnable implementiert erstellen. In unserem Fall wäre das also unser Konstruktor:

Code: Alles auswählen

public ParallelMergeSort(int[] array)

Die Referenz auf das Array speichern wir als Attribut ab. Mehr braucht der Konstruktor nicht machen.
Durch das Interface Runnable müssen wir jetzt die run() Methode überschreiben. Wie du richtig gesagt hast ruft diese Methode nur den rekursiven Mergesort auf. (Bei mir wäre das RecursiveMergeSort.sort(array))
Starten kann man diesen Thread dann so:

Code: Alles auswählen

ParallelMergeSort sorter = new ParallelMergeSort(array)
Thread th = new Thread(sorter);
th.start();

Der Mainthread muss jetzt warten bis alle Threads fertig sind und holt sich dann über einen Getter alle arrays. Die muss er dann nur noch mergen und fertig ists...
Damit sortiert dieser Thread jetzt das übergebene Array.


Das sollte so in Ordnung sein. Warum auch nicht. Der "Main-Thread" muss nicht unbedingt nur die Mainklasse beinhalten. Er wird am Anfang gestartet und arbeitet alles nacheinander/ sequentiell ab. Das geht durch Klassen und Methoden.

[Baloo]

Wann weiss ich, ob die Threads fertig sind?

Schau dir mal die Klasse ThreadGroup und speziell die Methode activeCount() an. Damit kann sich wunderbar ne eigene join methode basteln

[Christian S.]

Hm, habe die Zahl der Threads mit der Problemgröße skalieren lassen, sprich 1 neuer Thread pro Subproblem. Natürlich verbraucht das mehr Ressourcen, aber da weder auf dem Übungsblatt noch auf den Folien definiert wurde was genau hier unter Parallelisierung verstanden wid (2 Threads? 3 Threads? ...) werde ich es wohl auch so lassen.

[|silent]

Ja, da haste recht... kann man so und so implementieren.

Bei mir laufen zumindest schonmal die Threads, aber das Ergbnis ist einfach nur ein Krampf. Wieso sortiert MergeSort nicht mehr richtig?

3 8 2 0 6 6 5 1 7 3
0 0 0 0 1 1 1 1 3 3

8 3 2 5 4 5 9 1 6 8
1 1 1 1 1 1 1 1 6 8

2 0 1 6 6 2 8 1 3 6
0 0 1 1 1 1 1 1 3 6

Wenn ich den Sortieralgorithmus für Sequentiellen Code schreibe funktionierts, warum gehts dann im Zusammenhang mit Threads nichmehr?

[Thomas]

ich glaub das problem ist, dass die ausgabe zu schnell ausgibt und bis daher das ganze zeug noch gar nicht sortiert ist hab ich zumindest das gefühl. man müsste mit der ausgabe erst waren bis alles sortiert ist. wie man das jetzt aba macht weiß ich noch nicht. mach dir einfachmal ne ausgabe in deine sort-methode wenn du fertig sortiert hast dann siehst du, dass du richtig sortierst. ist zumindest bei mir so und ich wunder mich die ganze zeit warum überhaupt nix passiert :X so sieht meine methode mittlerweile aus

Code: Alles auswählen

	public static void sort(int[] src) {
		int mid = (src.length - 1)/2 + 1;
		int[] arrayLeft = new int[mid];
		int[] arrayRight = new int[src.length - mid];
		System.arraycopy(src, 0, arrayLeft, 0, arrayLeft.length);
		System.arraycopy(src, mid, arrayRight, 0, arrayRight.length);
		MergeSortParallel sorter1 = new MergeSortParallel(arrayLeft);
		MergeSortParallel sorter2 = new MergeSortParallel(arrayRight);
		Thread th1 = new Thread(sorter1);
		Thread th2 = new Thread(sorter2);
		th1.start();
		th2.start();
		try {
			th1.join();
		} catch (InterruptedException e) {
			e.printStackTrace();
		}
		try {
			th2.join();
		} catch (InterruptedException e) {
			e.printStackTrace();
		}
		src = merge(sorter1.source, sorter2.source);
		for (int i : src) {
			System.out.println(i);
		}
	}

[Tankwart]

So, ich wag mal das Experiment nicht funktionierender Code in perfektem Stil, mal schauen wieviel Punkte dabei rauskommen.