再帰処理のクイックソート vs 非再帰処理のクイックソート

最近、会社の仕事で全く触ったこともない Excel-VBA を触るハメになりました・・・orz

理由は「大企業にありがちな問題。委託開発の甘い罠・・・」で書いた通りで、委託開発したソフトウェアが涙がでるようなできばえで納品されまして、仕方なくソースを解読しつつバグ修正や仕様通りに動いていないロジックの変更などをやっております。

さて、VBA って実はいろいろ不便なこともありまして、通常の言語のようなのソート関数が用意されていません。

Excel-VBA の常套手段としては、ワークシートの Sort メソッドを用いて、Excel のネイティブ機能としてソートをするようです。但しその場合は、Excel 上で扱えるレコード数の制約を受けるので、データ数が 65535 以下である必要があります。従って、大量のデータをソートする場合には自前でソート関数を作成する必要があります。

ソートアルゴリズムにはいろいろありますが、当然ながらバブルソートのようなバカソートを作ったのでは、そもそも大量データをソートしようとしているので実時間で終了しない計算量になってしまいます。

一般的に簡単に実装ができて高速なソートアルゴリズムと言えば、クイックソートが思い浮かびます。取りあえず再帰処理でクイックソートを作成してみると

なるエラーでプログラムが続行できなくなる不具合に悩みました。そこで、今まで記述したことのない非再帰処理のクイックソートに書き直すことになりました。

僕の本業は VBA でないので、これ以上詳しい Excel VBA のソートのお話しは以下のサイトをご覧下さい。

さて、以下の説明は VBA に実装する前に作成した Perl 版クイックソートに説明を切り替えます。

まずは単純に再帰処理のクイックソートを実装してみる

sub qsort_normal() {
	my $array = shift;
	my $left  = shift;
	my $right = shift;
	my ($i, $j, $pivot, $tmp);
	if ($left < $right) {
		$i = $left;
		$j = $right;
		$pivot = $array->[($left+$right)/2];
		while ($i <= $j) {
			while ($array->[$i] < $pivot) { $i++; }
			while ($array->[$j] > $pivot) { $j--; }
			if ($i <= $j) {
				$tmp = $array->[$i];
				$array->[$i] = $array->[$j];
				$array->[$j] = $tmp;
				$i++;
				$j--;
			}
		}
		&qsort_normal($array, $left, $j);
		&qsort_normal($array, $i, $right);
	}
}

さて、これは極めて一般的なクイックソートの記述方法です。 クイックソートの基本的な考え方は、全体の中から基準となる要素を１つ選んで枢軸とし、枢軸より小さい要素群と大きい要素群に分割する処理を、それ以上分割できなくなるまで繰り返すことで、オーダー N log(N)　でソート済みの要素群を生成するものです。

分割処理の繰り返しに再帰を使うことでシンプルな関数に仕上げることができるわけです。

次に非再帰版のクイックソートを実装してみる

sub qsort_array() {
	my $array = shift;
	my $left  = shift;
	my $right = shift;
	my ($i, $j, $pivot, $tmp, $sp);
	my @left_stack;
	my @right_stack;
	## スタック初期化
	$left_stack[0]  = 0;
	$right_stack[0] = $right;
	$sp = 1;
	
	## スタックが空になるまで繰り返す
	while( $sp > 0 ) {
		## スタック pop
		$sp--;
		$left  = $left_stack[$sp];
		$right = $right_stack[$sp];
		
		if ($left < $right) {
			$i = $left;
			$j = $right;
			$pivot = $array->[($left+$right)/2];
			while (1) {
				while ($array->[$i] < $pivot && $i < $right) { $i++; }
				while ($array->[$j] >= $pivot && $left < $j) { $j--; }
				if( $i >= $j ){ last; }
				$tmp = $array->[$i];
				$array->[$i] = $array->[$j];
				$array->[$j] = $tmp;
			}
			## スタック push
			if ($i - $left < $right - i) {
				$left_stack[$sp]    = $i + 1;
				$right_stack[$sp++] = $right;
				$left_stack[$sp]    = $left;
				$right_stack[$sp++] = $i - 1;
			} else {
				$left_stack[$sp]    = $left;
				$right_stack[$sp++] = $i - 1;
				$left_stack[$sp]    = $i + 1;
				$right_stack[$sp++] = $right;
			}
		}
	}
}

非再帰版の考え方は、再帰処理をループ処理とスタック変数を用意して自前で再現することです。再帰関数を呼び出す部分が、スタックへの push に相当します。再帰関数から抜ける処理が、スタックの pop に相当します。できるだけ一度に使うメモリ領域を小さく抑える工夫として、スタックへの push 処理は、枢軸を基準に分けられた要素群の、小さい方の範囲を優先して処理するように実装するのが一般的です。

さて、C 言語等で記述した場合のバイナリコードで、速度最優先でコードを記述する必要がある場合は、関数 Call 時のスタック処理が気になってくるものです。そこで実行速度を稼ぐために、あえて人間には理解しづらい非再帰処理で記述する場合もままあります。Perl で実装する場合は、所詮インタプリタなので当てはまらないかもしれません。

ということで実験。要素数 100 万のデータのソート処理で、この２つの実装の処理速度を比較してみました。ついでなので Perl の sort 関数との比較もしてみました。

my $size=1000000;
my @data1;
my $debug=0;
my $begin;
my $array1 = [];
my $array2 = [];
my $array3 = [];
## ソート済みデータの生成
foreach(0 .. $size) { push @data1, $_; }
## データのランダム化
while(@data1) {
	my $idx = int(rand(@data1));
	push @$array1, splice(@data1, $idx, 1);
}
@$array2 = @$array1;
@$array3 = @$array1;
## 再帰版クイックソートを実行
$begin = time;
&qsort_normal($array1,0,$size);
print "\nqsort_normal:",(time-$begin),"sec\n\n";
## 非再帰版クイックソートを実行
$begin = time;
&qsort_array($array2,0,$size);
print "\nqsort_array:",(time-$begin),"sec\n\n";
## Perl Sort関数を実行
$begin = time;
@$array3 = sort { $a <=> $b } @$array3;
print "\nsort:",(time-$begin),"sec\n\n";

非再帰版クイックソートの方が再帰版クイックソートよりも僅かに高速なようです。ネイティブコードで動作する Perl Sort 関数よりも、非再帰版クイックソートの方が速いのは驚きです。

ちなみに、Perl sort 関数はソースコード pp_sort.c の中を見るとわかるとおり、

と関数が定義されていているのがわかります。コメントを読む限り（間違ってるかもしれませんが・・・） プラットホームの違いで速度が安定しないマージソートからパフォーマンスは少し劣るけど全てのプラットホームで安定してた速度のクイックソートを使っていると書かれている気がします。ちなみに、再帰版のクイックソートで実装されていました。

再帰処理を非再帰処理で記述する方法をいろいろ調べていましたら、「配列を用いた非線形再帰プログラムからの再帰除去」なる論文を見つけました。要するに前述したとおり、ループ処理とスタック変数で再帰処理を再現するってことを語っています。興味がある方はどうぞ。