Table,Caching,Memoize,Closure,Profiler

入力に対して決まった値を返し、入力値のレンジが広く、何度も値を取得する必要がある場合、Cなんかでは初期化時に全入力値に対する結果を保持するテーブルを生成したりします。速度重視する場合のsinテーブルとか。割と制約がシビアでない環境では、新しい入力パラメタが与えられるたびに値を保存する関数でもいいと思います。

my %cache;
sub fast_sin {
    return $cache{ $_[0] } if exists $cache{ $_[0] };
    $cache{ $_[0] } = sin( $_[0] );
}

PerlのMemoizeモジュールや、JSANのMemoizeモジュールを使うとこのキャッシング機能を毎回書く必要がなくなります。Perlの場合は、

use Memoize;
memoize 'sin';

とするだけでsin関数にキャッシュ機構が組込まれます。
Perlでの実装は、

my (%caches, %real); 
sub memoize { 
    my $package = caller; 
    my $func = join ’::’, $package, shift(); 
    $real{$func} = \&$func; 
    $caches{$func} = {}; 
    *$func =  sub { check_cache($func, @_) }; 
}
sub check_cache { 
    my $func = shift; 
    my $cache = $caches{$func}; 
    my $key = join ’,’, @_; 
    return $cache->{$key} if exists $cache->{$key}; 
    return $cache->{$key} = $real{$func}->(@_); 
}

のような感じです。memoizeされた関数名のグロブに無名関数を割り当てている。その無名関数内ではキャッシュを調べる関数をラップしていて、引数をキーに関数に対応するキャッシュ値があるか確認し、存在する場合はキャッシュ値を返し、存在しない場合は指定された関数を実行し、キャッシュに保存したあと、その値を返します。
memoizeされた関数を実際に呼ぶときはmemoize関数内の最後に定義されている無名関数を呼ぶことになります。無名関数内で呼んでいるcheck_cache関数には、memoizeした関数を呼ぶスコープからは通常アクセスできない$funcへの参照があります。無名関数を定義したスコープ内の変数は無名関数内に保持される、クロージャを使うことで、この問題は解決されています。

関数の実行結果をキャッシュする代わりに、関数実行にかかる時間を計測し、その値をキャッシュ値に加算していくことでプロファイラにすることでも出来ます。実行時間の代わりに実行回数でもいいかもしれません。

my (%real, %times);        
sub profile { 
    my $package = caller; 
    my $func = join ’::’, $package, shift(); 
    $real{$func} = \&$func; 
    $times{$func} = 0; 
    *$func =  sub { time_function($func, @_) }; 
} 
sub time_function { 
    my $func = shift; 
    my $start = time; 
    my $result = $real{$func}->(@_); 
    my $elapsed = time - $start; 
    $times{$func} += $elapsed; 
    return $result; 
}

……というようなことがYAPC::NA 2006のMark Jason Dominusさんの資料、Higher-Order Perlに書いてありました。p.20辺りまで。このあとイテレータの話になって、長そうなので気が向いたらまた続きやります。
クロージャが気になった人はHOP買うといいんだと思います。僕も、立ち読み出来そうなところが無かったら諦めて買おうかと思います。

Higher-Order Perl: Transforming Programs with Programs

Higher-Order Perl: Transforming Programs with Programs

以下は、クロージャ関連の参考リンクです。

オブジェクトとは、処理が付加されたデータのことです。クロージャーとは、データが付加された処理のことです。

  • 小さなシステムでは、閉包*1は、ほぼ間違いなくオブジェクトよりも扱いが容易です。オブジェクトのクラスを作成するためのコードの量に比べれば、ローカル環境で匿名関数を作成するために必要なコードは、本当に小さなものです。
  • しかし、ローカル環境に対応して機能する複数の関数（おそらく3つか4つ以上）を定義する必要があるときには、オブジェクトの方が効果的です。

*1:恐らく、クロージャのこと