Memoizing

Una función se dice pura si no tiene efectos laterales. Dicho de otro modo: el valor retornado sólo depende de sus argumentos de entrada. Si una función pura es llamada muchas veces con los mismos argumentos es posible acelerar la ejecución de la misma utilizando una estrategia denominada memoizing: Se usa una cache para guardar la correspondencia entre los argumentos y los resultados. Habitualmente esta cache es un hash, en el que las claves son los argumentos y los valores los resultados. La variable usada como cache se sitúa en clausura con la subrutina. Para saber mas sobre memoizing consulte el libro de Mark Jason Dominus Higher Order Perl [13]. El módulo Memoize , escrito por Dominus, proporciona memoización automática de una función.

El siguiente ejemplo memoiza la función que computa los números de Fibonacci:

lhp@nereida:~/Lperl/src$ cat -n memoize2.pl
 1  #!/usr/bin/perl -w
 2  use Benchmark;
 3  use Memoize;
 4
 5  sub fib {
 6    my $n = shift;
 7    if ($n < 2) { $n }
 8    else { fib($n-1)+fib($n-2) }
 9  }
10
11  {
12
13  my @fib = (0, 1);
14
15    sub fibm {
16      my $n = shift;
17
18      return $fib[$n] if defined $fib[$n];
19      $fib[$n] = fibm($n-1)+fibm($n-2);
20    }
21  }
22
23  sub fibM {
24    my $n = shift;
25    if ($n < 2) { $n }
26    else { fib($n-1)+fib($n-2) }
27  }
28
29  memoize 'fibM';
30
31  my ($r, $m, $a);
32  timethese(2, {
33    recursivo => sub { $r = &fib(30) },
34    memoized  => sub { $m = &fibm(30) },
35    automemoized  => sub { $a = &fibM(30) }
36    }
37  );
38
39  print "recursivo = $r, memoized = $m, automemoized = $a\n";

Este es un ejemplo en el cuál es conveniente ocultar la cache e impedir posibles colisiones de la variable @fib con cualesquiera otras variables que pudieran existir en el programa. La solución es hacer una clausura (lıneas 10-20).

La ejecución muestra como la técnica mejora claramente el rendimiento:

lhp@nereida:~/Lperl/src$ memoize2.pl
Benchmark: timing 2 iterations of automemoized, memoized, recursivo...
automemoized:  3 wallclock secs ( 2.98 usr +  0.00 sys =  2.98 CPU) @  0.67/s (n=2)
            (warning: too few iterations for a reliable count)
  memoized:  0 wallclock secs ( 0.00 usr +  0.00 sys =  0.00 CPU)
            (warning: too few iterations for a reliable count)
 recursivo:  6 wallclock secs ( 5.97 usr +  0.00 sys =  5.97 CPU) @  0.34/s (n=2)
            (warning: too few iterations for a reliable count)
recursivo = 832040, memoized = 832040, automemoized = 832040