Ява - многопоточная сортировка

Question

Я работал над различными вариантами сортировки по Radix. Сначала я использовал цепочку, которая была очень медленной. Затем я перешел к использованию сортировки счетчиков, используя val % (10 * pass), и совсем недавно превратил его в соответствующие байты и отсортировал их по числу, что позволяет мне также сортировать по отрицательным значениям.

Я хотел попробовать это с многопоточностью, и могу заставить его работать только половину времени. Мне было интересно, если кто-то может помочь посмотреть на мой код, и посмотреть, где я не так с потоками. У меня есть каждый поток отсчета сортировать каждый байт. Спасибо:

public class radixSort {

    public int[] array;
    public int arraySize, arrayRange;
    public radixSort (int[] array, int size, int range) {
        this.array = array;
        this.arraySize = size;
        this.arrayRange = range;
    }
    public int[] RadixSort() {
        Thread[] threads = new Thread[4];
        for (int i=0;i<4;i++)
            threads[i] = new Thread(new Radix(arraySize, i));
        for (int i=0;i<4;i++)
            threads[i].start();
        for (int i=0;i<4;i++)
            try {
                threads[i].join();
            } catch (InterruptedException e) {
                e.printStackTrace();
            }
        return array;
    }
    class Radix implements Runnable {
        private int pass, size;
        private int[] tempArray, freqArray;
        public Radix(int size, int pass) {
            this.pass = pass;
            this.size = size;
            this.tempArray = new int[size];
            this.freqArray = new int[256];
        }
        public void run() {
            int temp, i, j;
            synchronized(array) {
                for (i=0;i<size;i++) {
                    if (array[i] <= 0) temp = array[i] ^ 0x80000000;
                    else temp = array[i] ^ ((array[i] >> 31) | 0x80000000);
                    j = temp >> (pass << 3) & 0xFF;
                    freqArray[j]++;
                }
                for (i=1;i<256;i++)
                    freqArray[i] += freqArray[i-1];
                for (i=size-1;i>=0;i--) {
                    if (array[i] <= 0) temp = array[i] ^ 0x80000000;
                    else temp = array[i] ^ ((array[i] >> 31) | 0x80000000);
                    j = temp >> (pass << 3) & 0xFF;
                    tempArray[--freqArray[j]] = array[i];
                }
                for (i=0;i<size;i++)
                    array[i] = tempArray[i];
            }
        }
    }
}

Answer 1

Существует основная проблема с этим подходом. Чтобы получить выгоду от многопоточности, вы должны дать каждому потоку непересекающуюся задачу по сравнению с другими шагами. От synchonizing на array вы сделали так, что одновременно работает только один поток, то есть вы получаете все издержки потоков без каких-либо преимуществ.

Подумайте о способах разделения задачи, чтобы потоки работали параллельно. Например, после первого прохода все элементы с 1 старшим битом будут находиться в одной части массива, а элементы с нулевым старшим битом - в другой. Вы можете иметь один поток, работающий с каждой частью массива без синхронизации.

Обратите внимание, что ваш runnable должен полностью измениться, чтобы он прошел один проход в указанном подмножестве массива, а затем породил потоки для следующего прохода.

Answer 2

Помимо неправильных имен классов и методов (класс должен начинаться с заглавной буквы, метод не должен), я вижу, что вы синхронизируете все работы потоков в массиве. Так что на самом деле это совсем не параллельно.

Answer 3

Я совершенно уверен, что вы не можете по-настоящему распараллелить RadixSort, по крайней мере, так, как вы пытаетесь. Кто-то отметил, что вы можете сделать это путем "разделяй и властвуй", поскольку вы сначала упорядочиваете по старшим битам, но на самом деле RadixSort работает, сравнивая сначала младшие биты, поэтому вы не можете по-настоящему разделить и завоевать., Массив может быть полностью переставлен после каждого прохода.

Ребята, докажите, что я не прав, но я думаю, что по сути невозможно распараллелить этот алгоритм, как вы пытаетесь. Может быть, вы можете распараллелить (считать) сортировку, которая выполняется внутри каждого прохода, но помните, что ++ не является атомарной операцией.