Threads

Diskutiere Threads im Java Basics - Anfänger-Themen Bereich.
A

Adriano10

Java:
public class QuickSort {

    public static void sort(int[] numbers) {
        new QuickSort().quickSort(numbers, 0, numbers.length - 1);
    }

    protected void quickSort(int[] numbers, int leftIndex, int rightIndex) {
        if (leftIndex < rightIndex) {
            int pivotIndex = divide(numbers, leftIndex, rightIndex);
            quickSort(numbers, leftIndex, pivotIndex - 1);
            quickSort(numbers, pivotIndex + 1, rightIndex);
        }
    }

    /**
     * liefert den Index des Pivot-Elementes und ordnet das Array innerhalb
     * der angegebenen Indizes so um, dass alle Zahlen links vom Index
     * kleiner oder gleich und alle Zahlen rechts vom Index groesser
     * oder gleich dem Pivot-Element sind
     */
    protected int divide(int[] numbers, int leftIndex, int rightIndex) {
        int pivotIndex = choosePivotIndex(numbers, leftIndex, rightIndex);
        int pivotValue = numbers[pivotIndex];
        // das Pivot-Element kommt nach ganz rechts im Array
        swap(numbers, pivotIndex, rightIndex);
        int left = leftIndex - 1;
        int right = rightIndex;

        do {
            left++;
            while (left <= rightIndex && numbers[left] <= pivotValue)
                left++;
            right--;
            while (right >= leftIndex && numbers[right] >= pivotValue)
                right--;
            if (left < right) {
                swap(numbers, left, right);
            }
        } while (left < right);
        // platziere das Pivot-Element an seine korrekte Position
        if (left < rightIndex) {
            swap(numbers, left, rightIndex);
            return left;
        } else {
            return rightIndex;
        }
    }

    protected int choosePivotIndex(int[] numbers, int leftIndex, int rightIndex) {

        return (leftIndex + rightIndex) / 2;
    }

    protected void swap(int[] numbers, int index1, int index2) {
        if (index1 != index2) {
            int tmp = numbers[index1];
            numbers[index1] = numbers[index2];
            numbers[index2] = tmp;
        }
    }

}

public class QuickSortTest {
    public static void main(String[] args) {
        int[] numbers = {2, 3, 9, 33, -2, 4, 55, 66, -234};
        print(numbers);
        QuickSort.sort(numbers);
        print(numbers);
       
        int[] numbers2 = {2, 3, 9, 33, -2, 4, 55, 66, -234};
        print(numbers2);
        QuickSortThreaded.sort(numbers2);
        print(numbers2);
    }
   
    private static void print(int[] numbers) {
        for (int number : numbers) {
            System.out.print(number + " ");
        }
        System.out.println();
    }


}

public class QuickSortThreaded extends QuickSort{

    public static void sort(int[] numbers) {

        QuickSort.sort(numbers);
    }

    protected void quickSort(int[] numbers, int leftIndex, int rightIndex) {
       
        super.quickSort(numbers, leftIndex, rightIndex);
    }


}
In der Hilfsmethode quickSort werden nacheinander der Bereich links vom Pivot-Element und der Bereich rechts vom PivotElement durch rekursiven Aufruf der Methode sortiert. Die beide Aktionen sind unabhängig voneinander. Wie kann ich sie durch die Verwendung von Threads parallelisieren?
 
J

JustNobody

Du hast schon richtig erkannt, dass die zwei quicksort Aufrufe unabhängig voneinander sind.

Liegt Dein Problem nun darin, dass Du nicht weißt, wie Du einem neuen Thread die Parameter übergeben kannst? Eine Idee, das hin zu bekommen, wäre z.B. eine Klasse die Runnable implementiert. Im Konstruktor übergibst Du die Paramter in die Instanz.

Das geht auch über anonyme Klassen, aber dazu musst Du dann die Variablen mit den Parametern final machen.

Beides findest Du unter https://stackoverflow.com/questions/877096/how-can-i-pass-a-parameter-to-a-java-thread

Am Ende musst Du sicher stellen, dass die Threads beendet sind. Dazu kannst Du auf den erstellten Threads jeweils ein join aufrufen.

Und du musst natürlich nicht zwei Threads starten. Einen Thread hast Du ja schon. Zwei Threads zu starten und dann sofort ein join auf einen Thread auszuführen bringt keinen Vorteil. Also wäre die Logik:
- Einen Thread erstellen für eine Seite.
- Andere Seite direktmachen.
- join auf gestarteten Thread aufrufen
 
A

Adriano10

Du hast schon richtig erkannt, dass die zwei quicksort Aufrufe unabhängig voneinander sind.

Liegt Dein Problem nun darin, dass Du nicht weißt, wie Du einem neuen Thread die Parameter übergeben kannst? Eine Idee, das hin zu bekommen, wäre z.B. eine Klasse die Runnable implementiert. Im Konstruktor übergibst Du die Paramter in die Instanz.

Das geht auch über anonyme Klassen, aber dazu musst Du dann die Variablen mit den Parametern final machen.

Beides findest Du unter https://stackoverflow.com/questions/877096/how-can-i-pass-a-parameter-to-a-java-thread

Am Ende musst Du sicher stellen, dass die Threads beendet sind. Dazu kannst Du auf den erstellten Threads jeweils ein join aufrufen.

Und du musst natürlich nicht zwei Threads starten. Einen Thread hast Du ja schon. Zwei Threads zu starten und dann sofort ein join auf einen Thread auszuführen bringt keinen Vorteil. Also wäre die Logik:
- Einen Thread erstellen für eine Seite.
- Andere Seite direktmachen.
- join auf gestarteten Thread aufrufen
ja so habe ich mit der Implementierung von Runnable angefangen, danke für die Hinweise, ich versuche mal, ob ich die Methode run() zum Laufen bekomme.
 
A

Adriano10

Du hast schon richtig erkannt, dass die zwei quicksort Aufrufe unabhängig voneinander sind.

Liegt Dein Problem nun darin, dass Du nicht weißt, wie Du einem neuen Thread die Parameter übergeben kannst? Eine Idee, das hin zu bekommen, wäre z.B. eine Klasse die Runnable implementiert. Im Konstruktor übergibst Du die Paramter in die Instanz.

Das geht auch über anonyme Klassen, aber dazu musst Du dann die Variablen mit den Parametern final machen.

Beides findest Du unter https://stackoverflow.com/questions/877096/how-can-i-pass-a-parameter-to-a-java-thread

Am Ende musst Du sicher stellen, dass die Threads beendet sind. Dazu kannst Du auf den erstellten Threads jeweils ein join aufrufen.

Und du musst natürlich nicht zwei Threads starten. Einen Thread hast Du ja schon. Zwei Threads zu starten und dann sofort ein join auf einen Thread auszuführen bringt keinen Vorteil. Also wäre die Logik:
- Einen Thread erstellen für eine Seite.
- Andere Seite direktmachen.
- join auf gestarteten Thread aufrufen
Java:
public class QuickSortThreaded extends QuickSort implements Runnable{
    
    /**
     * sortiert das uebergebene Array in aufsteigender Reihenfolge
     * gemaess dem QuickSort-Algorithmus (parallel!)
     */
    
    private int[] number;
    int start, end;
    QuickSortThreaded(int[] number, int start, int end){
        this.number = number;
        this.start = start;
        this.end = end;
    }
    public static void sort(int[] numbers) {
        //TODO implement this
        QuickSort.sort(numbers);
    }

    /**
     * der Quicksort-Algorithmus wird auf dem Array zwischen den
     * angegebenen Indizes ausgefuehrt
     */
    protected void quickSort(int[] numbers, int leftIndex, int rightIndex) {
        
        super.quickSort(numbers, leftIndex, rightIndex);
    }

    @Override
    public void run() {
        quickSort(number, start, end);
        
    }


}
Das wollte ich Ihnen zeigen, ob ich auf dem richtigen Weg stehe.
 
A

Adriano10

Du hast schon richtig erkannt, dass die zwei quicksort Aufrufe unabhängig voneinander sind.

Liegt Dein Problem nun darin, dass Du nicht weißt, wie Du einem neuen Thread die Parameter übergeben kannst? Eine Idee, das hin zu bekommen, wäre z.B. eine Klasse die Runnable implementiert. Im Konstruktor übergibst Du die Paramter in die Instanz.

Das geht auch über anonyme Klassen, aber dazu musst Du dann die Variablen mit den Parametern final machen.

Beides findest Du unter https://stackoverflow.com/questions/877096/how-can-i-pass-a-parameter-to-a-java-thread

Am Ende musst Du sicher stellen, dass die Threads beendet sind. Dazu kannst Du auf den erstellten Threads jeweils ein join aufrufen.

Und du musst natürlich nicht zwei Threads starten. Einen Thread hast Du ja schon. Zwei Threads zu starten und dann sofort ein join auf einen Thread auszuführen bringt keinen Vorteil. Also wäre die Logik:
- Einen Thread erstellen für eine Seite.
- Andere Seite direktmachen.
- join auf gestarteten Thread aufrufen
Java:
public class QuickSortTest {
    public static void main(String[] args) {
    /*    int[] numbers = {2, 3, 9, 33, -2, 4, 55, 66, -234};
        print(numbers);
        QuickSort.sort(numbers);
        print(numbers);*/
        
        int[] numbers2 = {2, 3, 9, 33, -2, 4, 55, 66, -234};
    //    QuickSortThreaded.sort(numbers2);
        
        Thread thread = new Thread(new QuickSortThreaded(numbers2, 0, numbers2.length - 1));
        Thread thread1 = new Thread(new QuickSortThreaded(numbers2, 0, numbers2.length - 1));
        
        thread.start();
        thread1.start();
        
        try {
            thread.join();
            thread1.join();
        }catch(InterruptedException e) {
            
        }
        
        print(numbers2);
        
        
    }
    
    private static void print(int[] numbers) {
        for (int number : numbers) {
            System.out.print(number + " ");
        }
        System.out.println();
    }


}

public class QuickSortThreaded extends QuickSort implements Runnable{
    
    /**
     * sortiert das uebergebene Array in aufsteigender Reihenfolge
     * gemaess dem QuickSort-Algorithmus (parallel!)
     */
    

    private int[] numbers;
    //private int start, end;
    QuickSortThreaded(int[] numbers, int start, int end){
        this.numbers = numbers;
        quickSort(this.numbers, start, end);
        
        
    }
    public static void sort(int[] numbers) {
        //TODO implement this
        QuickSort.sort(numbers);
    }

    /**
     * der Quicksort-Algorithmus wird auf dem Array zwischen den
     * angegebenen Indizes ausgefuehrt
     */
    protected void quickSort(int[] numbers, int leftIndex, int rightIndex) {
        
        super.quickSort(numbers, leftIndex, rightIndex);
    }

    @Override
    public void run() {
        quickSort(numbers, 0, numbers.length - 1);
        
    }


}
so sieh mein Quelcode aus, zwar Array wird sortiert auf der Console sortiert ausgegeben, aber ich weiß trotzdem nicht, ob ich alles richtig gemacht habe.
 
J

JustNobody

Du bist zu schnell mit Deinen Posts ... ich war gerade noch dabei, zu deinem vorletzten Thread was zu schreiben :)

Da sah Dein Ansatz noch sehr gut aus. Du hattest da noch quickSort in der Oberklasse aufgerufen. Da hätte nur Deine eigene Implementation rein gemusst.

Und der Konstruktor ruft kein quickSort auf, denn so machst Du ja direkt im Hauptthread die Sortierung. Da wirklich nur die Parameter speichern für die spätere Verwendung!

Und in main erstellst Du keine Threads.

Also im run (oder wenn Du da nur ein quickSort aufrufen willst, in der quickSort methode) musst Du halt das implementieren, was Du in der Super Klasse schon hattest. Ich würde Dir raten, einfach einmal die quickSort Methode der Oberklasse 1:1 zu kopieren.
Und nur bei den rekursiven Aufrufen veränderst Du dann den Code, so dass Du Threads erstellst.

Dabei kannst Du Dir aber überlegen, nur einen Thread zu erstellen und beim zweiten den quickSort Aufruf so zu lassen.

Bildlich ausgedrückt: Es müssen zwei Dinge gemacht werden. Ohne zusätzliche Arbeiter bist Du der Arbeiter, der das machen muss, also machst du erst das Erste und danach das Zweite.

Mit den zusätzlichen Arbeitern ist die Logik derzeit:
Du erstellst zwei Arbeiter und schickst diese los. Du selbst (Bist ja auch ein Arbeiter) wartest, bis die zurück sind (join Aufrufe).

Aber Da Du zwe Sachen hast, ein Arbeiter hast Du schon, der auf das fertig werden warten soll, brauchst Du nur noch einen Arbeiter. Du musst also nur einen Arbeiter erstellen und los schicken und dann kannst Du selbst los rennen. Wenn Du zurück bist, musst Du nur auf den anderen Arbeiter warten und bist durch.
 
A

Adriano10

Du bist zu schnell mit Deinen Posts ... ich war gerade noch dabei, zu deinem vorletzten Thread was zu schreiben :)

Da sah Dein Ansatz noch sehr gut aus. Du hattest da noch quickSort in der Oberklasse aufgerufen. Da hätte nur Deine eigene Implementation rein gemusst.

Und der Konstruktor ruft kein quickSort auf, denn so machst Du ja direkt im Hauptthread die Sortierung. Da wirklich nur die Parameter speichern für die spätere Verwendung!

Und in main erstellst Du keine Threads.

Also im run (oder wenn Du da nur ein quickSort aufrufen willst, in der quickSort methode) musst Du halt das implementieren, was Du in der Super Klasse schon hattest. Ich würde Dir raten, einfach einmal die quickSort Methode der Oberklasse 1:1 zu kopieren.
Und nur bei den rekursiven Aufrufen veränderst Du dann den Code, so dass Du Threads erstellst.

Dabei kannst Du Dir aber überlegen, nur einen Thread zu erstellen und beim zweiten den quickSort Aufruf so zu lassen.

Bildlich ausgedrückt: Es müssen zwei Dinge gemacht werden. Ohne zusätzliche Arbeiter bist Du der Arbeiter, der das machen muss, also machst du erst das Erste und danach das Zweite.

Mit den zusätzlichen Arbeitern ist die Logik derzeit:
Du erstellst zwei Arbeiter und schickst diese los. Du selbst (Bist ja auch ein Arbeiter) wartest, bis die zurück sind (join Aufrufe).

Aber Da Du zwe Sachen hast, ein Arbeiter hast Du schon, der auf das fertig werden warten soll, brauchst Du nur noch einen Arbeiter. Du musst also nur einen Arbeiter erstellen und los schicken und dann kannst Du selbst los rennen. Wenn Du zurück bist, musst Du nur auf den anderen Arbeiter warten und bist durch.
Das heist in der sort methode soll ich drei Array erstellen, aber da diese Klasse interface Runnable implementiert, muss ich auch methode run() irgendwie zum Laufen bekommen, die ich, wie es scheint, überhaupt nicht benötige.

Ohne Runnable zu implementieren oder die Superklasse Threads zu erben, kann man das parallelisieren.. ?

Code:
public static void sort(int[] numbers) {
        int pivotElement = numbers[numbers.length-1];
        int[] array = new int[0];
        int[] arr = new int[0];
        int[] tmp;

        for (int numb: numbers) {
            if(numb <= pivotElement)
            {
                tmp = new int[kleiner.length+1];
                int i;
                for ( i = 0 ; i < kleiner.length ; i++)
                {
                    tmp[i] = kleiner[i];
                }
                tmp[i] = numb;
                kleiner = tmp;
            }
            else
            {
                tmp = new int[groesser.length+1];
                int i;
                for (i = 0 ; i < groesser.length ; i++)
                {
                    tmp[i] = groesser[i];
                }
                tmp[i] = numb;
                groesser = tmp;
            }
        }
 
A

Adriano10

Du bist zu schnell mit Deinen Posts ... ich war gerade noch dabei, zu deinem vorletzten Thread was zu schreiben :)

Da sah Dein Ansatz noch sehr gut aus. Du hattest da noch quickSort in der Oberklasse aufgerufen. Da hätte nur Deine eigene Implementation rein gemusst.

Und der Konstruktor ruft kein quickSort auf, denn so machst Du ja direkt im Hauptthread die Sortierung. Da wirklich nur die Parameter speichern für die spätere Verwendung!

Und in main erstellst Du keine Threads.

Also im run (oder wenn Du da nur ein quickSort aufrufen willst, in der quickSort methode) musst Du halt das implementieren, was Du in der Super Klasse schon hattest. Ich würde Dir raten, einfach einmal die quickSort Methode der Oberklasse 1:1 zu kopieren.
Und nur bei den rekursiven Aufrufen veränderst Du dann den Code, so dass Du Threads erstellst.

Dabei kannst Du Dir aber überlegen, nur einen Thread zu erstellen und beim zweiten den quickSort Aufruf so zu lassen.

Bildlich ausgedrückt: Es müssen zwei Dinge gemacht werden. Ohne zusätzliche Arbeiter bist Du der Arbeiter, der das machen muss, also machst du erst das Erste und danach das Zweite.

Mit den zusätzlichen Arbeitern ist die Logik derzeit:
Du erstellst zwei Arbeiter und schickst diese los. Du selbst (Bist ja auch ein Arbeiter) wartest, bis die zurück sind (join Aufrufe).

Aber Da Du zwe Sachen hast, ein Arbeiter hast Du schon, der auf das fertig werden warten soll, brauchst Du nur noch einen Arbeiter. Du musst also nur einen Arbeiter erstellen und los schicken und dann kannst Du selbst los rennen. Wenn Du zurück bist, musst Du nur auf den anderen Arbeiter warten und bist durch.
Das heist in der sort methode soll ich drei Array erstellen, aber da diese Klasse interface Runnable implementiert, muss ich auch methode run() irgendwie zum Laufen bekommen, die ich, wie es scheint, überhaupt nicht benötige.

Ohne Runnable zu implementieren oder die Superklasse Threads zu erben, kann man das parallelisieren.. ?

Code:
public static void sort(int[] numbers) {
        int pivotElement = numbers[numbers.length-1];
        int[] array = new int[0];
        int[] arr = new int[0];
        int[] tmp;

        for (int numb: numbers) {
            if(numb <= pivotElement)
            {
                tmp = new int[array.length+1];
                int i;
                for ( i = 0 ; i < array ; i++)
                {
                    tmp[i] = array[i];
                }
                tmp[i] = numb;
                array = tmp;
            }
            else
            {
                tmp = new int[arr.length+1];
                int i;
                for (i = 0 ; i < arr.length ; i++)
                {
                    tmp[i] = arr[i];
                }
                tmp[i] = numb;
               arr = tmp;
            }
        }
 
J

JustNobody

Was ich hier noch erwähnen möchte:
Der Ansatz ist nur begrenzt gut. Denn Du erstellst sehr schnell sehr viele Threads. Der Computer kann diese aber nur begrenzt parallel ausführen. Daher wirst Du bei großer Anzahl an Elementen schnell in eine Situation kommen, wo die CPU vor allem zwischen Threads umschaltet aber die Threads kaum noch Zeit bekommen.

Daher macht es Sinn, da eine Lösung zu finden, die die Anzahl der Threads begrenzt. Also nur n Threads und wenn die voll sind, dann werden keine weiteren Threads mehr benutzt. Dazu kann man sich überlegen, wie man dies bauen könnte.

Es gibt dazu aber auch prinzipiell schon Lösungen. So Thread Themen finden sich oft unter dem Stichwort ThreadPool. Ein sehr interessanter Artikel könnte z.B. https://www.baeldung.com/thread-pool-java-and-guava sein - speziell der Abschnitt 3.4 ForkJoinPool.
 
J

JustNobody

Also Du scheinst Dich gerade voll zu verrennen. Daher einfach einmal die ganzen Schritte der Entwicklung Schritt für Schritt durchgeführt

Du hast doch ohne Threads einfach nur:
Code:
    protected void quickSort(int[] numbers, int leftIndex, int rightIndex) {
        if (leftIndex < rightIndex) {
            int pivotIndex = divide(numbers, leftIndex, rightIndex);
            quickSort(numbers, leftIndex, pivotIndex - 1);
            quickSort(numbers, pivotIndex + 1, rightIndex);
        }
    }
Die Idee, die Du jetzt hattest, war doch, dass Du die quickSort Aufrufe in Threads machst.

Also etwas in der Form:
Code:
    protected void quickSort(int[] numbers, int leftIndex, int rightIndex) {
        if (leftIndex < rightIndex) {
            int pivotIndex = divide(numbers, leftIndex, rightIndex);
            quickSortOnNewThread(numbers, leftIndex, pivotIndex - 1);
            quickSort(numbers, pivotIndex + 1, rightIndex);
            waitForThreadToFinish();
        }
    }
Wobei ich jetzt schon darauf geachtet habe, dass der aktuelle Thread auch weiter verwendet wird.

Das waitForThreadToFinish benötigt eine Referenz auf den Thread und wird über ein join() Aufruf gemacht, also haben wir etwas wie:

Code:
    protected void quickSort(int[] numbers, int leftIndex, int rightIndex) {
        if (leftIndex < rightIndex) {
            int pivotIndex = divide(numbers, leftIndex, rightIndex);
            Thread thread = quickSortOnNewThread(numbers, leftIndex, pivotIndex - 1);
            quickSort(numbers, pivotIndex + 1, rightIndex);
            thread.join();
        }
    }
Wie können wir einen Thread erstellen, der diesen quickSort Aufruf macht?
a) Wir erstellen eine neue Instanz von QuickSortThreaded mit Konstruktor-Aufruf (numbers, leftIndex, pivotIndex-1)
b) Wir erzeugen einen neuen Thread mit dieser Instanz und geben diesen Thread dann zurück.

Damit haben wir etwas wie:
Code:
protected Thread createQuickSortThread(int[] numbers, int leftIndex, int rightIndex) {
    return new Thread(new QuickSortThreaded(number, leftIndex, rightIndex));
}
Und natürlich speichert der Konstruktor nur die übergebenen Werte:
Code:
    QuickSortThreaded(int[] numbers, int start, int end){
        this.numbers = numbers;
        this.start = start;
        this.end = end;
}
Und die run Methode ruft nur das entsprechende quickSort auf:
Code:
public void run() {
    quickSort(numbers, start, end);
}
Die Erweiterung bezüglich der Maximierung der Thread-Anzahl wäre denn z.B. dass die Methode createQuickSortThread auch null zurück geben kann... Das wäre dann in etwa so:

Code:
protected Thread createQuickSortThread(int[] numbers, int leftIndex, int rightIndex) {
    if (canCreateNewThreads())
        return new Thread(new QuickSortThreaded(number, leftIndex, rightIndex));

    // Do work in current thread and return null
    quickSort(numbers, leftIndex, rightIndex);
    return null;
}
Und der join Aufruf braucht dann natürlich einen null check:
Code:
    protected void quickSort(int[] numbers, int leftIndex, int rightIndex) {
        if (leftIndex < rightIndex) {
            int pivotIndex = divide(numbers, leftIndex, rightIndex);
            Thread thread = quickSortOnNewThread(numbers, leftIndex, pivotIndex - 1);
            quickSort(numbers, pivotIndex + 1, rightIndex);
            if (thread != null) thread.join();
        }
    }
Wie dann canCreateNewThreads() implementiert wird, muss man überlegen. Man könnte z.B. einen Zähler einbauen und wenn der Zähler < Maximum ist, dann wird er eins hoch gezählt und true ausgegeben. Und ansonsten false. Und in der run methode könnte man am Ende noch den Zähler reduzieren. Der Zähler muss dabei so geschützt werden, dass immer nur ein Thread diesen verändern kann.... Das kann man ggf. aber auch noch optimieren, aber das lassen wir an der Stelle einfach erst einmal :)
 
A

Adriano10

Also Du scheinst Dich gerade voll zu verrennen. Daher einfach einmal die ganzen Schritte der Entwicklung Schritt für Schritt durchgeführt

Du hast doch ohne Threads einfach nur:
Code:
    protected void quickSort(int[] numbers, int leftIndex, int rightIndex) {
        if (leftIndex < rightIndex) {
            int pivotIndex = divide(numbers, leftIndex, rightIndex);
            quickSort(numbers, leftIndex, pivotIndex - 1);
            quickSort(numbers, pivotIndex + 1, rightIndex);
        }
    }
Die Idee, die Du jetzt hattest, war doch, dass Du die quickSort Aufrufe in Threads machst.

Also etwas in der Form:
Code:
    protected void quickSort(int[] numbers, int leftIndex, int rightIndex) {
        if (leftIndex < rightIndex) {
            int pivotIndex = divide(numbers, leftIndex, rightIndex);
            quickSortOnNewThread(numbers, leftIndex, pivotIndex - 1);
            quickSort(numbers, pivotIndex + 1, rightIndex);
            waitForThreadToFinish();
        }
    }
Wobei ich jetzt schon darauf geachtet habe, dass der aktuelle Thread auch weiter verwendet wird.

Das waitForThreadToFinish benötigt eine Referenz auf den Thread und wird über ein join() Aufruf gemacht, also haben wir etwas wie:

Code:
    protected void quickSort(int[] numbers, int leftIndex, int rightIndex) {
        if (leftIndex < rightIndex) {
            int pivotIndex = divide(numbers, leftIndex, rightIndex);
            Thread thread = quickSortOnNewThread(numbers, leftIndex, pivotIndex - 1);
            quickSort(numbers, pivotIndex + 1, rightIndex);
            thread.join();
        }
    }
Wie können wir einen Thread erstellen, der diesen quickSort Aufruf macht?
a) Wir erstellen eine neue Instanz von QuickSortThreaded mit Konstruktor-Aufruf (numbers, leftIndex, pivotIndex-1)
b) Wir erzeugen einen neuen Thread mit dieser Instanz und geben diesen Thread dann zurück.

Damit haben wir etwas wie:
Code:
protected Thread createQuickSortThread(int[] numbers, int leftIndex, int rightIndex) {
    return new Thread(new QuickSortThreaded(number, leftIndex, rightIndex));
}
Und natürlich speichert der Konstruktor nur die übergebenen Werte:
Code:
    QuickSortThreaded(int[] numbers, int start, int end){
        this.numbers = numbers;
        this.start = start;
        this.end = end;
}
Und die run Methode ruft nur das entsprechende quickSort auf:
Code:
public void run() {
    quickSort(numbers, start, end);
}
Die Erweiterung bezüglich der Maximierung der Thread-Anzahl wäre denn z.B. dass die Methode createQuickSortThread auch null zurück geben kann... Das wäre dann in etwa so:

Code:
protected Thread createQuickSortThread(int[] numbers, int leftIndex, int rightIndex) {
    if (canCreateNewThreads())
        return new Thread(new QuickSortThreaded(number, leftIndex, rightIndex));

    // Do work in current thread and return null
    quickSort(numbers, leftIndex, rightIndex);
    return null;
}
Und der join Aufruf braucht dann natürlich einen null check:
Code:
    protected void quickSort(int[] numbers, int leftIndex, int rightIndex) {
        if (leftIndex < rightIndex) {
            int pivotIndex = divide(numbers, leftIndex, rightIndex);
            Thread thread = quickSortOnNewThread(numbers, leftIndex, pivotIndex - 1);
            quickSort(numbers, pivotIndex + 1, rightIndex);
            if (thread != null) thread.join();
        }
    }
Wie dann canCreateNewThreads() implementiert wird, muss man überlegen. Man könnte z.B. einen Zähler einbauen und wenn der Zähler < Maximum ist, dann wird er eins hoch gezählt und true ausgegeben. Und ansonsten false. Und in der run methode könnte man am Ende noch den Zähler reduzieren. Der Zähler muss dabei so geschützt werden, dass immer nur ein Thread diesen verändern kann.... Das kann man ggf. aber auch noch optimieren, aber das lassen wir an der Stelle einfach erst einmal :)
super danke... voll verständlich...
 
A

Adriano10

Also Du scheinst Dich gerade voll zu verrennen. Daher einfach einmal die ganzen Schritte der Entwicklung Schritt für Schritt durchgeführt

Du hast doch ohne Threads einfach nur:
Code:
    protected void quickSort(int[] numbers, int leftIndex, int rightIndex) {
        if (leftIndex < rightIndex) {
            int pivotIndex = divide(numbers, leftIndex, rightIndex);
            quickSort(numbers, leftIndex, pivotIndex - 1);
            quickSort(numbers, pivotIndex + 1, rightIndex);
        }
    }
Die Idee, die Du jetzt hattest, war doch, dass Du die quickSort Aufrufe in Threads machst.

Also etwas in der Form:
Code:
    protected void quickSort(int[] numbers, int leftIndex, int rightIndex) {
        if (leftIndex < rightIndex) {
            int pivotIndex = divide(numbers, leftIndex, rightIndex);
            quickSortOnNewThread(numbers, leftIndex, pivotIndex - 1);
            quickSort(numbers, pivotIndex + 1, rightIndex);
            waitForThreadToFinish();
        }
    }
Wobei ich jetzt schon darauf geachtet habe, dass der aktuelle Thread auch weiter verwendet wird.

Das waitForThreadToFinish benötigt eine Referenz auf den Thread und wird über ein join() Aufruf gemacht, also haben wir etwas wie:

Code:
    protected void quickSort(int[] numbers, int leftIndex, int rightIndex) {
        if (leftIndex < rightIndex) {
            int pivotIndex = divide(numbers, leftIndex, rightIndex);
            Thread thread = quickSortOnNewThread(numbers, leftIndex, pivotIndex - 1);
            quickSort(numbers, pivotIndex + 1, rightIndex);
            thread.join();
        }
    }
Wie können wir einen Thread erstellen, der diesen quickSort Aufruf macht?
a) Wir erstellen eine neue Instanz von QuickSortThreaded mit Konstruktor-Aufruf (numbers, leftIndex, pivotIndex-1)
b) Wir erzeugen einen neuen Thread mit dieser Instanz und geben diesen Thread dann zurück.

Damit haben wir etwas wie:
Code:
protected Thread createQuickSortThread(int[] numbers, int leftIndex, int rightIndex) {
    return new Thread(new QuickSortThreaded(number, leftIndex, rightIndex));
}
Und natürlich speichert der Konstruktor nur die übergebenen Werte:
Code:
    QuickSortThreaded(int[] numbers, int start, int end){
        this.numbers = numbers;
        this.start = start;
        this.end = end;
}
Und die run Methode ruft nur das entsprechende quickSort auf:
Code:
public void run() {
    quickSort(numbers, start, end);
}
Die Erweiterung bezüglich der Maximierung der Thread-Anzahl wäre denn z.B. dass die Methode createQuickSortThread auch null zurück geben kann... Das wäre dann in etwa so:

Code:
protected Thread createQuickSortThread(int[] numbers, int leftIndex, int rightIndex) {
    if (canCreateNewThreads())
        return new Thread(new QuickSortThreaded(number, leftIndex, rightIndex));

    // Do work in current thread and return null
    quickSort(numbers, leftIndex, rightIndex);
    return null;
}
Und der join Aufruf braucht dann natürlich einen null check:
Code:
    protected void quickSort(int[] numbers, int leftIndex, int rightIndex) {
        if (leftIndex < rightIndex) {
            int pivotIndex = divide(numbers, leftIndex, rightIndex);
            Thread thread = quickSortOnNewThread(numbers, leftIndex, pivotIndex - 1);
            quickSort(numbers, pivotIndex + 1, rightIndex);
            if (thread != null) thread.join();
        }
    }
Wie dann canCreateNewThreads() implementiert wird, muss man überlegen. Man könnte z.B. einen Zähler einbauen und wenn der Zähler < Maximum ist, dann wird er eins hoch gezählt und true ausgegeben. Und ansonsten false. Und in der run methode könnte man am Ende noch den Zähler reduzieren. Der Zähler muss dabei so geschützt werden, dass immer nur ein Thread diesen verändern kann.... Das kann man ggf. aber auch noch optimieren, aber das lassen wir an der Stelle einfach erst einmal :)
Java:
public class QuickSortThreaded extends QuickSort implements Runnable{
    
    private  int[] numbers;

    
    QuickSortThreaded(int[] numbers){
        this.numbers = numbers;
    }

    public static void sort(int[] numbers) {
        QuickSort.sort(numbers);
    }

    protected void quickSort(int[] numbers, int leftIndex, int rightIndex) {
        
        super.quickSort(numbers, leftIndex, rightIndex);
        
    }

    @Override
    public void run() {
        int pivot = divide(numbers, 0, numbers.length - 1);
        
        Thread thread = new Thread(() -> quickSort(numbers, 0, pivot - 1));
        Thread thread1 = new Thread(() -> quickSort(numbers, pivot + 1, numbers.length - 1));
        thread.start();
        thread1.start();
        
        try {
            thread.join();
            thread1.join();
        }catch(InterruptedException e) {
            
        }        }
}


public class QuickSortTest {

    public static void main(String[] args) {
        int[] numbers = {2, 3, 9, 33, -2, 4, 55, 66, -234};
        print(numbers);
        QuickSort.sort(numbers);
        print(numbers);
        
        int[] numbers2 = {2, 3, 9, 33, -2, 4, 55, 66, -234};
        print(numbers2);
        QuickSortThreaded q = new QuickSortThreaded(numbers2);
        q.run();
        print(numbers2);
    }
    
    private static void print(int[] numbers) {
        for (int number : numbers) {
            System.out.print(number + " ");
        }
        System.out.println();
    }

}
Jetzt muss sie funktionieren... Ich hab echt viel Mühe gegeben, da diese Threads, wie eben gesaget habe, mir ganzu neu sind.
 
J

JustNobody

Sorry, aber Ziel soll doch sein, dass das quickSort nun mit Threads arbeitet.

Also ist sowas
Code:
    protected void quickSort(int[] numbers, int leftIndex, int rightIndex) {
        super.quickSort(numbers, leftIndex, rightIndex);
    }
bestimmt nicht korrekt. Es sei denn, du willst nur einmalig zwei Threads haben und die dann wie normal durchlaufen lassen....

Code:
        QuickSortThreaded q = new QuickSortThreaded(numbers2);
        q.run();
das führt das Runnable ad absurdum. Der Sinn dahinter ist doch gerade, dass da ein anderer Thread das ausführt. so ein run() Aufruf ist in der Regel immer sehr dubios.

Code:
    public static void sort(int[] numbers) {
        QuickSort.sort(numbers);
    }
Das ist noch alter Müll? Der sort Aufruf in der neuen Klasse soll einfach sort von QuickSort aufrufen? Also keine Threads und so? Das wirst Du doch nicht wollen, oder?

Dann führst Du plötzlich Lambdas ein. Ist ok, kann man machen. Dann brauchst Du aber kein Runnable mehr....

Code:
public class QuickSortThreaded extends QuickSort {
   
    public static void sort(int[] numbers) {
        new QuickSortThreaded().quickSort(numbers, 0, numbers.length - 1);
    }

    protected void quickSort(int[] numbers, int leftIndex, int rightIndex) {
        if (leftIndex >= rightIndex) return;
       
        int pivot = divide(numbers, leftIndex, rightIndex);
       
        Thread thread = new Thread(() -> quickSort(numbers, leftIndex, pivot - 1));
        thread.start();
        quickSort(numbers, pivot + 1, rightIndex);

        try {
            thread.join();
        } catch(InterruptedException e) {
            e.printStackTrace();
        }
    }
}
Das einfach mal im Forum-Editor zusammen geschrieben als kurze, prägnante Lösung.

Und nutzen kannst Du das so, wie auch die QuickSort Klasse - durch Aufruf der statischen sort Methode.

Edit: Musste natürlich new QuickSortThreaded() in sort() sein!
 
J

JustNobody

Ich habe jetzt einmal ein GitHub repo gestartet mit Algorithmen für das Forum. Da habe ich dann mal jeweils die Implementation rein getan, wie ich diese geschrieben hätte.

Pivot Element ist bei mir einfach das rechte Element, dadurch kein Tausch nach Rechts und so ... (So aufgebaut wir bei Wikipedia auch beschrieben)

GitHub Repository findet man unter: https://github.com/kneitzel/java-forum-algorithms

Feedback und Verbesserungsvorschläge nehme ich gerne entgegen :)
 
Thema: 

Threads

Passende Stellenanzeigen aus deiner Region:
Anzeige

Neue Themen

Anzeige

Anzeige
Oben