北海道苫小牧市出身の初老PGが書くブログ

永遠のプログラマを夢見る、苫小牧市出身のおじさんのちらしの裏

メモ化関数

高階関数はほんと魅力たっぷりです。


On Lisp読んでいて、メモ化関数ってのが出てきました。

sub memoize($){
    my $func = shift;
    my %cache = ();
    return sub {
        my $key = join($;, @_);
        $cache{$key} = $func->(@_)
            unless defined $cache{$key};
        return $cache{$key};
    }
}

ざっくり実装でこんなの*1。これは、自分で作った関数をキャッシュ付きの高速バージョンに変えてくれる関数です。


使い方。例えば、以下のように極端に遅い関数があったとします。

sub my_slow_add {
    my ($n, $m) = @_;
    sleep(5);
    return $n + $m;
};

これを、さきほどのmemoizeでラップします。

 *my_add = memoize(\&my_slow_add);

これだけ。ああ、素敵。試しに、以下のコードを動かしてみましょう。

print my_add(1, 2), "\n";
print my_add(2, 3), "\n";
print my_add(1, 2), "\n";
print my_add(2, my_add(1, 2)), "\n";

最初の2回の呼び出しは5秒かかりますが、後の2回はきちんとキャッシュが効いて一瞬で返ってきます。

*1:実装しなくてもCPANでありそうだなー。探すのめんどいから知ってたら教えて下さい(コラ)