21

Vi hoje numa resposta o seguinte código:

function fibonacci($n) {
    $a = 0;
    $b = 1;
    $c = 1;
    for ($i = 1; $i < $n ; $i++) { 
        $c = $a + $b;
        $a = $b;
        $b = $c;
    }
    return $c;
}
echo fibonacci(100) ."\n";

Essa função tem um problema de performance, pois a cada chamada recalcula toda a sequência de Fibonacci até o número passado. Sei resolver esse problema em outras linguagens usando memoizaçãodetalhes em en – uma espécie de cache interno da função. É possível fazer o mesmo em PHP? Como?

6
  • Teria como explicar resumidamente o que é memoização?
    – rray
    Commented 15/12/2015 às 16:53
  • @rray Defini muito brevemente, as respostas podem explicar mais :)
    – bfavaretto
    Commented 15/12/2015 às 17:03
  • 1
    Já ajudou um pouco, da pra twitar essa explicação :D
    – rray
    Commented 15/12/2015 às 17:05
  • 6
    +1 pela pergunta, e dois comentários: 1) essa função não tem chamadas recursivas, então não se beneficiaria da memoização; 2) essa implementação é razoavelmente boa para calcular um único elemento da sequência (linear com a entrada), apenas se forem calculados vários é que há desperdício de processamento (i.e. sem ver a pergunta linkada isso não está claro).
    – mgibsonbr
    Commented 15/12/2015 às 17:20
  • Encontrei um artigo interessante a respeito do assunto: eddmann.com/posts/implementing-and-using-memoization-in-php Commented 15/12/2015 às 17:49

1 Resposta 1

18

É possível fazer um cache do dado, que é o princípio básico da memoização, algo assim:

function fibonacci($n) {
    static $cache = array();
    if (isset($cache[$n])) return $cache[$n];
    $a = 0;
    $b = 1;
    $c = 1;
    for ($i = 1; $i < $n ; $i++) { 
        $c = $a + $b;
        $a = $b;
        $b = $c;
    }
    $cache[$n] = $c;
    return $c;
}

Veja funcionando no ideone. E no repl.it. Também coloquei no GitHub para referência futura.

A variável local estática foi usada para manter o estado entre as chamadas da função. Enquanto o código estiver sendo executado ela mantém seu valor. Ela funciona de forma semelhante à uma variável global, ou seja, seu tempo de vida é global. Mas seu escopo é local.

Esta solução é simplificada e ingênua, não tem nenhum tipo de persistência e não escala bem. Teria que fazer algo bem mais elaborado para atender outras demandas não tão triviais. Mas resolve legal para a maioria.

Se a preocupação é performance, neste tipo de algoritmo, é interessante pré-calcular uma sequência grande de números mais prováveis de uso e alocar no array já no código. Claro que poderá ter um consumo maior de memória. Até certo ponto compensa.

Esta técnica não funciona em todo tipo de algoritmo, especialmente em algoritmos não determinísticos, o que não é o caso presente.

Mas tem um jeito de já dar uma boa melhorada sem pré-calcular em tempo de desenvolvimento, ainda que vá consumir mais memória sem, potencialmente, precisar de todos os valores.

function fibonacci($n) {
    static $cache = array();
    static $prox = 3;
    $cache[0] = 0;
    $cache[1] = 1;
    $cache[2] = 1;
    if ($n < $prox) {
        echo "cache -> "; //está aqui só para mostrar que entrou aqui
        return $cache[$n];
    }
    for ($i = $prox; $i <= $n; $i++) $cache[$i] = $cache[$i - 1] + $cache[$i - 2];
    echo $i - $prox . " passos -> "; //está aqui só para mostrar que entrou aqui
    $prox = $n + 1;
    return $cache[$n];
}

Veja funcionando no ideone. E no repl.it. Também coloquei no GitHub para referência futura.

Se quiser otimizar em tempo de desenvolvimento, pode adicionar $cache[3] = 2;, $cache[3] = 3;, $cache[4] = 5;, etc. O ganho será pequeno.

Se sabe que vai usar em uma sequência grande e sabe o maior valor (mesmo aproximado) pode ajudar mandando executar este número maior, assim popula o cache.

A resposta que originou esta pergunta agora tem uma variação de cálculo que não precisa passar por toda sequência. O que diminui a necessidade do cache.

Tem um módulo para ajudar fazer cache de forma mais intensiva. Provavelmente pensaram em muita coisa que pode acontecer nessa situação e testaram bem. Mas pode ser um canhão pra matar passarinho.

Achei esta outra solução.

Particularmente prefiro a solução usando laço porque ela é mais natural em sequencia de dados. Recursão é para árvores e assemelhados.

3
  • Nesse caso eu diria: Guardar o valor de retorno da função na variável seria mais viável. +1 Commented 15/12/2015 às 17:31
  • A outra solução que você citou é similar à solução em JS, com closures. Mas prefiro o seu código com variável estática, fica mais simples. Eu sempre me esqueço que existe esse tipo de variável no PHP, pode ser mesmo uma mão na roda!
    – bfavaretto
    Commented 15/12/2015 às 17:48
  • 2
    É solução de programador pragmático ao invés de acadêmico. Assim como este algoritmo ser um loop ao invés de recursivo :P
    – Maniero
    Commented 15/12/2015 às 17:51

Você deve fazer log-in para responder a esta pergunta.

Esta não é a resposta que você está procurando? Pesquise outras perguntas com a tag .