珠玉のプログラミング - マイナーアニメ好き

　少し前に「珠玉のプログラミング」という本を買って読んでみた。研究室にも置いてあるのでちょくちょく見ていたのだけれど、いい本だと思ったので購入。

　この本の中に配列要素のローテートを効率的にするアルゴリズムの解説がある。
　一つは「お手玉の方法」。これはローテートさせる要素数をnとして、x[n]の要素をx[0]に、x[2n]の要素をx[n]に……という風に進めていくアルゴリズムのことである。最初はよく分からなかったが、短い配列を考えて自分の手でやってみるとちゃんとうまくいくことが分かった。ただ、このアルゴリズムの実装は非常に面倒だった。

void otedama(char[] array, final int n) {
	char temp;
	int agcd = gcd(array.length, n);
	for(int i = 0; i < agcd; i++) {
		temp = array[i];
		int j = i;
		do {
			array[j] = array[(j + n) % array.length];
			j = (j + n) % array.length;
		} while(j != i);
		array[array.length-+i] = temp;
	}
}

　Javaで上のような「お手玉の方法」のプログラムを書いてみた。gcdは最大公約数を求める関数である。一応正しく動くことを確認したけれど、バグがないとは言い切れない。かなり実装が面倒だったが、「最大公約数を使う」というヒントを上記の本から与えられていなければ、もっとおどろおどろしいコードが出来上がっていたことだろう。

　配列のローテートを実現する二つ目（実際本の中で紹介されたのは三番目だけれど）の方法は、配列を逆転させる方法である。
　ローテートによって配列の後ろ側に付くことになる部分配列をa、a以外の部分配列をbとすると、配列全体はabとして表される。もちろん、ローテートが実行されれば配列全体はbaのようになっているはずである。ここでaの配列を逆転させたものを $a^r$ とし、同様にbの配列を逆にしたものを $b^r$ とする。
　この $a^r$ と $b^r$ を結合させると $a^rb^r$ となり、さらにこの配列全体を逆転、つまり $(a^rb^r)^r$ のようにすると、その結果がローテートされた配列になっているというものである。どちらかといえば、こちらのほうが「お手玉の方法」よりも分かりやすい。そして実装も単純である。

void reverse(char[] array, final int n) {
	char temp;
	int i = 0;
	for(i = 0; i < n/2; i++) {
		temp = array[i];
		array[i] = array[n-i-1];
		array[n-i-1] = temp;
	}
	for(i = 0; i < (array.length-n)/2; i++) {
		temp = array[i+n];
		array[i+n] = array[array.length-i-1];
		array[array.length-i-1] = temp;
	}
	for(i = 0; i < array.length/2; i++) {
		temp = array[i];
		array[i] = array[array.length-i-1];
		array[array.length-i-1] = temp;
	}		
}

　逆転法の実装は上のようなコードになる。「お手玉の方法」のコードと比べると非常に書きやすかった。また、直感的にもわかりやすく保守がしやすいように思う。

　さて、ここで「お手玉の方法」と「逆転法」のオーダーはO(n)になる。「お手玉の方法」はローテートする個数分だけ全要素を移動させており、「逆転法」は二つの部分配列の逆転と配列全体の逆転を行っているからである。
　しかし、よく考えてみれば「お手玉の方法」の要素交換回数はn程度であり、「逆転法」の交換回数は2n程度あるので「お手玉の方法」の方がより優れている気がする。このことは上記の本の問題でも出されているのだが、どうやら「逆転法」の方が「お手玉の方法」よりも速いようだ。そして、その理由には「参照の局所性」が絡んでくるらしい。
　なるほど、「お手玉の方法」ではx[n]をx[0]に入れ、その後x[2n]にx[n]の値を入れる。つまりx[0]の後にx[2n]にアクセスしている。nの値が大きくなれば、それだけアクセス位置がバラバラになり、空間的局所性にもとづいてキャッシュされているデータを有効利用できなくなるというわけなのだろう。

　というわけで、上記のjavaプログラムを実行させてみた。上記の仮説でいくと「逆転法」の方が「お手玉の方法」よりも速いはずである。

	実行時間(s)
お手玉の方法	77.869
逆転法	79.315

　上の表は配列の長さを10000、ローテートさせる長さを1023とし、ローテート処理を100000回繰り返した際の処理時間である。
　・・・なぜか「逆転法」の方が遅い。おかしい、本には「逆転法」の方が速いような言い回しで書いてあるのに。

　なぜ、「逆転法」の方が遅くなったのか。考えても理由がよく分からない。配列を逆転させるアルゴリズムは、よくある両端の要素を交換していくものなので、キャッシュがしっかり働いてくれると思っていたのだが・・・。
　そういえば、前にネットをさまよっていたとき、配列の内側から処理を始めたほうが速い、という話を聞いたことがあった。とりあえず、藁をもつかむ気持ちで内側から逆転処理をするコードを書いてみた。

void reverse2(char[] array, final int n) {
	char temp;
	int flag = n % 2 == 0 ? 0 : 1;
	
	int i = (n+1)/2 -(1+flag), j = (n+1)/2;
	while(i >= 0 && j < n) {
		temp = array[i];
		array[i] = array[j];
		array[j] = temp;
		i--; j++;
	}

	flag = (array.length-n) % 2 == 0 ? 0 : 1;
	i = ((array.length-n+1)/2-(1+flag)) + n;
	j = ((array.length-n+1)/2) + n;
	while(i >= n && j < array.length) {
		temp = array[i];
		array[i] = array[j];
		array[j] = temp;
		i--; j++;
	}

	flag = array.length % 2 == 0 ? 0 : 1;
	i = (array.length+1)/2-(1+flag);
	j = (array.length+1)/2;
	while(i >= 0 && j < array.length) {
		temp = array[i];
		array[i] = array[j];
		array[j] = temp;
		i--; j++;
	}
}

　外側から処理する方とは打って変わった複雑っぷり。まあ、無きに等しい期待を胸に実行させてみると・・・52.613秒。

　速くなっている！？
　計測ミスかとも思い、繰り返し計測してみたがやはり速くなっているようだ。なぜかはよく分からない。もしかしてjavaが特殊なんじゃないだろうか？と根拠がなにもないことを思い、今度はＣ言語で同じアルゴリズムを実装し、配列の長さなどの条件を一緒にしたあと、時間を計測してみた。結果をまとめたものが以下の表となる。

	javaでの実行時間(s)	Cでの実行時間(s)
お手玉の方法	77.869	27.890
逆転法（外側から）	79.315	22.077
逆転法（内側から）	52.613	21.171

　なんとＣ言語で実装した方はちゃんと「逆転法」の方が「お手玉の方法」よりも速くなっている。うーん、何故だ。原因がさっぱり分からない。これはＣ言語の結果の方を信用すればいいのだろうか？

　謎のまま終わるのはすっきりしないが、今までの計測はすべて自分のノートパソコンでやっていたので、パソコンを変えて計測すれば何か分かるかもしれない。

　今日はここまで。