diff その３ - 当面C#と.NETな記録

前回は http://www.mathertel.de/Diff/ のコードの Hashtable を削除したら２倍速くなったところまで。今日はその続き。
このコードでは文字列を行ごとにばらしてハッシュ値にする前処理があって、その後にハッシュ値配列のdiffを調べる。この前処理とdiff処理の各時間を計ると、２桁差で圧倒的に前処理に時間が掛かってました。
じゃあってことで、ハッシュ化止めて文字列をそのまま比較してみると、前回のHashtableなし版と同程度の速度でした。これって、オリジナルはハッシュ化で余計遅くなってるってことじゃ…。高速化はまず計測ありきですな。
文字列のインターン化も試してみたけど、Hashtableあり版と同程度の時間でした。内部でHashtable使ってるってリッチャーが書いてるけど、それと一致する速度ですね。
しょうがないんで(なにが？ｗ)、どう見ても手抜きな DiffCodes() を直してみました。Splitしてオプションに従って文字列いじってハッシュ値を求めた後は文字列を捨てるんで、どう見ても無駄です。経験的にSplitは遅い気がするし。LLっぽくてかなり重宝してるけど。

private static int[] DiffCodes( string text, Option option )
{
	if ( option.IgnoreCase )
		text = text.ToUpperInvariant();

	List<int> list = new List<int>();
	const int seed = 5381;
	int h = seed;
	for ( int i = 0; i < text.Length; i++ )
	{
		if ( text[ i ] == '\n' )
		{
			list.Add( h );
			h = seed;
			continue;
		}
		h = ( ( h << 5 ) ^ ( h >> 27 ) ) ^ text[ i ];
	}
	if ( ( h != seed ) || ( text[ text.Length - 1 ] == '\n' ) )
		list.Add( h );

	return list.ToArray();
}

まじめに行末を探しながらハッシュ化してみました。\r削除はいらないような気がしたんで削除。ignoreSpace と trimSpace は面倒なので元のコードを使ってください。ところで ignoreSpace は空白文字の連続を空白１文字にしてるけど、ignoreSpace って響きからすると空白全削除がいいような気がするんだけど、どうなんでしょう。

これで、オリジナルに比べて約６倍も速くなった！シャアより速いｗ

O(ND)とかO(NP)とか調べて楽しんでるのに、こんなところで高速化してしまうんじゃつまらないｗってわけで、O(NP)にも取り組んで、subversionの移植を捨ててペーパーのコードを持ってきました。subversionの一致部分の保存/読み取りのとこは参考にしつつ。今度こそO(ND)のコードより速くなりました。http://www.mathertel.de/Diff/ のコードと比べると当社比(?)14倍も高速。そのうち公開します。ペーパーではfpが-1ベースなのに対して0ベースに改善した(つもり)。たいていの言語でさらに速くなるハズ。
ところでsubversionのコードでシーケンスをリング状のリンクリストにしてる理由がよくわかんなかった。番兵を追加するときに、巧みに文字列の入れ替えをしてる(O(NP)では文字列長の制約がある。文字列A,BのうちBが長くないといけない)んだけど、そのためだけのような気がした。CとC#の違いも山程あるけど、もしかしたらsubversionも単純なコードにすればもう少し速くなるのかもしれない。あと、Cでは引数の[IN][OUT]くらいはコメントに書けｗ！

しっかし、アルゴリズムはまだしっかり理解できないな〜。速いアルゴリズムのほうが短くて単純なコードになってるのがおもしろい。以前見たQuickSearchもそうだったけど。比較回数はペーパーでは1/2とあるけど、それどころじゃなく減る場合も普通にあります。なんてかしこいんだろ。