algorithm b

アルゴリズムb 第8回

比較によらないソート(2)

基数ソートの性質

ビンソートも分布数え上げソートも、キーがある範囲にある場合にだけ利用可能です。すなわち、キーの種類が多すぎると使うことができません。

キーの種類が多い場合は、キーを分割して、小さいキー（サブキー, subkey）に対する「安定な」ソートを（下の桁から上の桁へと）繰り返し適用することによってソートを行います。これが「基数ソート(Radix Sort)」です。

サブキーでソートするアルゴリズムは安定であれば何でも構わないのですが、 $O(n)$ のアルゴリズム、つまり分布数え上げソートを使うのが普通です。キーの分割は、分布数え上げソートの実行回数と作業領域の大きさを考慮して決めることになります。

下の RadixSortData クラスは、キーの最大ビット幅がデフォルトでは 16ビットになっています。すなわち、デフォルトではキーは $0$ 〜 $65535$ ($= 2^{16}-1$)の値を取ることができます。この値はsetKeyBitWidth()メソッドで変更できます。

下の RadixSort クラスは、サブキーのビット幅がデフォルトでは 4ビットになっています。すなわち、デフォルトではキーを 4ビットずつのサブキーに分割してソートすることになります。この値はsetSubKeyBitWidth()メソッドで変更できます。

radixsortdata0.txt

10
2f38 要素0
2fb7 要素1
9328 要素2
a400 要素3
000f 要素4
0002 要素5
0844 要素6
ef85 要素7
289a 要素8
2f30 要素9

RunRadixSort.javaの実行例

$ javac RunRadixSort.java   
$ java RunRadixSort -d < radixsortdata0.txt   
ソート前
{12088(2f38):要素0 12215(2fb7):要素1 37672(9328):要素2 41984(a400):要素3
 15(f):要素4 2(2):要素5 2116(844):要素6 61317(ef85):要素7 10394(289a):要素8
 12080(2f30):要素9 }
Pass 1 -------------------
{41984(a400):要素3 12080(2f30):要素9 2(2):要素5 2116(844):要素6
 61317(ef85):要素7 12215(2fb7):要素1 12088(2f38):要素0 37672(9328):要素2
 10394(289a):要素8 15(f):要素4 }
Pass 2 -------------------
{41984(a400):要素3 2(2):要素5 15(f):要素4 37672(9328):要素2
 12080(2f30):要素9 12088(2f38):要素0 2116(844):要素6 61317(ef85):要素7
 10394(289a):要素8 12215(2fb7):要素1 }
Pass 3 -------------------
{2(2):要素5 15(f):要素4 37672(9328):要素2 41984(a400):要素3 2116(844):要素6
 10394(289a):要素8 12080(2f30):要素9 12088(2f38):要素0 61317(ef85):要素7
 12215(2fb7):要素1 }
Pass 4 -------------------
{2(2):要素5 15(f):要素4 2116(844):要素6 10394(289a):要素8 12080(2f30):要素9
 12088(2f38):要素0 12215(2fb7):要素1 37672(9328):要素2 41984(a400):要素3
 61317(ef85):要素7 }

{2(2):要素5 15(f):要素4 2116(844):要素6 10394(289a):要素8 12080(2f30):要素9
 12088(2f38):要素0 12215(2fb7):要素1 37672(9328):要素2 41984(a400):要素3
 61317(ef85):要素7 }

出力がわかりにくいので、わかりやすいように縦に並べてみました。下の桁から4ビットずつ選んではソートしている様子がわかると思います。この例では、16bitのキーを4bitずつに分割してソート繰り返すので、全体としては4回の繰り返しでソートが終了します。

ソート前

Pass 1

Pass 2

Pass 3

Pass 4

2f38:要素0
2fb7:要素1
9328:要素2
a400:要素3
000f:要素4
0002:要素5
0844:要素6
ef85:要素7
289a:要素8
2f30:要素9

a400:要素3
2f30:要素9
0002:要素5
0844:要素6
ef85:要素7
2fb7:要素1
2f38:要素0
9328:要素2
289a:要素8
000f:要素4

a400:要素3
0002:要素5
000f:要素4
9328:要素2
2f30:要素9
2f38:要素0
0844:要素6
ef85:要素7
289a:要素8
2fb7:要素1

0002:要素5
000f:要素4
9328:要素2
a400:要素3
0844:要素6
289a:要素8
2f30:要素9
2f38:要素0
ef85:要素7
2fb7:要素1

0002:要素5
000f:要素4
0844:要素6
289a:要素8
2f30:要素9
2f38:要素0
2fb7:要素1
9328:要素2
a400:要素3
ef85:要素7

アルゴリズムB 演習

作成したプログラムが正しく動作することを確認したら、それぞれの提出先に提出しなさい。

提出した後は、正しく提出されていることを http://ynitta.com/class/algoB/local/handin/ で必ず確認しておいて下さい。

課題提出〆切は次回の講義開始時刻です。

課題8a: 基数ソートのプログラムを動かしてみよう

提出ファイル	RadixSort.java
コメント欄:	RunRadixSort.javaに例と同じデータを与えた時の出力
提出先:	「宿題提出Web:アルゴリズムB：課題8a」 http://ynitta.com/class/algoB/local/handin/up.php?id=kadai8a

上記の RadixSortData.java, RadixSort.java, RunRadixSort.java を自分で入力し、動作させてみましょう。途中経過を表示させてみて、動作を確実に理解して下さい。

RadixSortDataクラスについて。

KeyBitWidthとMaxKeyの関係をよく理解して下さい。
2のKeyBitWidth乗を計算して1を引いた値はどういう意味を持つのでしょうか。
また、そもそもstatic { } という部分はいつ実行されるのでしょうか？

RadixSortクラスについて

SubKeyBitWidthとMaxSubKeyの関係をよく理解して下さい。
ここでも、2のSubKeyBitWidth乗を計算して1を引いているのはどうしてでしょうか。
また、sortメソッドのfor文の中で bit という変数を SubKeyBitWidthずつ増加させながら、データのキーを変数 bitの値だけ右シフトし、さらにMaxSubKeyとANDの計算をしています。これは何をやっているのでしょうか？

課題8b: 基数ソートの応用

提出ファイル	RunRadixSort2.java
コメント欄:	http://ynitta.com/class/algoB/radixsortdata2.txt を入力として与えたときの出力と実行速度。
提出先:	「宿題提出Web:アルゴリズムB：課題8b」 http://ynitta.com/class/algoB/local/handin/up.php?id=kadai8b

入力として、40bitの整数が複数個与えられる。ただし、これらの整数値は10桁の16進数で表現されている。

与えられたデータのうちから、小さい方から3個と、大きい方から 3個を選び表示するプログラム RunRadixSort2.java を作成しなさい。 1行に1個の数字を、小さい順に10桁の16進数として出力するものとする。

ソートする際には SubKeyのビット幅を8bitに設定した状態でRadixSortクラスの sortメソッドを利用することを条件とします。

入力データの形式は次の通り。

$N$
$H_{1,1} ~~ H_{1,2} ~~ H_{1,3} ~~ \cdots ~~ H_{1,10}$
$H_{2,1} ~~ H_{2,2} ~~ H_{2,3} ~~ \cdots ~~ H_{2,10}$
$\cdots$
$H_{N,1} ~~ H_{N,2} ~~ H_{2,3} ~~ \cdots ~~ H_{N,10}$

$N$ はデータの個数である。 $H_{i,j}$ は $0 \mbox{〜} 9$, $a \mbox{〜} f$の間の1文字を表す。すなわち、$H_{i,1} ~~ H_{i,2} ~~ \cdots ~~ H_{i,10}$ の並びは長さ10の文字列であり、10桁の16進数を表す。

$6 \leqq N \leqq 1000000$
$0000000000_{\mbox{(16進数)}} \leqq H_{i,1} ~~ H_{i,2} ~~ \cdots ~~ H_{i,10} \leqq ffffffffff_{\mbox{(16進数)}}$

が成り立っていると仮定して構わない。

100万個の40bitデータが http://ynitta.com/class/algoB/radixsortdata2.txt に用意されている。これを入力として与えたときの出力と実行時間を答えなさい。

[注意1]

10桁の16進数は40bitなので、int やIntegerでは扱えないことに注意して下さい。 longや Longを使うことになります。

[注意2]

RadixSortクラスは RadixSortDataオブジェクトの配列をソートしますが、今回はRadixSortDataオブジェクトの key だけに着目すればよいので、生成したRadixSortDataオブジェクトの dataフィールドには元の16進数の文字列表現を入れておくものとします。

[注意3]

CPUにもよりますが、radixsortdata2.txtの処理は数秒(2〜4秒)程度で終わるはずです。

[注意4]

環境によってはJava実行環境のHeapが足りなくなってエラーを起こすことがあります。その場合はHeap空間を広げて実行させます。 java の -Xmxオプションでヒープの最大サイズを指定します。

    [使用例]ヒープの最大値を128Mバイトに設定して実行する例
    $ time (java -Xmx128M RunRadixSort2 < radixsortdata2.txt)

radixsortdata1.txt

10
39ae5489f0
9912c8a11d
00be1ffc83
3504ed8352
5db6b7f7b4
99d036bbf4
88ba7e51cb
ac0df9dc08
65cd216015
7e3f816f94

RunRadixSort2.javaの実行例

$ javac RunRadixSort2.java   
$ java RunRadixSort2 <radixsortdata1.txt   
00be1ffc83
3504ed8352
39ae5489f0
9912c8a11d
99d036bbf4
ac0df9dc08

RunRadixSort2がradixsortdata1.txtを処理する様子

Keyの長さを40ビット、SubKeyの長さを8ビットに設定して基数ソートを行ったので、 5回SubKeyによるソートを行っています。 16進数で2桁ずつ、すなわち8ビットずつに分割されたキーでソートされていく様子を下の表に示します。

初期状態

Pass 1

Pass 2

Pass 3

Pass 4

Pass 5

39ae5489f0
9912c8a11d
00be1ffc83
3504ed8352
5db6b7f7b4
99d036bbf4
88ba7e51cb
ac0df9dc08
65cd216015
7e3f816f94


ac0df9dc08
65cd216015
9912c8a11d
3504ed8352
00be1ffc83
7e3f816f94
5db6b7f7b4
88ba7e51cb
39ae5489f0
99d036bbf4


88ba7e51cb
65cd216015
7e3f816f94
3504ed8352
39ae5489f0
9912c8a11d
99d036bbf4
ac0df9dc08
5db6b7f7b4
00be1ffc83


00be1ffc83
65cd216015
99d036bbf4
39ae5489f0
88ba7e51cb
7e3f816f94
5db6b7f7b4
9912c8a11d
3504ed8352
ac0df9dc08


3504ed8352
ac0df9dc08
9912c8a11d
7e3f816f94
39ae5489f0
5db6b7f7b4
88ba7e51cb
00be1ffc83
65cd216015
99d036bbf4


00be1ffc83
3504ed8352
39ae5489f0
5db6b7f7b4
65cd216015
7e3f816f94
88ba7e51cb
9912c8a11d
99d036bbf4
ac0df9dc08