SWT[4]#4

[salami]

Hallo,
glaubt ihr es geht in Ordnung, wenn man MergeSort 1:1 von der Algo-Programmieraufgabe übernimmt?
Wieso das Rad neu erfinden, wenn es schon eine gute Implementierung gibt? Eigentlich geht es ja nur darum, den Algorithmus zu parallelisieren.

[BenTreeser]

kann es sein, dass dieses falsch implementiert ist?
Ich kriege zumindest bei dem folgende Ergebnisse:
Vorher: 3 6 9 5 4 8 1 2 0 7
Nachher: 0 1 2 3 4 5 6 8 9 7

hier noch komischer
Vorher: 3 6 9 5 4 8 1 2 0 7
Meins: 1 2 3 4 5 5 6 7 9 9
Im unsortiertem Array exestiert nur eine 9, in dem sortieren schon 2....

Edit:
Aber naja, wir brauchen ja eh einen sequentiellen und keinen rekursiven, gell?

[Christian S.]

Vorsicht, so weit ich weiß ist sequentiell != iterativ. Sprich der Algorithmus ist trotzdem rekursiv. Ein gutes Beispiel aus Wikipedia ( ):

Sequentieller Algorithmus: „Bier auf Wein, lass das sein“ beiden Operationen ist eine Reihenfolge vorgegeben und diese sollte nicht verändert werden.

Nebenläufiger Algorithmus: „Schnaps und Bier“ Die Reihenfolge ist nicht vorgegeben und kann auch gleichzeitig erfolgen.

[Dre]

Hi,

hab ich das richtig verstanden, dass die Prozedur merge() der variable Teil von MergeSort ist und dieser dann
a) sequentiell und...
b) parallel
implementiert werden soll?
...folglich der Schablonenmethode. Ansonsten hab ich das noch nicht richtig verstanden wie man das "aufteilen" soll.

[salami]

Ich habe es so verstanden (mit Schablonenmethode), dass man den Algorithmus über diese Schablone einfach austauschen kann. Praktisch 1:1 so wie beim Algo-Programm. Sprich: Schablone ist einfach eine abstrakte Klasse mit sort()-Methode, die dann je nach Algorithmus was anderes macht.
Hat das noch jemand so gemacht?

[oZz]

Kann mir, einem hübschen, nymphanen Mädchen, erklären wie das mit den Threads funktioniert (sprich im Code selbst mit Parameterübergabe usw. - nicht das Prinzip)? Der erste der gescheit antwortet wird entsprechend meine Dankbarkeit zu spüren bekommen...

[peterlustig]

Ich kann dir zwar nicht bei deinem Problem helfen, aber kann es sein, dass du die geile Drecksau bist, mit der ich letzte woche in LA geredet hab?

[Blurio]

Ich schließ mich oZz mal an, auch wenn man nicht unbedingt sexuelle Gefälligkeiten erwarten kann. Dafür Paddel fürs nichthelfen.

[Misda]

Tztztz, also manche Leute hier machen wohl alles um ne Antwort zu bekommen.

Für alle mit Threadproblemen: Das mit den Threads ist nicht mal so schwer, hier ein ganz kleines Quick&Dirty Beispiel (für das nicht mal Gefälligkeiten verlangt werden ):

Code: Alles auswählen

public class Main implements Runnable {

    private String name;

    public static void main(String[] args) {
        for(int i=0;i<10;i++) {
            Thread t = new Thread(new Main("Thread - " + i));
            t.start();
        }
    }

    public Main(String name) {
       this.name = name;
    }

    public void run() {
//        this.doOutputSynchron();
        this.doOutputWithoutSynchron();
    }

    public void doOutputSynchron() {
        synchronized(System.out) {
            for(int i=0;i<20;i++) {
                System.out.println(this.name + " : " + i);
            }
        }
    }

    public void doOutputWithoutSynchron() {
        for(int i=0;i<20;i++) {
            System.out.println(this.name + " : " + i);
        }
    }

}

Lasst mal den Quellcode so und dann mit der anderen Funktion in run() laufen, und schaut euch die Ausgabe an.

Bei der Ausgabe mit Synchronisation, müssen die anderen Threads warten, bis der Monitor "System.out" wieder frei ist und können dann ne Ausgabe machen (komplette Schleife läuft dann für den Thread). Die Reihenfolge der Threads ist unterschiedlich, wer zuerst kommt, darf an die Ausgabe.

Ohne Synchronisation, schreibt jeder Thread an die Ausgabe, wenn er gerade den Befehl abarbeitet.

Es gibt jetzt noch Mechanismen wie notifyAll() und wait() um manche Dinge besser zu steuern, aber zuerst sollte diese Vorgehensweise verstanden werden.

EDIT:

Ich hab noch ne Frage zur Schablonenmethode - Laut Folien gibts da ja ne konkrete Methode, die abstrakte Methoden aufruft. Bei MergeSort würde mir nun spontan merge() und sort() einfallen - aber die Parallel machen? Ne andere Möglichkeit ist, die Sortierung sequentiell zu machen und dann das Array in n-Teile auftrennen und dies an Threads schicken - aber was hat das dann mit der Schablonenmethode zut tun

[oZz]

Das Problem ist ja nicht verschieden Threads zu starten, sondern ich denke mal es ist so gedacht dass die Rekursion auf zwei Threads aufgeteilt wird und Threads laufen ja über eine ganze Klasse und nicht über Methoden, d.h. man kann nicht in einer einzigen Klasse sagen tue run() für Thread t1 mit der Rekursion für den linken Baum sozusagen und tue run() für Thread t2 mit dem rechten Baum. Das ist das eigentliche Problem

Und zur Schablonenmethode hätt ich gedacht dass die die Aufgaben a) und b) zusammenfasst. Also eine Klasse abstract MergeSort und dann zwei Klasse MSSequentiell und MSParallel. Die Schablonenmethode ist dann die die die Sortierung durchführt (für jede Klasse unterschiedlich) und danach eine Ausgabe macht (für beide Klassen gleich). Also quasi

void sort() { }

void schablonenmethode() {
this.sort();
... // Ausgabe
}