Быстрая сортировка Многопоточность

Question

Я бы хотел реализовать алгоритм быстрой сортировки для двумерного массива с многопоточностью.

Он работает очень быстро в однопоточном режиме, но теперь я попытался ускорить его. Это мой код для правильной сортировки каждой части массива 2d (скорость самого алгоритма сортировки должна быть очень высокой). Его непосредственно работает на "с".

public static void sort(int[][] c) {
    int[][] a = new int[][] { { 0, -4, 1, 2 }, { 1, 0, 3 }, { 2, 3, 0 } };
    for (int i = 0; i < c.length; i++) {
        sort(c[i],0,c[i].length-1);
    }

}

Я пытался узнать: разбить цикл for на маленькие «петли», которые выполняют задачу из петель «x», но это замедляет алгоритм.

Может кто-нибудь помочь мне ускорить это?

Answer 1

Пара возможностей:

public static void sort(int[][] c) {
    for (int i = 0; i < c.length; i++) {
        //sort(c[i],0,c[i].length-1);
        Arrays.sort(c[i]);
    }
}

public static void parallelSort(int[][] c) {
    Arrays.asList(c).parallelStream().forEach(d -> Arrays.sort(d));
}

public static void threadedSort(int[][] c) throws InterruptedException {
    int count = 4;
    Thread[] threads = new Thread[count];
    for (int i = 0; i < count; i++) {
        final int finalI = i;
        threads[i] = new Thread(
                () -> sortOnThread(c, (c.length / count) * finalI, c.length / count), 
                "Thread " + i
            );
        threads[i].start();
    }
    for (Thread thread : threads) {
        thread.join();
    }
}

private static void sortOnThread(int[][] c, int first, int length) {
    for (int i = first; i < first + length; i++) {
        Arrays.sort(c[i]);
    }
}

public static void main(String[] args) throws InterruptedException {
    int[][] c = new int[10_000_000][75];

    shuffle(c);
    System.out.println("Starting sort()");
    long before = System.currentTimeMillis();
    sort(c);
    System.out.println("Took " + (System.currentTimeMillis() - before) + "ms");

    shuffle(c);
    System.out.println("Starting parallelSort()");
    before = System.currentTimeMillis();
    parallelSort(c);
    System.out.println("Took " + (System.currentTimeMillis() - before) + "ms");

    shuffle(c);
    System.out.println("Starting threadedSort()");
    before = System.currentTimeMillis();
    threadedSort(c);
    System.out.println("Took " + (System.currentTimeMillis() - before) + "ms");
}

private static void shuffle(int[][] c) {
    for (int i = 0; i < c.length; i++) {
        for (int j = 0; j < c[i].length; j++)
            c[i][j] = j;
        Collections.shuffle(Arrays.asList(c[i]));
    }
}

, которые привели к этим временам на четырехъядерном процессоре (i5-2430M):

Starting sort()
Took 2486ms
Starting parallelSort()
Took 984ms
Starting threadedSort()
Took 875ms

Подход parallelStream() был наименьшим кодом,но явно идет с немного большими затратами (отправка каждой сортировки через ForkJoinPool), чем прямой поток.Это было более заметно, когда массив был меньше [100_000] [75]:

Starting sort()
Took 48ms
Starting parallelSort()
Took 101ms
Starting threadedSort()
Took 21ms

---

На всякий случай, если это полезно ... изначально при кодировании я обнаружил, что время для трех подходов было гораздо большеАналогично:

Starting sort()
Took 2403ms
Starting parallelSort()
Took 2435ms
Starting threadedSort()
Took 2284ms

Это оказалось потому, что я наивно выделял новые подмассивы каждый раз в своем методе shuffle().Ясно, что это вызвало много дополнительной работы с GC - даже недолгое время перед вызовом методов сортировки имело все значение.