15.8. 実装例（CPU）

戻る		次へ

LSD Radix Sortは通常はデータから情報単位（ビット）を抽出しますが、この方法では基数整列のアルゴリズムが見えにくくなるので、今回は大幅に簡略化して配列として処理を行います。

並び変える元データは、8ビットのデータを2列持った配列となります。

byte[][] data = new byte[4][2];

データの数は4つとして、一時変数tmpで中間処理を保管します。

byte[][] tmp = new byte[N][W];

Nがデータ数、Wが元データのユニット数となります。WはASCIIコードにすると2つの文字を持つ配列を整列する問題となりますが、シンプルに数値の整列を問題とします。

LSDの定義としてデータ配列の右側から整列することになります。この前提ですとW-1, W-2, …, 0というように一つ一つ左に走査・デクリメントしていきます。

従ってアルゴリズムは以下の反復を行います。

for(int d = W-1; d>=0; d--) {
    //dの列を整列
}

反復してd列を整列するアルゴリズムが、前述のヒストグラム、Prefix-Sum(up-sweep、down-sweep)、並び替え（Rank）となります。

15.8.1. ヒストグラム

ヒストグラムはcount変数に保管します。8bitなので、要素数は256に決め打ちできます。

int[] count = new int[256];

ヒストグラムの算出は以下のようにします。

for(int i = 0; i<N; ++i) {
    count[a[i][d]+1]++;
}

15.8.2. Prefix-Sum

Prefix-Sum（up-sweepとdown-sweep）については、シーケンシャルに連続する要素を加算していきます。

for(int k = 1; k < 256; k++) {
    count[k] += count[k-1];
}

15.8.3. 並び替え

次に「並び替え（Rank）」ですが、元データとその値を、tmpで累積した頻度をマッチしていきます。

for(int i = 0; i < N; ++i) {
    tmp[count[a[i][d]]++] = a[i];
}

最後に次の反復をするための準備をします。tmpは添字dの一つに限定して整列したのですが、この整列した結果を元データの配列aに一旦更新します。

for(int i = 0; i < N; ++i) {
    a[i] = tmp[i];
}

tmpは次の反復には新たに整列しなおすので、aは毎回（配列右側から）最も新しい整列を更新していきます。

LSDSortTest.java.

package com.book.jocl.reduction;

public class LSDSortTest {

        public static void lsd_sort(byte[][] a) {
                int N = a.length;
                int W = a[0].length;
                byte[][] tmp = new byte[N][W];
                for(int d = W-1; d>=0; d--) {
                        int[] count = new int[256];
                        for(int i = 0; i<N; ++i) {
                                count[a[i][d]+1]++; //(1)
                        }
                        for(int k = 1; k < 256; k++) {
                                count[k] += count[k-1]; //(2)
                        }
                        for(int i = 0; i < N; ++i) {
                                tmp[count[a[i][d]]++] = a[i]; //(3)
                        }
                        for(int i = 0; i < N; ++i) {
                                a[i] = tmp[i]; //(4)
                        }
                }
        }

        public static void main(String[] args) {
                byte[][] data = new byte[4][2];
                data[0][0] = 1;
                data[0][1] = 4;
                data[1][0] = 23;
                data[1][1] = 23;
                data[2][0] = 5;
                data[2][1] = 1;
                data[3][0] = 2;
                data[3][1] = 2;
                lsd_sort(data);
                for(int i = 0; i < 4; i++) {
                        System.out.println(data[i][0]+":"+data[i][1]);
                }
        }

}

(1)	ヒストグラムの計算をします。
(2)	ヒストグラムの累積配列を計算（Up-SweepとDown-Sweep）します。
(3)	配列を並び変え、tmp配列に一時的に保管します。
(4)	tmp配列からa配列に要素をコピーします。

上記のサンプルプログラムの出力は以下のようになります。

1:4
2:2
5:1
23:23

これで整列の確認ができました。