Sig: Compartición, Persistencia y Privacidad: Sup: Clausuras Ant: Currying Err: Si hallas una errata ...

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. En ocasiones, es posible acelerar la ejecución de una función pura utilizando una estrategia denominada memoizing. La estrategia consiste en hacer una cache, habitualmente un hash, en el que las claves son los argumentos y los valores los resultados. El siguiente ejemplo memoiza la función que computa los números de Fibonacci:

$ cat -n ./memoize.pl
     1  #!/usr/bin/perl -w
     2  use Benchmark;
     3
     4  sub fib {
     5    my $n = shift;
     6    if ($n < 2) { $n }
     7    else { fib($n-1)+fib($n-2) }
     8  }
     9
    10  {
    11
    12  my @fib = (0, 1);
    13
    14    sub fibm {
    15      my $n = shift;
    16
    17      return $fib[$n] if defined $fib[$n];
    18      $fib[$n] = fibm($n-1)+fibm($n-2);
    19    }
    20  }
    21
    22  timethese(2, {
    23    recursivo => sub { &fib(30) },
    24    memoized  => sub { &fibm(30) }
    25    }
    26  );

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:

$ time ./memoize.pl
Benchmark: timing 2 iterations of memoized, recursivo...
  memoized:  0 wallclock secs ( 0.00 usr +  0.00 sys =  0.00 CPU)
            (warning: too few iterations for a reliable count)
 recursivo:  5 wallclock secs ( 5.81 usr +  0.00 sys =  5.81 CPU) @  0.34/s (n=2)
            (warning: too few iterations for a reliable count)

real    0m5.894s
user    0m5.880s
sys     0m0.010s

Ejercicio 5.16.3  

• Memoize la función que computa el factorial de un número y llame a la función 30 veces para calcular el factorial de los 30 primeros números. ¿Por qué no se obtiene ninguna ventaja al memoizar la función factorial si sólo se llama una vez para un número dado $N$?

Sig: Compartición, Persistencia y Privacidad: Sup: Clausuras Ant: Currying Err: Si hallas una errata ...