Ich experimentiere mit Parallelisierungsalgorithmen in Java. Ich habe mit dem Sortieren von Zusammenführungen begonnen und meinen Versuch in diesem @ geposteFrag. Mein überarbeiteter Versuch ist im Code unten, wo ich jetzt versuche, schnelles Sortieren zu parallelisieren.

Gibt es irgendwelche Anfängerfehler in meiner Multithread-Implementierung oder in der Herangehensweise an dieses Problem? Wenn nicht, sollte ich nicht mit einer Geschwindigkeitssteigerung von mehr als 32% zwischen einem sequentiellen und einem parallelisierten Algorithmus auf einem Duell-Core rechnen (siehe Timings unten)?

Hier ist der Multithreading-Algorithmus:

    public class ThreadedQuick extends Thread
    {
        final int MAX_THREADS = Runtime.getRuntime().availableProcessors();

        CountDownLatch doneSignal;
        static int num_threads = 1;

        int[] my_array;
        int start, end;

        public ThreadedQuick(CountDownLatch doneSignal, int[] array, int start, int end) {
            this.my_array = array;
            this.start = start;
            this.end = end;
            this.doneSignal = doneSignal;
        }

        public static void reset() {
            num_threads = 1;
        }

        public void run() {
            quicksort(my_array, start, end);
            doneSignal.countDown();
            num_threads--;
        }

        public void quicksort(int[] array, int start, int end) {
            int len = end-start+1;

            if (len <= 1)
                return;

            int pivot_index = medianOfThree(array, start, end);
            int pivotValue = array[pivot_index];

            swap(array, pivot_index, end);

            int storeIndex = start;
            for (int i = start; i < end; i++) {
               if (array[i] <= pivotValue) {
                   swap(array, i, storeIndex);
                   storeIndex++;
               }
            }

            swap(array, storeIndex, end);

            if (num_threads < MAX_THREADS) {
                num_threads++;

                CountDownLatch completionSignal = new CountDownLatch(1);

                new ThreadedQuick(completionSignal, array, start, storeIndex - 1).start();
                quicksort(array, storeIndex + 1, end);

                try {
                    completionSignal.await(1000, TimeUnit.SECONDS);
                } catch(Exception ex) {
                    ex.printStackTrace();
                }
            } else {
                quicksort(array, start, storeIndex - 1);
                quicksort(array, storeIndex + 1, end);
            }
        }
    }

Hier ist, wie ich es anfange:

ThreadedQuick.reset();
CountDownLatch completionSignal = new CountDownLatch(1);
new ThreadedQuick(completionSignal, array, 0, array.length-1).start();
try {
    completionSignal.await(1000, TimeUnit.SECONDS);
} catch(Exception ex){
    ex.printStackTrace();
}

Ich habe dies mit Arrays.sort und einem ähnlichen sequentiellen schnellen Sortieralgorithmus getestet. Hier sind die Timing-Ergebnisse auf einem Intel-Duell-Core-Dell-Laptop in Sekunden:

Elemente: 500.000, fortlaufend: 0,068592, mit Gewinde: 0,046871, Arrays.sort: 0,079677

Elements: 1,000,000, sequentiell: 0,14416, mit Gewinde: 0,095492, Arrays.sort: 0,167155

Elemente: 2.000.000, fortlaufend: 0.301666, Gewinde: 0.205719, Arrays.sort: 0.350982

Elemente: 4.000.000, fortlaufend: 0.623291, Gewinde: 0.424119, Arrays.sort: 0.712698

Elemente: 8.000.000, fortlaufend: 1.279374, Gewinde: 0.859363, Arrays.sort: 1.487671

Jede Zahl oben ist die durchschnittliche Zeit von 100 Tests, wobei die drei niedrigsten und die drei höchsten Fälle herausgerechnet werden. Ich habe Random.nextInt (Integer.MAX_VALUE) verwendet, um für jeden Test ein Array zu generieren, das alle 10 Tests einmal mit demselben Startwert initialisiert wurde. Jeder Test bestand aus dem Timing des angegebenen Algorithmus mit System.nanoTime. Nach der Mittelung habe ich auf sechs Dezimalstellen gerundet. Und natürlich habe ich nachgesehen, ob jede Sortierunghat funktionier.

Wie Sie sehen, steigt die Geschwindigkeit zwischen sequenziellen und Thread-Fällen in jeder Testreihe um ca. 32%. Wie ich oben gefragt habe, sollte ich nicht mehr als das erwarten?