隣接n項間漸化式 - dachs

キャッシュを使ったフィボナッチをもう一段抽象化してみます．初期値は引数にできますし，無名サブルーチンを使えば，漸化式そのものも引数にすることができます．

use strict;
use warnings;
no warnings 'recursion';
use bigint;

{my %cache;
sub receq{
    my ($n, $eqn, $init) = @_;
    return $cache{$n,$eqn}  if defined $cache{$n,$eqn};
    return $init->[$n] if defined $init->[$n];
    for my $i (0..$#{$init}){
	push @arg, receq($n-1-$i,$eqn,$init);
    }
    return $cache{$n,$eqn} = $eqn->(@arg);
}
}

キャッシュはそのまま残して，第一引数には項数，第二引数には「漸化式」，第三引数には「初期値」を与えます．

このとき，フィボナッチの1000項目は

print receq(1000, sub{ $_[0]+$_[1] }, [0,1])

で出力できます．また，昨日の「キャッシュなし呼び出し回数」の $F_n$ の例えば100項は

print receq(100, sub{ $_[0]+$_[1]+1 }, [1,1])

で出力できます．

そして，例えば，隣接四項間漸化式 $a_{n}=a_{n-1}+a_{n-2}+a_{n-3}$ ， $n=3,4,\ldots$ ， $a_0=0$ ， $a_1=1$ ， $a_2=1$ は

print receq(100, sub{ $_[0]+$_[1]+$_[2] }, [0,1,1])

として計算して出力できます．

このコードのメインは二箇所ありおます．一つは最後にキャッシュに値を入れて返すときに漸化式に値をいれて計算させるところ

    return $cache{$n,$eqn} = $eqn->(@arg);

です．引数をあらかじめ計算させた@argにしています．これによって，引数の個数が何個でも対応できるようにしています．直前でpushによって，必要なだけの引数を計算させてしまっているのです．

もう一つ，こっちの方がポイントですが，キャッシュに使っているハッシュ%cacheのキーが重複しないようにしています．一般化したことで，異なる漸化式でも同じサブルーチンで計算させることができるようになってますが，%cacheのキーを単純に項数だけにすると違う漸化式の同じ項数の値が同じになってしまいます．そこでキーとして，項数と漸化式をカンマで連結したものにしています．「漸化式」はサブルーチンへのリファレンスなので値としては意味がありませんが，一意にできるのでキーには適しています．

ただし，同じ漸化式を何度も使う場合には

my $eqn = sub{ $_[0]+$_[1] };
print receq(1000, $eqn, [0,1]);

のように，漸化式をあらかじめ「固定」しないと，キャッシュが無意味になります．無名のサブルーチンを使うと，毎回違うものとなるので毎回計算しなおすことになるからです．