EqualityComparer

昨日のエントリーは玉砕してしまって考察が不足したまま終わったので、考察を追加します。朝起きたらいろんな疑問が湧いてきたわけです。
その前にちょっと反省。昨日のコードは Test クラスのメソッド名がどれもよくないですね。今読んでみると何が何だかわからないので、メソッド名を変更しました。

疑問。
A. List のデフォルトの Enumerator (長いので以下、列挙子)と Forward 列挙子の２倍以上のパフォーマンスの差は何が原因か？

B. 番兵列挙子(Sentinel Enumerator)と検索列挙子(Find Enumerator)が極端に遅いのはなぜか？ TestFor() と SentinelListYield.Find()、また、TestSentinel() と SentinelListYield.FindWithSentinel() はほとんど同じなのに大きな実行速度の差があるのはなぜか？

A についてはデフォルト列挙子は List クラス内にある nested class なので、List の private フィールドの情報を使って早くできるのかもしれない。推測でしかないので、よくわからないまま保留。

B は番兵列挙子でいうと「while ( !this[ i ].Equals( target ) )」の比較処理でボックス化が起きてそうなことに気づきました。
「while ( this[ i ] != target )」 と書ければいいんだけど、これはコンパイルエラー。List では T型に制約はありません。非バインド型パラメータってやつです。MSDNによると「!= 演算子と == 演算子は、具象型引数がこれらの演算子をサポートするという保証がないため、使用できません。」だそうです。でも、IndexOf() などがあるので比較演算は使っているはずです。
調べてみると EqualityComparer を発見。ジェネリックなコレクションクラスで要素を比較するにはこれを使えばいいようです。IEqualityComparer が実装された型なら、EqualityComparer.Default でその比較処理が返ってきます。
さっそく番兵列挙子と検索列挙子を書き換え。

public IEnumerable<T> Find( T target )
{
	for ( int i = 0; i < this.Count; i++ )
	{
		//if ( this[ i ].Equals( target ) )
		if ( EqualityComparer<T>.Default.Equals( this[ i ], target ) )
		{
			yield return this[ i ];
		}
	}
}

public IEnumerable<T> FindWithSentinel( T target )
{
	int i = 0;
	do
	{
		this.Add( target );

		//while ( !this[ i ].Equals( target ) )
		while ( !EqualityComparer<T>.Default.Equals( this[ i ], target ) )
		{
			i++;
		}

		this.RemoveAt( this.Count - 1 );

		if ( i < this.Count )
			yield return this[ i++ ];
		else
			yield break;
	}
	while ( i < this.Count );
}

実行時間はこうなりました。(TestFindAllPredicateは除外)

Result: 2059, Time:  125, Name: TestSentinel
Result: 2059, Time:  141, Name: TestFor
Result: 2059, Time:  343, Name: TestDefaultEnumerator
Result: 2059, Time:  390, Name: TestSentinelEnumerator
Result: 2059, Time:  453, Name: TestFindEnumerator
Result: 2059, Time:  829, Name: TestForwardEnumerator

番兵列挙子を使った TestSentinelEnumerator と、検索列挙子を使った TestFindEnumerator がぐんと早くなりました。これでボックス化は回避されたようです。でもデフォルト列挙子で普通に比較したよりはやっぱり遅いままです。何度か実行してみましたが一度も順位は逆転しませんでした。
番兵列挙子は yield を使わずに書いて、番兵の追加と削除を列挙子のコンストラクタと Dispose に持ってくれば多少伸びるかもしれません。でも foreach 以外からの呼び出しなんていうレアケースで嫌な感じになります。番兵はマルチスレッドにも対応できてませんね。もっと言えば、単純な検索にはうまい手ですが複雑な条件での検索に使うのは簡単じゃなかったりもします。

ところで保留にした Forward 列挙子の遅さが際立っています。これはなんでなんだろう。さっぱりわかりません。また気が向いたら調べてみます。

昨日、今日とこれらのコードはジェネリック、列挙、yield といろいろ勉強になりました。これまでなにげなく書いてた foreach ( int x in list ) の list の部分には何なら来てもいいの？とか、デバッガでステップ実行すると in でいったん止まるわけですが、何で in で止まるの？とか見過ごしてた部分が勉強になりました。
ジェネリックでは「==」「!=」が使えないってのも衝撃でした(もしかして制約によっては使えるかも？)。

勉強になったのはよかったけど、番兵列挙子や検索列挙子はどういうときに便利か？っていう部分はまるで思いつきませんｗ