まわしまわされ

C#3.0 数学 Haskell

今週も（今日も）やってまいりました現実逃避のお時間です。
Haskellの本を読んでいたら遅延評価と竹内（様）関数のことが書かれていた。
なるほどー。
とか言いながら読んだのは結構前なのですが、今日ようやく手を動かしてみました。
先日知った不動点演算子を使って（！）試してみました。

Prelude Control.Monad.Fix>
fix(\f x y z -> if x<=y then y else f (f (x-1) y z) (f (y-1) z x) (f (z-1) x y)) 192 96 0

ただ時間の計り方が分からなかったので体内時計で精密に計ってみました。
測定結果は、「とにかくはやい」となりました。おめでとうございます。
ちゃんと関数定義してコンパイルしたらもっと速いんだろうな。
追記(08/07/26)：timeが欲しいがためにcygwin入れた。笑


でも実はHaskellより先にC#でコードを書きました。
本日の現実逃避コードを掲載します。

// namespace以前
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

using LazyInt = System.Func<int>; // これちょっと重要
//
//（中略）
//
public void Test1()
{
	var watch = new System.Diagnostics.Stopwatch();
	int x = 15, y = 10, z = 0;
	Action stop = () => {
		watch.Stop();
		Console.WriteLine( "\a{0}", watch.Elapsed );
		watch.Reset();
	};

	watch.Start();
	this.Tarai1( x, y, z );
	stop();

	watch.Start();
	this.Tarai2( ()=>x, ()=>y, ()=>z );
	stop();
}

// 普通のたらいまわし関数
public int Tarai1( int x, int y, int z )
{
	if ( x <= y ) return y;
	return this.Tarai1(
		this.Tarai1( x-1, y, z ),
		this.Tarai1( y-1, z, x ),
		this.Tarai1( z-1, x, y ) );
}
// クロージャで遅延評価もどきを施したたらいまわし関数
public int Tarai2( LazyInt x, LazyInt y, LazyInt z )
{
	var xv = x(); var yv = y();
	if ( xv <= yv ) return yv;
	return this.Tarai2(
		() => this.Tarai2( (() => xv-1), y, z ),
		() => this.Tarai2( (() => yv-1), z, x ),
		() => this.Tarai2( (() => z()-1), x, y ) );
}

このPCでの結果：
20, 10, 5 の時の結果（2回ずつ）



00:00:38.3894013

00:00:00.0013644
00:00:39.1424989

00:00:00.0026614
15, 10, 0 の時の結果（2回ずつ）


00:01:26.4451298

00:00:00.0014618
00:01:26.0065666

00:00:00.0017924


ラムダ式のオーバーヘッドとかクロージャ生成のコストがあるだろうから非正格純粋関数型言語には到底及ばないでしょうけども、想像以上に大差がついてちょっとビックリしました。中学生の頃地味な感じだった子が、おもいっきり高校デビューしていた時と同じくらいの驚きです。
C#の場合ってコンパイラによってかなりコード置き換えられるから、思ったよりオーバーヘッドとか小さいのかなぁ。


関係ないですが、プログラム中の出力部分に「\a」が含まれているのは仕様です。
ずっと待ってるの面倒だったのでビープ音を鳴らすようにしました。笑
待っている間はCPUに負荷を掛けないように繊細かつ丁寧にネットサーフィンしてた。


あと、C#で遅延評価というとyieldが思い浮かびますが、
すでにsiokoshouさんがやっておられました。
http://d.hatena.ne.jp/siokoshou/20061129#p1
あとでじっくり読ませていただこう。


たらいまわしリンク集：
竹内関数 - Wikipedia
Scheme:たらいまわしべんち
404 Blog Not Found:たらいを回すならHaskell
Concurrent Clean : たらいまわし関数 - lethevert is a programmer
uskzさんによるC++版