亀岡的プログラマ日記

京都のベッドタウン、亀岡よりだらだらとお送りいたします。

文字列向けバケツソートを実装してみたけれども全く使い物にならなかった。

@dankogaiさんの、

これを参考に、文字列用のバケットソートを作ってみたもののベンチマークとってみたら惨憺たる結果だった。
いや、多分原因は分かってるんですが。newし過ぎだし、計算かぶりまくりだし。

・・・そこら辺はプロファイリングして改善する、というエントリーを書くとして。とりあえず恥を晒してみます。

基本はバケツソート、というか基数ソートみたいなもんですね。

まず、文字列の一文字目を全比較して各バケツに放り込みます。int型では普通にその数字をインデックスに使えば良かでしたが、文字列だとそうは行かないので、その文字列の文字コード値を取ってきています。あと終端文字は読んでくれないので、長さを超えていたら終端文字総統のバイトを渡しています。
あとは何個も入るのでListのnewを必要なときにやる、と。

バケツに入れるまでは以下のような感じですね。

	 	//ソートしたい配列の要素がiに入ってると思ってください。
	 	//depth:現在の検索深さ(先頭から何文字目の比較を行なっているか)
		char index;
		if(i.Length <= depth)
		{
			index = (char)0x00;
		}
		else
		{
			index = i[depth];
		}
		if(bucketArray[index] == null)
		{
			bucketArray[index] = new List<string>();
		}
		bucketArray[index].Add(i);	

それから、バケツの中身を再度探索深さをひとつ進めて最実行します。再帰ですね。

bucketArray.Where(ele => ele != null).SelectMany(ele => ExecuteBucketSort(ele, depth + 1));

停止条件は、バケツ内の要素が一つだった場合と、全ての要素が現在の探索深さで終端文字列になっている場合(つまり、バケツ内がおんなじ場合)

			if(input.Count() <= 1)
			{
				return input;
			}
			if(input.All(ele => ele.Length <= depth))
			{
				return input;
			}

というわけで、まとめると以下のような感じ。

	public static IEnumerable<string> BucketSort(this IEnumerable<string> input)
	{
		return ExecuteBucketSort(input,0);
	}
	
	static IEnumerable<string> ExecuteBucketSort(IEnumerable<string> input, int depth)
	{
		if(input.Count() <= 1)
		{
			return input;
		}
		if(input.All(ele => ele.Length <= depth))
		{
			return input;
		}
		
		//Create backet
		var bucketArray = new List<string>[byte.MaxValue];
		
		//put inputs to backet
		foreach(var i in input)
		{
			char index;
			if(i.Length <= depth)
			{
				index = (char)0x00;
			}
			else
			{
				index = i[depth];
			}
			if(bucketArray[index] == null)
			{
				bucketArray[index] = new List<string>();
			}
			bucketArray[index].Add(i);	
		}
		return bucketArray.Where(ele => ele != null).SelectMany(ele => ExecuteBucketSort(ele, depth + 1));
	}

見てわかるように、どう考えてもnewが多すぎるとか、スッカスカの配列作っておいてヌルチェックして返すだとか、割とひどい。
まぁアルゴリズムを素直に実装したらこうなるわけで。

というわけで、ちょっと分析してみましょうかね・・・(続くの!?)