なつたん

例によってHigher-order Perlから

昨日までは、同じ処理を同じアルゴリズムで書いたらC/C++が一番早いに決まっているという信念があったのですが、この本を読んで考えが変わりました。2007年11月3日はそんな記念日。

相変わらずメモ化の話なんですが、

・フィボナッチ書けたよ → 遅くね？
・メモ化したよ → 毎回メモ化の仕組み作るの面倒じゃね？
・closureがあるよ → 引数が一つの時しか使えなくね？
・joinでつなぐよ → f("x,", "y")と、f("x", ",y")でバグるよ
・正規表現でエスケープするよ → 遅くね？
・key generatorを引数で渡して、if文で切り替えたらどうよ → if文無駄じゃね？
・eval使うよ ← 今ここ

という議論を経て、evalを使う話。上の議論は全部Perlのソース付きで説明されています。
で、問題のコードがこれ。

sub memoize {
　my ($func, $keygen) = @_;
　$keygen ||= q{join ',', @_};

　my %cache;
　my $newcode = q{
　　sub { my $key = do { KEYGEN };
　　　　$cache{$key} = $func->(@_) unless exists $cache{$key};
　　　　　return $cache{$key};
　　　　}
　};
　$newcode =~ s/KEYGEN/$keygen/g;
　return eval $newcode;
}
　
引用のレベルだと思うけど、念のため。ソースはここから取得可能、ソースのライセンスはここです。

evalを使う前ののソースが、my $key = $keygen ? $keygen->(_@) : join ',' , @_; と、引数$keygenがあるかないかで、joinを使うか、引数で与えられた$keygen関数を使うかを切り分けていたのが、上のやり方で三項演算子が一つ消えている。つまり、自分で最適化されたソースを作り出し(KEYGEN部分の置換)、evalしてそのまま利用することで条件分岐を減らしているわけだ。これはC言語では難しい。条件分岐をnopでつぶすとか、DLL作り直して再ロードとかできなくはないが、明らかにCの範囲を超えている。これCommon Lispでできたらすごい事になる事に気がついた。

状況としては、良く呼ばれてボトルネックになっている関数があるとする。その関数が、起動時のオプションや実行時の状態によって、ちょっとずつ動きを変える必要があるとする。Cで書くと、どうしても動きを変えるためにif文が必要になる。Common Lispだと動きを変えたS式を作り出し、最適化を書けてコンパイルして使い続けることができる。Lispについてのよくある誤解と、その中にあるちょっとした真実にあるように、もともとCommon Lispのコンパイル能力は高いらしいので、「いろいろ変わる条件」が複雑になればなるほど、Common Lispの方が速い可能性が出てくる。Cでも、考えられる組み合わせにはそれぞれ別の関数を作るってやり方もあるけど「100回以上呼ばれたら、自動的に最適化されたS式を作り出して、再コンパイル」みたいな芸当はCにはできない。

結論：Lispすげー！

メモ化の話としては、内容的にも、ページ数的にも、ここで折り返し
後は、特殊な状況下での考察がソース付きで続く。Higher-Orderはあまり関係ない。

キーワードだけ列挙
・f(A=>32, C=>99)と、A(C=>99, A=>32)を同じに扱うべきかどうか
・デフォルト引数的な動きをする関数をどう扱うか。
・オブジェクトのメソッドをメモ化するときの注意点
・オブジェクト(のアドレス)をキーにしてはいけない理由
・メモ化の結果をDiskに残して、後で再利用する
・時刻を取得する関数をメモ化が有効な時
・sort関数でのメモ化
・Orcish Maneuver
・Semipredicate problem
・"0e0"問題
・100回呼ばれたら自動的にメモ化する

100ページを読んでまだまだ絶賛ベタ褒め中。