Este é um post de José Lopes.

No caso de se fazerem muitos cálculos com uma determinada função, pode ser interessante que esta se lembre de resultados anteriores para os dar imediatamente quando solicitados, poupando um considerável tempo de computação.

Este post fornece uma solução de memorização. De frisar que não tem a ver com memória no sentido de hardware mas sim na capacidade de lembrar resultados anteriores.

Antes do mais vamos criar uma função para simular os nossos cálculos.
Por uma questão académica vamos considerar os números de Fibonacci, que não são mais do que uma sucessão iniciada por 0 e 1, com número seguinte dado pela soma dos dois anteriores.
A escolha desta sucessão não tem qualquer razão em especial, vai servir somente para ilustrar a potencialidade do método apresentado neste post.

Escrevemos então a função:

def fibonacci(n):
  if n < 2:
    return n
  else:
    return fibonacci(n-1) + fibonacci(n-2)

Agora, vamos escrever o memorizador que vai ser definido por uma classe para o tornar genérico.

class memo:

  def __init__ (self, f):
    self.result = {}
    self.f = f

  def __call__ (self, *args):
    if not self.result.has_key(args):
      self.result[args] = self.f(*args)
    return self.result[args]

Como se pode verificar pelo código, esta classe vai guardar o resultado num dicionário.
Quando se faz um cálculo é verificado em primeiro lugar se o dicionário já tem o resultado, caso exista devolve o valor levando virtualmente zero segundos, caso contrário calcula o valor, devolve-o e regista-o no dicionário.

Para vermos isto tudo em acção vamos fazer uso de um temporizador como o descrito no post Determinar o tempo de execução de uma função, surgindo a função timer.

test = memo(fibonacci)
timer (test, 50)
timer (test, 50)

O primeiro timer vai calcular o número de Fibonacci enquanto o segundo devolve-o rapidamente por este já estar calculado.
Se quisermos calcular para n=30, na sequência deste exemplo, o valor ainda não existe pelo que será calculado.

No entanto podemos fazer uma magia com:

fibonacci = memo(fibonacci)
timer (fibonacci, 50)
timer (fibonacci, 50)

Neste caso o primeiro timer vai ser muito mais rápido que no caso anterior, sendo o segundo timer ainda mais rápido.

A explicação para isto é que a função fibonacci deixa de funcionar como uma função recursiva normal, funcionando no mesmo princípio mas utilizando o cash da classe memo pois para devolver o valor n vai guardar uma só vez os outros valores que o antecedem.
Deixamos de ter um algoritmo exponencial para ter um de ordem n.
No caso do segundo timer o valor já existe pelo que o devolve num tempo inferior. Se pedirmos o n=49 ele também existe.

De notar que esta magia só funciona com funções recursivas, daí a minha maldade em escolher os números de Fibonacci.