2

私は基数ソートのさまざまなバリエーションに取り組んできました。最初はチェインを使用していましたが、これは非常に遅かったです。次に、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];
            }
        }
    }
}
4

3 に答える 3

2

このアプローチには基本的な問題があります。マルチスレッドの利点を得るには、各スレッドに他のスレッドと比較して重複しないタスクを与える必要があります。これによりsynchonizing、array一度に 1 つのスレッドのみが機能するようになりました。つまり、スレッドのオーバーヘッドをすべて得て、何のメリットもありません。

スレッドが並行して動作するようにタスクを分割する方法を考えてください。たとえば、最初のパスの後、上位ビットが 1 のすべての項目が配列の一方の部分に配置され、上位ビットが 0 の項目が他方の部分に配置されます。同期せずに、アレイの各部分で 1 つのスレッドを動作させることができます。

runnable配列の指定されたサブセットで 1 つのパスを実行し、次のパスのスレッドを生成するように完全に変更する必要があることに注意してください。

于 2012-12-17T20:39:01.187 に答える
0

少なくともあなたがしようとしている方法では、RadixSortを実際に並列化できないと確信しています。上位ビットから順に並べると分割統治できると誰かが指摘していましたが、実はRadixSortは下位ビットを先に比較することで機能するため、実際には分割統治はできません。 . 配列は基本的に、各パスの後に完全に並べ替えることができます。

みんな、私が間違っていることを証明してください。しかし、あなたがしようとしているように、このアルゴリズムを並列化することは本質的に不可能だと思います。各パス内で行われる (カウント) ソートを並列化できるかもしれませんが、++ はアトミック操作ではないことに注意してください。

于 2012-12-17T20:53:59.210 に答える
0

間違ったクラス名とメソッド名 (クラスは大文字で始める必要がありますが、メソッドは大文字で始める必要はありません) に加えて、配列上のすべてのスレッド作業を同期させていることがわかります。したがって、実際にはまったく平行ではありません。

于 2012-12-17T20:38:44.953 に答える