Java - 线程基数排序

Question

我一直在研究基数排序的不同变体。起初我使用链接，这真的很慢。然后我开始使用计数排序，同时使用 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

这种方法有一个基本问题。要从多线程中获益，您需要为每个线程分配一个与其他线程相比不重叠的任务。通过在 array 上进行同步，一次只有一个线程在工作，这意味着您得到了线程的所有开销而没有任何好处。

想办法对任务进行分区，让线程并行工作。例如，在第一次遍历之后，所有高位为 1 的项目将在数组的一部分中，而高位为 0 的项目将在另一部分中。您可以让一个线程在不同步的情况下处理数组的每一部分。

请注意，您的 runnable 必须完全更改，以便它在数组的指定子集上执行一次传递，然后为下一次传递生成线程。