アルゴリズムB 第5回


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

基数ソートの性質

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

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

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

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

RadixSortData.java
授業で配布するプリントを参照して下さい。


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

RadixSort.java
授業で配布するプリントを参照して下さい。


RunRadixSort.java
授業で配布するプリントを参照して下さい。

radixsortdata0.txt
授業で配布するプリントを参照して下さい。


RunRadixSort.javaの実行例
$ javac RunRadixSort.java
o$ 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://nw.tsuda.ac.jp/class/algoB/local/handin/ で必ず確認しておいて下さい。

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

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

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

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

RadixSortDataクラスについて。

RadixSortクラスについて

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

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

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

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

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

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

  N
  H1,1H1,2H1,3...H1,10
  H2,1H2,2H2,3...H2,10
  H3,1H3,2H3,3...H3,10

  ...
  HN,1HN,2HN,3...HN,10

Nはデータの個数である。 Hi,jは 0〜9, a〜fの間の1文字を表す。 すなわち、Hi,1 ... Hi,1 の並びは 長さ10の文字列であり、10桁の16進数を表す。

    6 ≦ N ≦ 1000000
    0000000000 (16進数) ≦ Hi,1Hi,2...Hi,10 ≦ ffffffffff
が成り立っていると仮定して構わない。

100万個の40bitデータが http://nw.tsuda.ac.jp/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)

RunRadixSort2.java
授業で配布するプリントを参照して下さい。

radixsortdata1.txt
授業で配布するプリントを参照して下さい。



RunRadixSort2.javaの実行例
授業で配布するプリントを参照して下さい。

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