perl(v5.7.3以降) の標準モジュールに Memoize というのがある。何をするやつかというと、perldoc 曰く

Make functions faster by trading space for time

「(計算)時間と(メモリ等の)領域とを取引して、関数を早くします」ということで、メモ化を行ってくれるモジュールです。

百聞は一見に如かず。というわけで、(Benchmark使うんでcodepadは自重

use strict;

use Memoize;
use Benchmark 'timethese';

sub collatz
{
  my $n = shift;
  $n == 1 ? 0 : 1+collatz( $n%2 ? $n*3+1 : $n/2 );
}

sub fibonacci
{
  my $n = shift;
  $n <= 2 ? 1 : fibonacci($n-2)+fibonacci($n-1);
}

timethese( 100, {
    'no_memo_collatz'   => sub {collatz($_) for 1 .. 1000},
    'no_memo_fibonacci' => sub {fibonacci($_) for 1 .. 24},
  });

memoize('collatz');
memoize('fibonacci');

timethese( 1000, {
    'memo_collatz'   => sub {collatz($_) for 1 .. 1000},
    'memo_fibonacci' => sub {fibonacci($_) for 1 .. 24},
  });

私が試したときの結果は以下の通り。

Benchmark: timing 100 iterations of no_memo_collatz, no_memo_fibonacci...
no_memo_collatz: 13 wallclock secs (11.31 usr + 0.00 sys = 11.31 CPU) @ 8.84/s
(n=100)
no_memo_fibonacci: 38 wallclock secs (33.14 usr + 0.00 sys = 33.14 CPU) @ 3.02
/s (n=100)
Benchmark: timing 1000 iterations of memo_collatz, memo_fibonacci...
memo_collatz: 10 wallclock secs ( 9.75 usr + 0.00 sys = 9.75 CPU) @ 102.56/s (
n=1000)
memo_fibonacci: 0 wallclock secs ( 0.22 usr + 0.00 sys = 0.22 CPU) @ 4566.21/
s (n=1000)
(warning: too few iterations for a reliable count)

繰り返し数が10倍になったにもかかわらず、collatzは3秒減、fibonacci に至ってはほぼ0秒で処理が終了している。メモ化素晴らしい。

が、メモ化を施す関数には副作用があってはならない点に注意。Memoizeはあくまで引数と結果のペアを格納するだけなので、例えば以下のようなコードは期待通りに動かない。(http://codepad.org/E9xX2K6K) (もちろんfooの呼出し毎に$i が変更されることを期待してるとして、だが)

use strict;

use Memoize;

my $i = 0;
sub foo
{
  ++$i;
}

print foo(), "\n" for 1 .. 10;
print "i = $i\n";

$i = 0;
memoize('foo');
print foo(), "\n" for 1 .. 10;
print "i = $i\n";

トラックバック(0)

トラックバックURL: http://floralcompany.jp/mt/mt-tb.cgi/150

コメントする

AUTHOR

  • turugina (虎王 剱奈)
  • E-mail: turugina {at} floralcompany.jp
  • pixiv
  • ニジエ

2014年5月

        1 2 3
4 5 6 7 8 9 10
11 12 13 14 15 16 17
18 19 20 21 22 23 24
25 26 27 28 29 30 31

アーカイブ

OpenID対応しています OpenIDについて
Powered by Movable Type 5.2.10

- 警 告 -

本サイトにはいわゆる「18禁画像」(イラスト)へのリンクが存在します。 未成年の方や、その手の画像に不快感を覚える方は、 該当記事(「えちぃの」及び「ちょっとえちぃの」カテゴリ) をご覧にならないようお願いいたします。

上記を理解した上で非表示のブログパーツを表示する
あわせて読みたいブログパーツ
ついった
drawr/pixiv/twitpic