More than 3 years have passed since last update.

実用的な基数ソートを目指して

Last updated at 2021-10-20Posted at 2018-04-14

実用的な基数ソートを目指して

早いソートアルゴリズムとして、計数ソートを知っている人も多いと思います。
計数ソートは、配列の中身を精査して、中身の値に対するインデックス配列（バケツ）にカウントをしていき、次にそのバケツの中身を配列に書き戻していくという作業をすることにより、配列の大きさを n とすると、$O(n)$ の計算量でソートが完了させられるものです。
早いという名前の Quick sort の平均計算量が $O(n\log{n})$ なので、それよりも早いソートです。
ただし、配列の中に出てくる値が大きいと、その最大値に対するバケツが必要になってしまうというネックがあります。配列の中の値の最大値が 10万なら、バケツの大きさも 10万になってしまいます。

計数ソートのバケツの大きさ問題、および、値の最大値によって作るバケツの大きさを変えなければいけないという汎用性の無さを解決するために、基数ソートというアルゴリズムが考えられています。
基数ソートでは、値が複数の「桁」で出来ていることに注目し、桁ごとに計数ソートを繰り返すという方法を取ります。このとき、下の桁から順番にソートするというというのがコツです。
バケツの数は、桁の中に表れる最大数だけあればOKです。

一般的に使う int は 32ビットなので、8ビットづつに区切れば、int は 4桁の256数進と考えることができます。このため、基数ソートをプログラムするときは 8ビットづつにする事が多いです。
基数ソートの計算量は $O(n * 桁数)$ なので、配列サイズが 16 以上ならば Quick sort などよりも 8ビット計数ソートの方が早くなるように思えます（$log{16} = 4$ ですから）。
しかし、実際にプログラムを書いて試してみると、配列サイズが小さい時（100ぐらい）ならライブラリのソートよりも基数ソートの方が早いのに、配列サイズが大きくなると基数ソートが負けるという、理屈とは逆の結果が出ます。
ライブラリに備わっているソートは、前処理に時間をかけてでも、実際にソートを始めてしまうとバカっ早で終わるような設計になっているため、このような結果になるのだと想像します。最小値などが一度確定してしまうと、もうその配列にはアクセスしないのだと思います。
それに比べると基数ソートの 8ビット版では必ず 4回、全体を精査してしまいます。出てくる値の最大値が 255以下と仮定して精査を 1回で終わらせても、配列サイズが 300以上では負けます。そもそも値の最大値が小さいと分かっているというような場合は計数ソートを使えば良いので基数ソートを選択する意味がありません。
ライブラリのソートプログラムは、やはり相当に練り込まれて作られているので、これに勝つというのはなかなか困難なようですね。

基数ソートにはもう1つ、オリジナル配列と同じ大きさのメモリを別に使うという問題もあります。
基数ソートを素直にコーディングすると、バケツの中に Vector や ArrayList のような片方向リストを使う事になりますが、この片方向リストの中にはオリジナル配列の中身を全部持つ事になってしまうので、それだけメモリを食います。また、バケツではカウントだけしておいて、そのカウントから配列の出力位置を求めて別の配列に値を置き直すという方法でも同じくメモリを食います。
オリジナル配列と同じだけ別メモリを使うというのは、配列サイズが数十万とかあると、ちょっと躊躇しますよね。そこでまずは、別メモリを使わない（こういうのを In-placeアルゴリズムという）基数ソートのアルゴリズムを考えてみる事にします。

前提条件

プログラムは Java を使ってます。
ソートできる値は、正の int とする（負の数は考えない）。int の範囲であれば、桁数は何桁でも良い。
小さい順にソートする。

In-place な基数ソートの考え方

別メモリを使わないという事は、オリジナル配列を壊してそれをそのままソート結果として使う事です。
計数ソートや基数ソートでは、配列を頭から 1つ取得したら、その配列インデックスはもう使わないので削除する事にしましょう。そしてその代わりに、バケツの方に値を 1つ追加するのです。こうすれば、全体のメモリ量は変化しません。また、精査が終わったら、単純にバケツを連結すれば、それがソート結果になりますね。

この考え方を実現するには、オリジナル配列が、Vector や ArrayList のような片方向リストである必要があります。
Java でプログラムを書いてみようとして Vector や ArrayList のAPIドキュメントを見ましたが、どうも、単純に片方向リンクを繋げるという機能は無いようです（？）
そこで、自分で片方向リンクを書いてみる事にしました。

データ構造

まず、オリジナルのデータ構造を定義します。ここでは、 TestGoods というクラス名にして、製品の名前と値段をフィールドとして持つようにしてみました。ソートは値段の値でおこなうことにします。
このオリジナルデータ構造に、片方向リンクの為のフィールド next も加えておきます。

TestGoods.java

/** 製品 Class (test) */
public class TestGoods {
	public int price;		/// 値段
	public String name;	/// 製品名
	public TestGoods next;	/// 次の TestGoods への片方向リンク

	/** コンストラクタ */
	public TestGoods(int price) {
		this.price = price;
		next = null;
	}
}

テスト用なので getter,setter 無しで、public でアクセス可能にしてます。コンストラクタも値段に対するものしか用意していません（つまり、name は単なる飾りです）。

配列クラス（片方向リスト）

次に、TestGoods の配列クラス TestGoodsArray を作ります。メソッドは最低限必要な、add(), clear() と、connect() だけを作ってます。get() は無くて、直接 start などを触ります（行儀が悪いですね）。
今回は使わないのですが、 size フィールドも作っておきました。

TestGoodsArray.java

/** TestGoods の配列 */
public class TestGoodsArray {
	public TestGoods start;	// 片方向リンクの開始object
	public TestGoods last;	// 最後にあるobject
	public int size;
	
	/** コンストラクタ */
	public TestGoodsArray() {
		clear();
	}
	/** 中身を空にする */
	public void clear() {
		start = null;
		last = null;
		size = 0;
	}
	/** 要素を追加 */
	public boolean add(TestGoods goods) {
		size++;
		if (start == null) {
			start = goods;
			last = goods;
			return true;
		}
		last.next = goods;	// リンクを繋げる
		last = goods;
		return true;		// (一応、Collection.add の汎用規約どおり)
	}
	/** 要素同士を繋げる */
	public void connect(TestGoodsArray link) {
		if (link == null) { return; }
		if (start == null) {
			start = link.start;
			last = link.last;
			size = link.size;
			return;
		}
		size += link.size;
		last.next = link.start;
		last = link.last;
	}
}

基数ソート部分

ソートの実体は簡単です。
上記の説明どおり、int を8ビットで桁を区切るので、バケツのサイズは 256 になります。
ビット区切りを桁としたので、ファイル名を bitRadixSort としたのですが、ダサかったですかね。
ソートの返り値は、処理の実行時間(ナノ秒)としました。

どのような配列でも必ず4桁全部を調べるのでは無く、1回目の精査で最大値を調べ、上位の桁が使われていなかったらループ回数を減らすという処理にしてみました。こうすると、1桁の値しか表れない配列では、処理時間が 1/6 ほどになりました。
最初だけ最大値を求めるという部分のソースが醜い（ループ中で条件判定すると遅くなりそうだったので、同じようなループを2つ書いた）のですが、とりあえずご容赦を。

BitRadixSort.java

/**
 * 基数ソート （int を、8ビット毎 4桁として処理する）
 * 一般的な基数ソートに比べて、メモリを多く取ることはありません。
 * その代償として、元の配列を書き換えます。
 * */
public class BitRadixSort {
	TestGoodsArray[] bucket = new TestGoodsArray[256];	/// 桁のバケツ

	/** コンストラクタ */
	public BitRadixSort() {
		for (int i = 0; i < 256; i++) {
			bucket[i] = new TestGoodsArray();
		}
	}

	/**
	 * @param array	ソートしたい配列。配列は直接書き換わります。
	 * @return	ソートにかかった時間 (nano seconds)
	 */
	public long sort(TestGoodsArray array) {
		long stTime = System.nanoTime();		// 処理計測用
		int bitShift = 0;
		TestGoods link;
		int maxVal = Integer.MIN_VALUE;
		int i;
		int cnt = 4;		// 最大チェック桁数 = 4
		do {
			// bucket のクリア
			for (i = 0; i < 256; i++) {
				bucket[i].clear();
			}
			link = array.start;	// 配列の最初から
			// 値の桁に対するバケツに入れていく
			if (cnt == 4) {
				// ループの最初だけ、最大値を求める。また、ループの最初は bitShift をしなくても良い。
				do {
					int a = link.price;
					if (a > maxVal) { maxVal = a; }
					TestGoods linkOld = link;
					bucket[a & 255].add(linkOld);	// 桁のバケツに入れる
					link = link.next;		// 次の link へ
					linkOld.next = null;	// バケツに入れた link は切る
				} while (link.next != null);
			} else {
				// 2回目以降のループ
				do {
					int a = link.price;
					TestGoods linkOld = link;
					bucket[(a >> bitShift) & 255].add(linkOld);	// 桁のバケツに入れる
					link = link.next;		// 次の link へ
					linkOld.next = null;	// バケツに入れた link は切る
				} while (link.next != null);
			}
			// バケツを繋いでいって配列を作る
			array.clear();	// array は一旦、空にする
			for (i = 0; i < 256; i++) {
				if (bucket[i].start != null) {
					array.connect(bucket[i]);
				}
			}
			array.last.next = null; // 念のため

			bitShift += 8;	// 次の8ビットへ

			if (cnt == 4) {		// 最初のループだったら、値の最大値によってループ回数を小さくする
				if ((maxVal & 0xff000000) == 0) {
					cnt--;
					if ((maxVal & 0xff0000) == 0) {
						cnt--;
						if ((maxVal & 0xff00) == 0) {
							cnt--;
						}
					}
				}
			}
		} while (--cnt > 0);

		return System.nanoTime() - stTime;		// かかった時間を返す
	}
}

このソースを見れば分かりますが、ソート中に一度も new が使われておりません。単にリンクを継ぎはぎしているだけです。
これは、ちょっと早そうですね。

動作検証用の main クラス

最後は、動作検証用の main クラスです。
ソート後に、値が正しく（小さい順に）並んでいるかをテストしています。
また、時間比較のために Collections.sort も試してみています。API ドキュメントによると、Collections.sort のアルゴリズムは修正マージソートだと言う事です。
ソートする値はランダムで生成していますが、基数ソートと Collections.sort で同じランダム値を使って、値による優劣が出ないようにしています。

BitRadixTest.java

import java.util.*;

public class BitRadixTest {
	static final int N = 10000;		/// 配列の大きさ
	static final int VARMAX = 0x01000000;	/// 配列の中身の取り得る最大値

	/** main */
	public static void main(String[] args) {
		int i;
		TestGoodsArray array_Radix = new TestGoodsArray();	// BitRadix sort 用配列を確保
		ArrayList<TestGoods> array_Csort = new ArrayList<TestGoods>(N);	// Collections.sort 用配列を確保
		Random rnd = new Random();

		// テストデータの作成 (0 以上 VARMAX 未満の、ランダムな値で埋める)
		for (i = 0; i < N; i++) {
			int val = rnd.nextInt(VARMAX);
			array_Radix.add(new TestGoods(val));	// テスト用2つの配列に同じ値をセット
			array_Csort.add(new TestGoods(val));
		}
		
		// BitRadix sort
		BitRadixSort radix = new BitRadixSort();
		long time_bitRadix = radix.sort(array_Radix);

		// Csort
		long stTime = System.nanoTime();
		Collections.sort(array_Csort, new Comparator<TestGoods>() {
			public int compare(TestGoods obj1, TestGoods obj2) {
				return obj1.price - obj2.price;
			}
		});
		long time_Csort = System.nanoTime() - stTime;
		
		// データの検証
		int lastVal = Integer.MIN_VALUE;
		TestGoods link = array_Radix.start;
		do {
			int val = link.price;
			if (val < lastVal) {
				System.out.println("\nError !! (last=" + lastVal + ", val=" + val);
			}
			//System.out.print(val + ", ");	// 配列の内容を表示したい時はコメントを外す
			lastVal = val;
			link = link.next;
		} while (link != null);
		//System.out.println("");	// 配列の内容を表示したい時はコメントを外す
		System.out.println("Radix time  = " + time_bitRadix + " ns");
		System.out.println("Arrays time = " + time_Csort + " ns");
	}
}

実行結果

値の最大値を 0x10000000 (つまり、8 ビット基数での 4桁) とした場合の Collections.sort との実行時間を比較すると、私の環境下では以下のようになりました（値のランダム性により毎回実行時間は変わるので、あくまで一例です）。

配列サイズ	基数ソート	Collections.sort
100	171,262	948,590
1000	567,246	3,036,774
10000	4,531,319	17,188,987
100000	30,454,387	75,877,154

なんと！配列サイズに関わらず、全ての場合で基数ソートの方が早いという結果が出ました。
値の最大値を 200 (つまり、8 ビット基数での 1桁)にすると、配列サイズが 100 で 1/2、100000 で 1/6 ぐらいになります。
つまり、正の整数に限れば、このアルゴリズムの方が、Javaライブラリよりも早くソートできると言う事のようです。
Collections.sort の時間計測には比較演算用のクラスの生成が含まれているのに対して、基数ソートのバケツ生成が計測時間外という差はありますが、配列サイズが 10万とかだと誤差かなと思います。
データ構造の中に片方向リストを加えたのもズルかったですね。

宿題

宿題その1：負の数への対応

この BitRadixSort では、ソートする値が全て正の整数であることを前提にしています。
負の数にも対応するようにするには、4桁目のソートの最後でリンクを繋げるときに、バケツの128〜255までを先に繋げてから、次に 0〜127 を繋げれば良いです。
これは、int の表現が 2の補数となっていて、最上位ビットが負の記号になっていることによります。

宿題その2：TestGoodsArray クラスの一般化

TestGoodsArray クラスには get() さえ無いので、実装した方が良いでしょうね。
i 番目の要素を得るためには、リンクを巡る必要があります。i 番目が無かった時のエラー処理とかも必要です。
また、配列からオブジェクトを順次取り出すためのイテレータとかも、無いと不便でしょう。
（もしかしたら、リンクの結合に ArryList.addAll() を使うだけでもそれなりのスピードが出るかもしれません。未検証です）

宿題その3：一般的なオブジェクトへの対応

今回は TestGoods の中に直接片方向リンクのフィールドを置きましたが、これを一般的なオブジェクトでもソートできるようにしたいですね。
しかし、Integer[] array とかでもソートできるようにするのは、かなり大変に思います。
単に片方向リンクを外に出すだけではなく、どのフィールドでソートするのかをソートプログラムの引数に与えるようにしなければなりません。

ちなみに、小さい順番にソートするだけでなく、大きい順番にも対応するのは、バケツの繋ぎ方を逆順にすれば良いだけです。
しかしこれも、sort() の引数で逆順指定もできるようにするしか無いでしょうね。

ここまでやれば、int を短時間でソートできるライブラリとして多くの人が使えるように思います。
が、上のソースを見れば分かるとおり、私はプログラマとしては未熟なので、他のカスタマイズも含めて優秀な方にお願いしたい感じです。

宿題その4：小数点への対応

Javaで言う単精度浮動小数点数形式 float は、32ビットの大きさを持ちます。この形式は IEEE 754 で規定されていて、符号 1ビット、指数部 8ビット、仮数部 23ビットで構成されています。

指数部の方が仮数部より上位であるため、実は float でも、なんらかの方法で 4バイトとして取得できれば、基数ソートと全く同じアルゴリズムでソートできるはずです。その場合、処理スピードもそれなりに速い事が期待できます。
倍精度浮動小数点数では 64ビットとなってしまうので、さすがに基数ソートでは遅くなると想像します。

You get articles that match your needs
You can efficiently read back useful information
You can use dark theme

What you can do with signing up