Existe alguma maneira de acelerar a recursão lembrando-se dos nós filhos?

Question

Por exemplo, observe o código que calcula o número n -th fibonacci:

fib(int n)
{
    if(n==0 || n==1)
        return 1;
    return fib(n-1) + fib(n-2);
}

O problema com esse código é que ele gerará erro de estouro de pilha para qualquer número maior que 15 (na maioria dos computadores).

Suponha que estejamos calculando fib(10).Neste processo, digamos que fib(5) é calculado muitas vezes.Existe alguma maneira de armazenar isso na memória para recuperação rápida e, assim, aumentar a velocidade da recursão?

Estou procurando uma técnica genérica que possa ser usada em quase todos os problemas.

Answer 1

Sim, sua visão está correta.Isso é chamado programaçao dinamica.Geralmente é uma troca comum de tempo de execução de memória.

No caso do fibo, você nem precisa armazenar tudo em cache:

Editar] O autor da pergunta parece estar procurando um método geral para armazenar em cache, em vez de um método para calcular o Fibonacci.Pesquise na Wikipedia ou veja o código do outro autor da postagem para obter esta resposta.Essas respostas são lineares no tempo e na memória.

**Aqui está um algoritmo de tempo linear O(n), constante na memória **

in OCaml:

let rec fibo n = 
    let rec aux = fun
        | 0 -> (1,1)
        | n -> let (cur, prec) = aux (n-1) in (cur+prec, cur)
    let (cur,prec) = aux n in prec;;



in C++:

int fibo(int n) {
    if (n == 0 ) return 1;
    if (n == 1 ) return 1;
    int p = fibo(0);
    int c = fibo(1);
    int buff = 0;
    for (int i=1; i < n; ++i) {
      buff = c;
      c = p+c;
      p = buff;
    };
    return c;
};

Isso funciona em tempo linear.Mas log é realmente possível!!!O programa do Roo também é linear, mas muito mais lento e usa memória.

Aqui está o algoritmo de log O(log(n))

Agora, para o algoritmo de tempo de log (muito mais rápido), aqui está um método:Se você conhece u(n), u(n-1), calcular u(n+1), u(n) pode ser feito aplicando uma matriz:

| u(n+1) |  = | 1 1 | | u(n)   |
| u(n)   |    | 1 0 | | u(n-1) |    

Para que você tenha:

| u(n)    |  = | 1 1 |^(n-1) | u(1) | = | 1 1 |^(n-1) | 1 |
| u(n-1)  |    | 1 0 |       | u(0) |   | 1 0 |       | 1 |

Calcular o exponencial da matriz tem uma complexidade logarítmica.Basta implementar recursivamente a ideia:

M^(0)    = Id
M^(2p+1) = (M^2p) * M
M^(2p)   = (M^p) * (M^p)  // of course don't compute M^p twice here.

Você também pode simplesmente diagonalizá-lo (não muito difícil), você encontrará o número dourado e seu conjugado em seu autovalor, e o resultado lhe dará uma fórmula matemática EXATA para u(n).Ele contém potências desses autovalores, de modo que a complexidade ainda será logarítmica.

Fibo é frequentemente tomado como exemplo para ilustrar a Programação Dinâmica, mas como você pode ver, não é realmente pertinente.

@John:Não acho que tenha algo a ver com hash.

@João2:Um mapa é um pouco genérico, você não acha?Para o caso de Fibonacci, todas as chaves são contíguas para que um vetor seja apropriado, mais uma vez existem maneiras muito mais rápidas de calcular a sequência fibo, veja meu exemplo de código ali.

Answer 2

Isso se chama memoização e há um artigo muito bom sobre memoização Mateus Podwysocki postado esses dias.Ele usa Fibonacci para exemplificar isso.E mostra o código em C# também.Leia-o aqui.

Answer 3

Se você estiver usando C# e puder usar PostSharp, aqui está um aspecto simples de memorização para seu código:

[Serializable]
public class MemoizeAttribute : PostSharp.Laos.OnMethodBoundaryAspect, IEqualityComparer<Object[]>
{
    private Dictionary<Object[], Object> _Cache;

    public MemoizeAttribute()
    {
        _Cache = new Dictionary<object[], object>(this);
    }

    public override void OnEntry(PostSharp.Laos.MethodExecutionEventArgs eventArgs)
    {
        Object[] arguments = eventArgs.GetReadOnlyArgumentArray();
        if (_Cache.ContainsKey(arguments))
        {
            eventArgs.ReturnValue = _Cache[arguments];
            eventArgs.FlowBehavior = FlowBehavior.Return;
        }
    }

    public override void OnExit(MethodExecutionEventArgs eventArgs)
    {
        if (eventArgs.Exception != null)
            return;

        _Cache[eventArgs.GetReadOnlyArgumentArray()] = eventArgs.ReturnValue;
    }

    #region IEqualityComparer<object[]> Members

    public bool Equals(object[] x, object[] y)
    {
        if (Object.ReferenceEquals(x, y))
            return true;

        if (x == null || y == null)
            return false;

        if (x.Length != y.Length)
            return false;

        for (Int32 index = 0, len = x.Length; index < len; index++)
            if (Comparer.Default.Compare(x[index], y[index]) != 0)
                return false;

        return true;
    }

    public int GetHashCode(object[] obj)
    {
        Int32 hash = 23;

        foreach (Object o in obj)
        {
            hash *= 37;
            if (o != null)
                hash += o.GetHashCode();
        }

        return hash;
    }

    #endregion
}

Aqui está um exemplo de implementação de Fibonacci usando-o:

[Memoize]
private Int32 Fibonacci(Int32 n)
{
    if (n <= 1)
        return 1;
    else
        return Fibonacci(n - 2) + Fibonacci(n - 1);
}

Answer 4

Memoização rápida e suja em C++:

Qualquer método recursivo type1 foo(type2 bar) { ... } é facilmente memorizado com map<type2, type1> M.

// your original method
int fib(int n)
{
    if(n==0 || n==1)
        return 1;
    return fib(n-1) + fib(n-2);
}

// with memoization
map<int, int> M = map<int, int>();
int fib(int n)
{
    if(n==0 || n==1)
        return 1;

    // only compute the value for fib(n) if we haven't before
    if(M.count(n) == 0)
        M[n] = fib(n-1) + fib(n-2);

    return M[n];
}

EDITAR:@Konrad Rodolfo
Konrad ressalta que std::map não é a estrutura de dados mais rápida que poderíamos usar aqui.Isso é verdade, um vector<something> deveria ser mais rápido que um map<int, something> (embora possa exigir mais memória se as entradas para as chamadas recursivas da função não forem números inteiros consecutivos como são neste caso), mas os mapas são geralmente convenientes para uso.

Answer 5

De acordo com Wikipédia Fib(0) deveria ser 0, mas isso não importa.

Aqui está uma solução C# simples com for cycle:

ulong Fib(int n)
{
  ulong fib = 1;  // value of fib(i)
  ulong fib1 = 1; // value of fib(i-1)
  ulong fib2 = 0; // value of fib(i-2)

  for (int i = 0; i < n; i++)
  {
    fib = fib1 + fib2;
    fib2 = fib1;
    fib1 = fib;
  }

  return fib;
}

É um truque bastante comum converter recursão em recursão de cauda e depois fazer um loop.Para mais detalhes veja por exemplo este palestra (ppt).

Answer 6

Que língua é essa?Não transborda nada em c...Além disso, você pode tentar criar uma tabela de pesquisa no heap ou usar um mapa

Answer 7

o cache geralmente é uma boa ideia para esse tipo de coisa.Como os números de Fibonacci são constantes, você pode armazenar o resultado em cache depois de calculá-lo.Um exemplo rápido de c/pseudocódigo

class fibstorage {


    bool has-result(int n) { return fibresults.contains(n); }
    int get-result(int n) { return fibresult.find(n).value; }
    void add-result(int n, int v) { fibresults.add(n,v); }

    map<int, int>   fibresults;

}


fib(int n ) {
    if(n==0 || n==1)
            return 1;

    if (fibstorage.has-result(n)) {
        return fibstorage.get-result(n-1);
    }

    return ( (fibstorage.has-result(n-1) ? fibstorage.get-result(n-1) : fib(n-1) ) +
             (fibstorage.has-result(n-2) ? fibstorage.get-result(n-2) : fib(n-2) )
           );
}


calcfib(n) {
    v = fib(n);
    fibstorage.add-result(n,v);
}

Isto seria bastante lento, pois cada recursão resulta em 3 pesquisas, no entanto isto deve ilustrar a ideia geral

Answer 8

Este é um exemplo escolhido deliberadamente?(por exemplo.um caso extremo que você deseja testar)

Como atualmente é O (1,6 ^ n), só quero ter certeza de que você está apenas procurando respostas sobre como lidar com o caso geral deste problema (armazenamento de valores em cache, etc.) e não apenas escrevendo acidentalmente um código ruim: D

Olhando para este caso específico, você poderia ter algo como:

var cache = [];
function fib(n) {
    if (n < 2) return 1;
    if (cache.length > n) return cache[n];
    var result = fib(n - 2) + fib(n - 1);
    cache[n] = result;
    return result;
}

O que degenera para O (n) no pior caso: D

[Editar:* não é igual a +: D]

[Mais uma edição:a versão Haskell (porque sou masoquista ou algo assim)

fibs = 1:1:(zipWith (+) fibs (tail fibs))
fib n = fibs !! n

]

Answer 9

Tente usar um mapa, n é a chave e seu número de Fibonacci correspondente é o valor.

@Paulo

Obrigado pela informação.Eu não sabia disso.De Link da Wikipédia você mencionou:

Essa técnica de salvar valores que já foram calculados é chamada de memorização

Sim, já olhei o código (+1).:)

Answer 10

@ESRogs:

std::map a pesquisa é Ó(registro n) o que o torna lento aqui.Melhor usar um vetor.

vector<unsigned int> fib_cache;
fib_cache.push_back(1);
fib_cache.push_back(1);

unsigned int fib(unsigned int n) {
    if (fib_cache.size() <= n)
        fib_cache.push_back(fib(n - 1) + fib(n - 2));

    return fib_cache[n];
}

Answer 11

Outros responderam bem e com precisão à sua pergunta - você está procurando memorização.

Linguagens de programação com otimização de chamada final (principalmente linguagens funcionais) podem executar certos casos de recursão sem estouro de pilha.Não se aplica diretamente à sua definição de Fibonacci, embora existam truques.

A formulação da sua pergunta me fez pensar em uma ideia interessante.Evitar o estouro de pilha de uma função recursiva pura, armazenando apenas um subconjunto de quadros de pilha e reconstruindo quando necessário.Realmente útil apenas em alguns casos.Se o seu algoritmo depende apenas condicionalmente do contexto em oposição ao retorno, e/ou você está otimizando a memória e não a velocidade.

Answer 12

O Mathematica tem uma maneira particularmente inteligente de fazer memorização, contando com o fato de que hashes e chamadas de função usam a mesma sintaxe:

fib[0] = 1;
fib[1] = 1;
fib[n_] := fib[n] = fib[n-1] + fib[n-2]

É isso.Ele armazena em cache (memoiza) fib[0] e fib[1] imediatamente e armazena em cache o restante conforme necessário.As regras para chamadas de função de correspondência de padrões são tais que sempre usam uma definição mais específica antes de uma definição mais geral.

Answer 13

Mais um excelente recurso para programadores C# para recursão, parciais, curry, memoização e similares é o blog de Wes Dyer, embora ele não poste há algum tempo.Ele explica bem a memorização, com exemplos de código sólidos aqui:http://blogs.msdn.com/wesdyer/archive/2007/01/26/function-memoization.aspx

Answer 14

O problema com esse código é que ele gerará erro de estouro de pilha para qualquer número maior que 15 (na maioria dos computadores).

Realmente?Qual computador você está usando?Está demorando muito aos 44, mas a pilha não está transbordando.Na verdade, você obterá um valor maior do que um número inteiro pode conter (~ 4 bilhões de não assinados, ~ 2 bilhões de assinados) antes que a pilha transborde (Fibbonaci (46)).

Isso funcionaria para o que você deseja fazer (executa rapidamente)

class Program
{
    public static readonly Dictionary<int,int> Items = new Dictionary<int,int>();
    static void Main(string[] args)
    {
        Console.WriteLine(Fibbonacci(46).ToString());
        Console.ReadLine();
    }

    public static int Fibbonacci(int number)
    {
        if (number == 1 || number == 0)
        {
            return 1;
        }

        var minus2 = number - 2;
        var minus1 = number - 1;

        if (!Items.ContainsKey(minus2))
        {
            Items.Add(minus2, Fibbonacci(minus2));
        }

        if (!Items.ContainsKey(minus1))
        {
            Items.Add(minus1, Fibbonacci(minus1));
        }

        return (Items[minus2] + Items[minus1]);
    }
}

Answer 15

Se você estiver usando uma linguagem com funções de primeira classe como Scheme, poderá adicionar memoização sem alterar o algoritmo inicial:

(define (memoize fn)
  (letrec ((get (lambda (query) '(#f)))
           (set (lambda (query value)
                  (let ((old-get get))
                    (set! get (lambda (q)
                                (if (equal? q query)
                                    (cons #t value)
                                    (old-get q))))))))
    (lambda args
      (let ((val (get args)))
        (if (car val)
            (cdr val)
            (let ((ret (apply fn args)))
              (set args ret)
              ret))))))


(define fib (memoize (lambda (x)
                       (if (< x 2) x
                           (+ (fib (- x 1)) (fib (- x 2)))))))

O primeiro bloco fornece um recurso de memorização e o segundo bloco é a sequência de Fibonacci que usa esse recurso.Agora ele tem um tempo de execução O(n) (em oposição a O(2^n) para o algoritmo sem memorização).

Observação:o recurso de memorização fornecido usa uma cadeia de fechamentos para procurar invocações anteriores.Na pior das hipóteses, isso pode ser O (n).Neste caso, porém, os valores desejados estão sempre no topo da cadeia, garantindo a pesquisa O(1).

Answer 16

Como outros cartazes indicaram, memorização é uma maneira padrão de trocar memória por velocidade. Aqui está um pseudocódigo para implementar memoização para qualquer função (desde que a função não tenha efeitos colaterais):

Código de função inicial:

 function (parameters)
      body (with recursive calls to calculate result)
      return result

Isto deveria ser transformado para

 function (parameters)
      key = serialized parameters to string
      if (cache[key] does not exist)  {
           body (with recursive calls to calculate result)
           cache[key] = result
      }
      return cache[key]

Answer 17

A propósito, Perl tem um memorizar módulo que faz isso para qualquer função em seu código que você especificar.

# Compute Fibonacci numbers
sub fib {
      my $n = shift;
      return $n if $n < 2;
      fib($n-1) + fib($n-2);
}

Para memorizar esta função, tudo o que você faz é iniciar seu programa com

use Memoize;
memoize('fib');
# Rest of the fib function just like the original version.
# Now fib is automagically much faster ;-)

Answer 18

@lassevk:

Isso é incrível, exatamente o que eu estava pensando depois de ler sobre memoização em Perl de ordem superior.Duas coisas que acho que seriam acréscimos úteis:

1. Um parâmetro opcional para especificar um método estático ou de membro usado para gerar a chave para o cache.
2. Uma maneira opcional de alterar o objeto de cache para que você possa usar um cache de disco ou banco de dados.

Não tenho certeza de como fazer esse tipo de coisa com atributos (ou se eles são possíveis com esse tipo de implementação), mas pretendo tentar descobrir.

(Fora do assunto:Eu estava tentando postar isso como um comentário, mas não percebi que os comentários têm um comprimento permitido tão curto, então isso não cabe como uma 'resposta')