番兵つき Find Enumerator

C# .NET

今日は長文。
MSDN の Articles and Columns に載っている Tips and Tricks がおもしろかったので、いろんな列挙を書いて遊んでみました。
STL でいうところのアルゴリズムとイテレータが混ざったものに当たるので、コンテナ、アルゴリズム、イテレータを分離して直交性を高くするっていう考えに逆行するけど、まぁやってみました。

お題は List に対する FindAll。List にランダムな数字を詰め込んで、ある数字がいくつあるか数え上げるサンプルです。

まずは Enumerator を３種類用意してみました。
Forward Enumerator は普通に前から順に列挙する列挙子。
Find Enumerator は一致する数字だけを列挙します。
FindWithSentinel Enumerator は番兵(Sentinel)付き Find Enumerator。元の List をいじるような Enumerator はどうなのよって気もするけど、ものは試しで。ところで、番兵は番兵パターン(Sentinel Design Pattern)と呼んだらいいのに。

using System;
using System.Collections;
using System.Collections.Generic;

namespace Banpei
{
	public class SentinelListYield<T> : List<T>
	{
		public IEnumerable<T> Forward
		{
			get
			{
				for ( int i = 0; i < this.Count; i++ )
				{
					yield return this[ i ];
				}
			}
		}

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

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

				while ( !this[ i ].Equals( target ) )
				{
					i++;
				}

				this.RemoveAt( this.Count - 1 );

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

FindWithSentinel は、毎回毎回 this.Add( target ) で番兵を追加し、ヒットのたびに(つまり値を返すたびに) this.RemoveAt( this.Count - 1 ) で番兵を削除しています。利用側が foreach で必ず最後まで回すとは限らないので、こうするしかなさそうです。なんだかいまいちです…。

yield がどう展開されるかってのは、これをコンパイルして Reflector で見ると分かります。ドキュメントなら C# Language Specification 2.0, March 2005 Draft の「22. Iterators」にサンプルが３つ載っています。

１つ展開してみると、大筋はこんな感じ。細かいところは簡単にしてあります。yield がないとこれだけ書かないといけないかと思うと、実にありがたい構文です。宣言型のプログラムって感じ。

public IEnumerable<T> Find( T target )
{
	return new FindEnumerator<T>( this, target );
}

private class FindEnumerator<U> : IEnumerator<U>, IEnumerator, IEnumerable<U>, IEnumerable, IDisposable
{
	private SentinelList<U> list;
	private int index;
	private U target;

	public FindEnumerator( SentinelList<U> list, U target )
	{
		this.list = list;
		this.index = -1;
		this.target = target;
	}

	public IEnumerator<U> GetEnumerator()
	{
		return this;
	}

	System.Collections.IEnumerator System.Collections.IEnumerable.GetEnumerator()
	{
		return GetEnumerator();
	}

	public U Current { get { return list[ index ]; } }
	object System.Collections.IEnumerator.Current { get { return list[ index ]; } }

	public void Dispose() { }

	public bool MoveNext()
	{
		for ( index++; index < list.Count; index++ )
		{
			if ( list[ index ].Equals( target ) )
			{
				return true;
			}
		}
		return false;
	}

	public void Reset()
	{
		throw new NotSupportedException();
	}
}

誰も使わない(^^;) Reset はサポートしないようです。

テストはこんな感じ。

using System;
using System.Collections.Generic;

namespace Banpei
{
	public class Test
	{
		private SentinelListYield<int> list;
		protected int target;
		protected string name;

		protected delegate int FindDelegate();

		public Test( SentinelListYield<int> list, int target )
		{
			this.list = list;
			this.target = target;
			this.name = "Test yield: ";
		}

		public void Do()
		{
			Console.WriteLine( "" );
			Console.WriteLine( name );

			FindDelegate[] del = new FindDelegate[] {
				TestFor, TestSentinel,
				TestDefaultEnumerator, TestForwardEnumerator, TestFindEnumerator, TestSentinelEnumerator,
				TestFindAllPredicate };
			for ( int i = 0; i < del.Length; i++ )
				DoMethod( del[ i ] );
		}

		private void DoMethod( FindDelegate del )
		{
			int t0 = Environment.TickCount;
			int ret = del();
			ret = del();
			ret = del();
			ret = del();
			ret = del();
			int t1 = Environment.TickCount;
			Console.WriteLine( "Result: {0}, Time: {1,4:D}, Name: {2}", ret, t1 - t0, del.Method.Name );
		}

		private int TestFor()
		{
			int count = 0;
			for ( int i = 0; i < list.Count; i++ )
			{
				if ( list[ i ] == target )
				{
					count++;
				}
			}
			return count;
		}

		private int TestSentinel()
		{
			int count = 0;

			int i = 0;
			list.Add( target );
			do
			{
				while ( list[ i ] != target )
				{
					i++;
				}

				count++;
				i++;
			}
			while ( i < list.Count );
			list.RemoveAt( list.Count - 1 );
			count--;

			return count;
		}

		private int TestDefaultEnumerator()
		{
			int count = 0;
			foreach ( int x in list )
			{
				if ( x == target )
				{
					count++;
				}
			}
			return count;
		}

		private int TestForwardEnumerator()
		{
			int count = 0;
			foreach ( int x in list.Forward )
			{
				if ( x == target )
				{
					count++;
				}
			}
			return count;
		}

		private int TestFindEnumerator()
		{
			int count = 0;
			foreach ( int x in list.Find( target ) )
			{
				count++;
			}
			return count;
		}

		private int TestSentinelEnumerator()
		{
			int count = 0;
			foreach ( int x in list.FindWithSentinel( target ) )
			{
				count++;
			}
			return count;
		}

		private bool FindPredicate( int x )
		{
			if ( x == target )
				return true;
			return false;
		}

		private int TestFindAllPredicate()
		{
			List<int> ret = list.FindAll( FindPredicate );
			return ret.Count;
		}
	}
}
  • TestFor: 素直に for で検索
  • TestSentinel: Enumerator を使わない番兵
  • TestDefaultEnumerator: List のデフォルトの Enumerator で素直に検索
  • TestFindAllPredicate: List の FindAll( Predicate match ) を使って検索

以下の３つが 今回作成したカスタム列挙子を使った検索

  • TestForwardEnumerator: SentinelListYield クラスの Forward Enumerator を使って検索
  • TestFindEnumerator: SentinelListYield クラスの Find Enumerator を使って検索
  • TestSentinelEnumerator: SentinelListYield クラスの FindWithSentinel Enumerator を使って検索

Main はこんな。

using System;
using System.Collections.Generic;

namespace Banpei
{
	public class Program
	{
		public const int Max = 10000000;

		public static void Main()
		{
			Random random = new Random();
			SentinelListYield<int> list = new SentinelListYield<int>();

			for ( int i = 0; i < Max; i++ )
			{
				int n = random.Next( 1000 );
				list.Add( n );
			}
			int target = list[ 2 ];

			Test test = new Test( list, target );

			test.Do();
			test.Do();
			test.Do();
			Console.ReadLine();
		}
	}
}

何も見つからないと寂しいので、List 中の list[ 2 ] の値を探すようにしています。
気になる実行時間を早い順に。WindowsXP Pro SP2、Pentium4 3.20GHz、1GB RAM での実行結果の一例です。

Result: 9963, Time:  125, Name: TestSentinel
Result: 9963, Time:  156, Name: TestFor
Result: 9963, Time:  328, Name: TestDefaultEnumerator
Result: 9963, Time:  344, Name: TestFindAllPredicate
Result: 9963, Time:  828, Name: TestForwardEnumerator
Result: 9963, Time: 1109, Name: TestSentinelEnumerator
Result: 9963, Time: 1188, Name: TestFindEnumerator
  • TestSentinel: Enumerator を使わない番兵
  • TestFor: 素直に for で検索
  • TestDefaultEnumerator: List のデフォルトの Enumerator で素直に検索
  • TestFindAllPredicate: List の FindAll( Predicate match ) を使って検索
  • TestForwardEnumerator: SentinelListYield クラスの Forward Enumerator を使って検索
  • TestSentinelEnumerator: SentinelListYield クラスの FindWithSentinel Enumerator を使って検索
  • TestFindEnumerator: SentinelListYield クラスの Find Enumerator を使って検索

こうなりました。yield を使わずに書いたものも試してみましたが、ほぼ同じような実行時間でした。
Enumerator は素直に書いただけでは、もともと用意されてる Enumerator の速度にまったく歯が立たないってことが分かりました。カリカリチューンされてるんですね。どこをどうチューンしてあるんだろう。

TestDefaultEnumerator と TestFindAllPredicate は何度も実行していると順位がときどき入れ替わります。速度はだいたい同じとみていいかも。TestDefaultEnumerator と TestForwardEnumerator は２倍以上の差があります。TestSentinelEnumerator と TestFindEnumerator は TestSentinel の８倍以上遅い！
番兵は早い。for 文と foreach 文では当然だけど for が早い。といっても一千万件x5回でこの時間なら気にすることでもないですね。

結論。もともと用意されてる Enumerator は早い！ Enumerator スピードチューニング法が知りたくなったところで長文終了。

(追記) テストの名前がややこしかったので、すべて TestHoge() という名前に変更しました。テストの説明も一部修正しました。
http://d.hatena.ne.jp/siokoshou/20060305#p1 に続く。