第15章 基数整列

目次

15.1. ヒストグラム
15.2. Bucket Scan
15.3. Reduction(還元)
15.3.1. 結合性
15.3.2. 交換性
15.4. Prefix Sumへの適用
15.5. up-sweep(掃き上げ)
15.6. down-sweep(掃き下げ)
15.7. 並び替え(Rank)
15.8. 実装例(CPU)
15.8.1. ヒストグラム
15.8.2. Prefix-Sum
15.8.3. 並び替え
15.9. 実装例(GPU)
15.9.1. Up-sweep(GPU)
15.9.2. down-sweep
15.9.3. 並び替え(rearrange)
15.9.4. マルチキュー実装(CPU+GPU)

重要

この項目では基数、カウンティングソート等の情報工学の基礎については前提知識とします。

基数整列は、複数桁の数値や文字列を、各桁のバイトを使用して整列するのに用います。各桁が表す整数(文字)のバイトサイズはRadix Rとするため、Radix Sortと呼びます。

基数整列アルゴリズムは、入力桁(ソートキー)をR個に分割するものとします。例えば基数が1バイト(8-bit)であれば、256個に分割します。基数の単位は一般に「Bucket」(バケット)または「Bin」(ビン)と呼称します。

表15.1 バケットのバイト構造

ソートキー内のバイト0
ソートキー内のバイト1
...
ソートキー内のバイトN-1
Bucket[0]
Bucket[1]
...
Bucket[N-1]

基数整列にはMSDとLSDの2種類がありますが、MSD(Most Significant Digit)はソーティングキーを左数えします。反対にLSD(Least Significant Digit)は右からソーティングキーを数えていきます。

基数配列(Radix Sort)の並列化についてはいくつかありますが、一般的な参考文献となる以下のものを使います。

「Radix Sort for Vector Multiprocessors. Marco Zagha, Guy E. Blelloch」

Zagha & Blellochのアルゴリズムは3部で構成されます。

これらのステップは「カウンティングソート」(バケットソートが用いられることもある)に基づいています。

ソート
    // K: 未整列データ
    // N-1: データサイズ
    // D: ソーティングキー
    do j = 0 to N - 1
        D[j] = K[j] & R
    基数キーのヒストグラム
        // R: (2のr乗 - 1)
        do i = 0 to (2のr乗 - 1)
            Bucket[i] = 0
        do j = 0 to N – 1
            Bucket[D[j]] = Bucket[D[j]] + 1 //(1)
    バケットのスキャン(Prefix-Sum)
        Sum = 0
        do i = 0 to 2のr乗 – 1
            Val = Bucket[i]
            Bucket[i] = Sum //(2)
            Sum = Sum + Val
    並び替え
       do j = 0 to N – 1
            A = Bucket[D[j]]
            // R: 整列データ
            // K: 未整列データ
            R[A] = K[j] //(3)
            Bucket[D[j]] = A + 1 //(4)

(1)

D[j]をインデックスとしてBucketをインクリメント。ソーティングキーのヒストグラムを作ります。

(2)

Prefix sumを計算します。累積ヒストグラムと同じものです。

(3)

整列データの配列を更新します。

(4)

Aの位置をインクリメントして、次に更新する整列データの配列の添字を移動

注記

累積ヒストグラムについての定義は以下の式で表せます。

images/cumulative_histogram.png

(1)のnはビン(バケツ)を指し、(2)のMは累積値を示します。

Copyright 2018-2019, by Masaki Komatsu