C#でたらいまわし
yieldで遅延評価めいたことができたので、こうなってくるとたらいまわしたいよね？と思って考えてました。
悩みに悩んだ挙句、ついにできた！
//#define COUNTusing System;
using System.Collections.Generic;
using System.Diagnostics;namespace Taraimawashi
{
class Program
{
static void Main()
{
int x = 20, y = 10, z = 5;
//int x = 192, y = 96, z = 5;
//int x = 452, y = 195, z = 15;System.Diagnostics.Stopwatch sw = new Stopwatch();
sw.Reset();
sw.Start();
int resultYa = Eval( YieldTarai( x, y, new int[] { z } ) );
sw.Stop();
Console.WriteLine( "Lazy: " + resultYa );
PrintCounter( yieldTaraiCount );
Console.WriteLine( sw.Elapsed );
Console.WriteLine();sw.Reset();
sw.Start();
int resultYb = Eval( YieldTarai( x, y, new int[] { z } ) );
sw.Stop();
Console.WriteLine( "Lazy: " + resultYb );
Console.WriteLine( sw.Elapsed );
Console.WriteLine();
sw.Reset();
sw.Start();
int resultNa = Tarai( x, y, z );
sw.Stop();
Console.WriteLine( "Normal: " + resultNa );
PrintCounter( taraiCount );
Console.WriteLine( sw.Elapsed );
Console.WriteLine();sw.Reset();
sw.Start();
int resultNb = Tarai( x, y, z );
sw.Stop();
Console.WriteLine( "Normal: " + resultNb );
Console.WriteLine( sw.Elapsed );
Console.WriteLine();Console.Read();
}static int Tarai( int x, int y, int z )
{
CountUp( ref taraiCount );if ( x <= y ) return y;
return Tarai( Tarai( x - 1, y, z ),
Tarai( y - 1, z, x ),
Tarai( z - 1, x, y ) );
}static IEnumerable<int> YieldTarai( int x, int y, IEnumerable<int> ez )
{
CountUp( ref yieldTaraiCount );if ( x <= y ) yield return y;
int z = Eval( ez );
yield return Eval( YieldTarai( Eval( YieldTarai( x - 1, y, ez ) ),
Eval( YieldTarai( y - 1, z, new int[] { x } ) ),
YieldTarai( z - 1, x, new int[] { y } ) ) );
}static int Eval( IEnumerable<int> enumerable )
{
IEnumerator<int> it = enumerable.GetEnumerator();
if ( it.MoveNext() )
return it.Current;
else
throw new ArgumentException( "ゴラァ" );
}static Int64 taraiCount = 0;
static int yieldTaraiCount = 0;[Conditional( "COUNT" )]
static void CountUp( ref int counter )
{
counter++;
}[Conditional( "COUNT" )]
static void CountUp( ref Int64 counter )
{
counter++;
}[Conditional( "COUNT" )]
static void PrintCounter( object counter )
{
Console.WriteLine( "Count: " + counter.ToString() );
}
}
}
Taraiがフツーのたらいまわしで、YieldTaraiが遅延評価版。
yield returnでIEnumerableを返して、受け手で必要なときにEvalで取り出してます。IEnumerableなくせに値は一つしか返しません。姑息です。裏技っぽいです。
ちなみにたらいまわし関数って性能評価以上の意味は特にありません。何しているんだろうって真剣に悩まないでねｗ
気になる性能は…*1
Lazy: 20 00:00:00.0025689 Lazy: 20 00:00:00.0001233 Normal: 20 00:00:25.2980460 Normal: 20 00:00:25.2766800
すげぇぇぇぇぇ！桁が違いすぎ！
2回目どうしで比較すると、20万倍の高速化!?
たらいまわし関数が評価された回数は、Lazyが151回、フツーのが2,927,486,081回(^^; Int32じゃ足りなかった(^^;;;
先頭の#define COUNTを有効にするとカウントしてくれます。
この技が有効に使える場面があるかどうか、ちょっとわかりませんが、おもしろいですねぇ。
＃なんか、Don Boxが食いつきそうなネタだ。
*1:計測環境は Windows XP Pro SP2、RAM 1G、CPU Pen4 3.2GHz
