22.7. 実装例（CPU）

Prev		Next

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

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

DATA_SIZE = 16
BIN_SIZE = 3
W = 4
raw_data = randint(0, BIN_SIZE, DATA_SIZE*W).astype(np.uint8)
data = raw_data.reshape((DATA_SIZE, W))

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

raw_tmp = np.zeros(DATA_SIZE*W).astype(np.uint8)
tmp = raw_tmp.reshape((DATA_SIZE, W))

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

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

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

for d in reversed(range(W)):
    //dの列を整列

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

22.7.1. ヒストグラム

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

count = np.zeros(BIN_SIZE+1).astype(np.uint32)

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

for i in range(0, DATA_SIZE):
    count[data[i][d] + 1] += 1

22.7.2. Prefix-Sum

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

for k in range(1, BIN_SIZE):
    count[k] += count[k-1]

22.7.3. 並び替え

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

for i in range(DATA_SIZE):
    tmp[count[data[i][d]]] = data[i]
    count[data[i][d]] += 1

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

for i in range(DATA_SIZE):
    data[i] = tmp[i]

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

RadixSortCPUTest.py.

from numpy.random import *

# Set the seed to 0
np.random.seed(0)

DATA_SIZE = 16
BIN_SIZE = 3
W = 4
raw_data = randint(0, BIN_SIZE, DATA_SIZE*W).astype(np.uint8)
data = raw_data.reshape((DATA_SIZE, W))

raw_tmp = np.zeros(DATA_SIZE*W).astype(np.uint8)
tmp = raw_tmp.reshape((DATA_SIZE, W))

for d in reversed(range(W)):
    count = np.zeros(BIN_SIZE+1).astype(np.uint32)
    for i in range(0, DATA_SIZE): #(1)
        count[data[i][d] + 1] += 1
    for k in range(1, BIN_SIZE): #(2)
        count[k] += count[k-1]
    for i in range(DATA_SIZE): #(3)
        tmp[count[data[i][d]]] = data[i]
        count[data[i][d]] += 1
    for i in range(DATA_SIZE): #(4)
        data[i] = tmp[i]

print(data)

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

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

/Library/Frameworks/Python.framework/Versions/3.5/bin/python3.5 /Users/komatsu/PycharmProjects/MyPythonProject/RadixSortCPUTest.py
[[0 0 0 2]
 [0 0 1 1]
 [0 1 1 1]
 [0 1 2 2]
 [0 2 0 0]
 [0 2 0 1]
 [1 0 0 0]
 [1 0 2 1]
 [1 1 0 2]
 [1 1 2 2]
 [1 2 0 2]
 [1 2 2 0]
 [2 0 1 2]
 [2 0 2 1]
 [2 1 2 1]
 [2 2 2 2]]

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