Alguém realmente implementou um Fibonacci-Heap com eficiência?

Alguém de vocês já implementou um Fibonacci-Heap ? Eu fiz isso alguns anos atrás, mas foi várias ordens de magnitude mais lenta do que usar BinHeaps baseados em array.

Naquela época, eu pensava nisso como uma lição valiosa de como a pesquisa nem sempre é tão boa quanto afirma ser. No entanto, muitos trabalhos de pesquisa afirmam os tempos de execução de seus algoritmos com base no uso de um Fibonacci-Heap.

Você já conseguiu produzir uma implementação eficiente? Ou você trabalhou com conjuntos de dados tão grandes que o Fibonacci-Heap foi mais eficiente? Nesse caso, alguns detalhes seriam apreciados.

As bibliotecas Boost C ++ incluem uma implementação de hibridos de Fibonacci no Windows boost/pending/fibonacci_heap.hpp. Aparentemente, esse arquivo existe pending/há anos e, de acordo com minhas projeções, nunca será aceito. Além disso, houve erros nessa implementação, que foram corrigidos pelo meu conhecido e pelo cara legal Aaron Windsor. Infelizmente, a maioria das versões desse arquivo que eu consegui encontrar on-line (e a do pacote libboost-dev do Ubuntu) ainda tinham os bugs; Eu tive que puxar uma versão limpa do repositório Subversion.

Desde a versão 1.49, as bibliotecas Boost C ++ adicionaram muitas novas estruturas de heaps, incluindo heap de fibonacci.

Consegui compilar dijkstra_heap_performance.cpp em uma versão modificada do dijkstra_shortest_paths.hpp para comparar pilhas de Fibonacci e pilhas binárias. (Na linha typedef relaxed_heap<Vertex, IndirectCmp, IndexMap> MutableQueue, mude relaxedpara fibonacci.) Primeiro, esqueci-me de compilar com otimizações . Nesse caso, Fibonacci e pilhas binárias realizam a mesma coisa, com as pilhas de Fibonacci geralmente superando uma quantidade insignificante. Depois que compilei com otimizações muito fortes, as pilhas binárias receberam um enorme impulso. Nos meus testes, os hibridos de Fibonacci apenas superaram os binários binários quando o gráfico era incrivelmente grande e denso, por exemplo:

Generating graph...10000 vertices, 20000000 edges.
Running Dijkstra's with binary heap...1.46 seconds.
Running Dijkstra's with Fibonacci heap...1.31 seconds.
Speedup = 1.1145.

Até onde eu entendo, isso toca nas diferenças fundamentais entre os montes de Fibonacci e os binários. A única diferença teórica real entre as duas estruturas de dados é que as pilhas de Fibonacci suportam chave decrescente no tempo constante (amortizado). Por outro lado, as pilhas binárias obtêm muito desempenho de sua implementação como uma matriz; o uso de uma estrutura explícita de ponteiros significa que as pilhas de Fibonacci sofrem um enorme impacto no desempenho.

Portanto, para se beneficiar dos montes de Fibonacci na prática , você deve usá-los em um aplicativo em que as teclas de diminuição são incrivelmente frequentes. Em termos de Dijkstra, isso significa que o gráfico subjacente é denso. Alguns aplicativos podem ser intrinsecamente intensos em key_key; Eu queria experimentar o algoritmo de corte mínimo de Nagomochi-Ibaraki porque, aparentemente, gera muitas teclas de diminuição, mas foi muito esforço para fazer uma comparação de tempo funcionar.

Aviso : Eu posso ter feito algo errado. Você pode tentar reproduzir esses resultados você mesmo.

Nota teórica : O desempenho aprimorado dos montes de Fibonacci no decréscimo-chave é importante para aplicações teóricas, como o tempo de execução de Dijkstra. As pilhas de Fibonacci também superam as pilhas binárias na inserção e mesclagem (ambas amortizadas em tempo constante pelas pilhas de Fibonacci). A inserção é essencialmente irrelevante, porque não afeta o tempo de execução do Dijkstra, e é bastante fácil modificar as pilhas binárias para também inserir no tempo constante amortizado. Mesclar em tempo constante é fantástico, mas não relevante para esta aplicação.

Nota pessoal : Um amigo meu e eu uma vez escrevemos um artigo explicando uma nova fila de prioridades, que tentou replicar o tempo de execução (teórico) dos montes de Fibonacci sem sua complexidade. O artigo nunca foi publicado, mas meu co-autor implementou pilhas binárias, pilhas de Fibonacci e nossa própria fila de prioridade para comparar as estruturas de dados. Os gráficos dos resultados experimentais indicam que os montes de Fibonacci superaram os montantes binários ligeiramente superiores em comparação total, sugerindo que os montes de Fibonacci teriam melhor desempenho em uma situação em que o custo de comparação excede a sobrecarga. Infelizmente, não tenho o código disponível e, presumivelmente, na sua comparação de situação é barato, esses comentários são relevantes, mas não são diretamente aplicáveis.

Aliás, eu recomendo tentar combinar o tempo de execução dos hibridos de Fibonacci com sua própria estrutura de dados. Eu descobri que simplesmente reinventei Fibonacci. Antes de pensar que todas as complexidades dos montes de Fibonacci eram algumas idéias aleatórias, mas depois percebi que eram todas naturais e razoavelmente forçadas.

Knuth fez uma comparação entre a pilha de fibonacci e a pilha binária para árvores de abrangência mínima em 1993 para seu livro Stanford Graphbase . Ele descobriu que os fibonacci eram 30 a 60 precedentes mais lentos que os binários nos tamanhos de gráfico que ele estava testando, 128 vértices em densidades diferentes.

O código fonte está em C (ou melhor, CWEB, que é um cruzamento entre C, matemática e TeX) na seção MILES_SPAN.

aviso Legal

Eu sei que os resultados são bastante semelhantes e "parece que o tempo de execução é totalmente dominado por algo diferente da pilha" (@Alpedar). Mas não consegui encontrar nenhuma evidência disso no código. O código está aberto; portanto, se você encontrar algo que possa afetar o resultado do teste, informe-me.

Talvez eu tenha feito algo errado, mas escrevi um teste , com base na análise do A.Rex comparando:

• Fibonacci-Heap
• D-Ary-heap (4)
• Pilha binária
• Pilha descontraída

Os tempos de execução (apenas para gráficos completos) para todos os montões foram muito próximos. O teste foi realizado para gráficos completos com 1000,2000,3000,4000,5000,6000,7000 e 8000 vértices. Para cada teste, 50 gráficos aleatórios foram gerados e o resultado é o tempo médio de cada heap:

Desculpe a saída, não é muito detalhado, porque eu precisava criar alguns gráficos a partir de arquivos de texto.

Aqui estão os resultados (em segundos):

Também fiz um pequeno experimento com a pilha de Fibonacci. Aqui está o link para os detalhes: Experimentando com o dijkstras-algoritmo . Eu apenas pesquisei os termos "Fibonacci heap java" e tentei algumas implementações de código aberto existentes do hibrido Fibonacci. Parece que alguns deles têm algum problema de desempenho, mas há alguns que são bastante bons. Pelo menos, eles estão superando o desempenho PQ da pilha ingênua e binária no meu teste. Talvez eles possam ajudar a implementar o eficiente.