Memoize | 関数結果のキャッシュ



```
$ corelist Memoize

Data for 2014-10-01
Memoize was first released with perl v5.7.3
```

関数のメモ化って、だいたい再帰とセットになって説明されてるんだけど、
普通の関数でのメモ化の説明が見あたらない。

重い処理と言うことで、コマンドの `find` を実行させる例を[^1]。

[^1]: 軽い処理を与えたら返って遅くなってしまうのは試すまでもない。負荷をかけるのだけが目的なので、 `0` が見つかろうと見つからまいと、どうでもいい.

```
sub code { qx{find . -name 0} ; }
```

この `code ` が所謂「重いサブルーチン」。

これをメモ化。

## Memoize

### 単純なケース
```
use Memoize ;
memoize( 'code') ;
sub code { qx{find . -name 0} ; }
```

これだけ。
書き手が意識せずに、キャッシュされるので、同じ解析を二度行なわない。で、速度が早くなる。
もちろん、 `code` の中で、更にグローバル変数への変更を行なっている場合などは、`memoize` してはいけないだろう。

どれだけ高速化したかはベンチマークを取ってみる。


上のコードに続けて以下を記載。


```
sub code2 { qx{find . -name 0} ; }
use Benchmark qw(:all) ;
cmpthese(timethese (undef, {
    'find'  => 'code',
    'find2' => 'code2',
}));
```

メモ化しない用のサブルーチンを用意するのだけれど、`code `と `code2` って中身は全く同じ。
同じものを2回書くのはダサいので以下の様に変更。

#### code
```pl:test.pl
use Benchmark qw(:all) ;
use Memoize ;
memoize( 'code', INSTALL => 'memo') ;
sub code { qx{find . -name 0} ; }

cmpthese(timethese (undef, {
    'non_memo'  => 'code',
    'memoize'   => 'memo',
}));
```

`INSTALL` は、Memoize したサブルーチンに別名を与える為のオプション[^2]。
[^2]: ベンチ以外の時の必要性が感じられない、、、

`Benchmark` は定番のベンチマークモジュール

```
$ corelist Benchmark

Data for 2014-10-01
Benchmark was first released with perl 5
```


#### 実行結果
```
Benchmark: running memoize, non_memo for at least 3 CPU seconds...
   memoize:  3 wallclock secs ( 3.06 usr +  0.00 sys =  3.06 CPU) @ 553411.76/s (n=1693440)
  non_memo: 27 wallclock secs ( 0.47 usr  2.86 sys +  8.07 cusr 16.57 csys = 27.97 CPU) @ 354.74/s (n=9922)
             Rate non_memo  memoize
non_memo    355/s       --    -100%
memoize  553412/s  155906%       --
```
当たり前だけど、メモ化した方が速い。



### キャッシュの永続化
キャッシュをファイルに落し込む事も出来る[^3]。

[^3]: `Storable` とか、`GDBM_File` とか、`SDBM_File` とか。
ここでは、 `Storable` での例を。




#### code の変更
```
use Benchmark qw(:all) ;
use Memoize ;
use Memoize::Storable ;

tie ( my %cache, 'Memoize::Storable', 'test.db', 'nstore');
memoize 'code',  INSTALL => 'memo', SCALAR_CACHE => [HASH => \%cache],;
sub code { qx{find . -name 0} ; }

cmpthese(timethese (undef, {
    'non_memo'  => 'code',
    'memoize'   => 'memo',
}));
```

1. `use Memoize::Storable` 宣言して
2. `tie ~` 行で、 `test.db` ってファイルに `nstore` で `tie` して、
3. `memoize` 行で、`SCALAR_CACHE => [HASH => \%cache],` にてキャッシュの形式を指定

しています。


#### 実行結果
```
Benchmark: running memoize, non_memo for at least 3 CPU seconds...
   memoize:  3 wallclock secs ( 3.05 usr +  0.00 sys =  3.05 CPU) @ 230743.28/s (n=703767)
  non_memo: 32 wallclock secs ( 0.53 usr  2.58 sys +  9.33 cusr 19.09 csys = 31.53 CPU) @ 366.70/s (n=11562)
             Rate non_memo  memoize
non_memo    367/s       --    -100%
memoize  230743/s   62825%       --
```

やはり、外部ファイルへの保存があると言う事で、素での `memoize` よりは遅くなる。


### NORMALIZER

引数1 とかの場合は単純だったのだが、デフォルトの値を与えたり、引数の順番が順不動だったりと言うケースで、別だと判断されてしまうのを避けたい事もある。
その時は、`NORMLIZER` オプションで、正規化サブルーチンを指定してやる。
例えば、 `code` が引数を二つ引き受ける以下の様なコードだった場合[^4]

[^4]: あくまでも例。実際には、こんなコトしない。

```
sub code { 
    qx{find . -name $_[0]} ;
    qx{find . -name $_[1]} ;
}
```
以下の様な感じに正規化のサブルーチンを作る。

```
sub normalize_code {  join ",", sort @_  }
```

で、

```
memoize 'base', INSTALL => 'memo', NORMALIZER => 'normalize_code';
```

これで引数を、 A, B と与えた時も、B, A と与えた時も同じキャッシュを見に行く。

### ここまで書いといて

なんだけど、`Memoize.pm` だけでも 300行を越える `Pure Perl` のコードで構成されている。

```
$ perldoc -m Memoize | perltidy -dac | wc -l 
314
```
- [`perltidy`](http://search.cpan.org/~shancock/Perl-Tidy-20150815/bin/perltidy) は定番コード整形ツール。 `-dac` で `pod` を含むコメントを除外。

っつーことは、普通に考えて自分でキャッシュさせた方が、どんなもんでも速い。

```
use Benchmark qw(:all) ;
use Memoize ;
use feature qw(state) ;
memoize( 'code', INSTALL => 'memo') ;
sub code { qx{find . -name 0} ; }
sub code2 { 
    state $c ;
    $_[0] = 0 ; 
    return $c->{$_[0]} if defined $c->{$_[0]} ;
    return $c->{$_[0]} = qx{find . -name $_[0]} ;
}

cmpthese(timethese (undef, {
    'non_memo'  => 'code',
    'memoize'   => 'memo',
    'cache'     => 'code2',
}));
```


結果

```
Benchmark: running cache, memoize, non_memo for at least 3 CPU seconds...
     cache:  4 wallclock secs ( 3.04 usr +  0.00 sys =  3.04 CPU) @ 1914506.58/s (n=5820100)
   memoize:  3 wallclock secs ( 3.15 usr +  0.00 sys =  3.15 CPU) @ 554938.41/s (n=1748056)
  non_memo: 35 wallclock secs ( 0.58 usr  2.44 sys + 10.46 cusr 21.43 csys = 34.91 CPU) @ 375.57/s (n=13111)
              Rate non_memo  memoize    cache
non_memo     376/s       --    -100%    -100%
memoize   554938/s  147661%       --     -71%
cache    1914507/s  509666%     245%       --
```

### 結論
散らばりがちなキャッシュ用ハッシュとかも、今となっては、 `state` でサブルーチンの中に埋め込んでしまえばいいし、キャッシュを見るコードと、return 時にキャッシュするコード追加するだけだし、、、余っ程コードを簡潔にしたいか、キャッシュを外部に簡便に保存したい時以外では、使わなくていいんじゃね？