¿Alguien ha implementado realmente un Fibonacci-Heap de manera eficiente?

¿Alguno de ustedes alguna vez ha implementado un Fibonacci-Heap ? Lo hice hace unos años, pero fue mucho más lento que usar BinHeaps basado en matrices.

En aquel entonces, lo consideraba una valiosa lección sobre cómo la investigación no siempre es tan buena como dice ser. Sin embargo, muchos trabajos de investigación afirman los tiempos de ejecución de sus algoritmos basados ​​en el uso de un Fibonacci-Heap.

¿Alguna vez lograste producir una implementación eficiente? ¿O trabajó con conjuntos de datos tan grandes que Fibonacci-Heap fue más eficiente? Si es así, se agradecerían algunos detalles.

Las bibliotecas Boost C ++ incluyen una implementación de montones de Fibonacci en boost/pending/fibonacci_heap.hpp. Aparentemente, este archivo ha estado pending/por años y, según mis proyecciones, nunca será aceptado. Además, ha habido errores en esa implementación, que fueron solucionados por mi conocido y genial chico Aaron Windsor. Desafortunadamente, la mayoría de las versiones de ese archivo que pude encontrar en línea (y la del paquete libboost-dev de Ubuntu) todavía tenían errores; Tuve que extraer una versión limpia del repositorio de Subversion.

Desde la versión 1.49, las bibliotecas Boost C ++ agregaron muchas nuevas estructuras de montones, incluido el montón de Fibonacci.

Pude compilar dijkstra_heap_performance.cpp contra una versión modificada de dijkstra_shortest_paths.hpp para comparar montones de Fibonacci y montones binarios. (En la línea typedef relaxed_heap<Vertex, IndirectCmp, IndexMap> MutableQueue, cambie relaxeda fibonacci.) Primero olvidé compilar con optimizaciones, en cuyo caso Fibonacci y los montones binarios tienen un rendimiento similar, con montones de Fibonacci que generalmente superan en una cantidad insignificante. Después de compilar con optimizaciones muy fuertes, los montones binarios tuvieron un enorme impulso. En mis pruebas, los montones de Fibonacci solo superaron a los montones binarios cuando el gráfico era increíblemente grande y denso, por ejemplo:

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.

Hasta donde entiendo, esto toca las diferencias fundamentales entre los montones de Fibonacci y los montones binarios. La única diferencia teórica real entre las dos estructuras de datos es que los montones de Fibonacci admiten clave de disminución en tiempo constante (amortizado). Por otro lado, los montones binarios obtienen un gran rendimiento de su implementación como una matriz; El uso de una estructura de puntero explícita significa que los montones de Fibonacci sufren un gran impacto en el rendimiento.

Por lo tanto, para beneficiarse de los montones de Fibonacci en la práctica , debe usarlos en una aplicación donde las teclas de disminución son increíblemente frecuentes. En términos de Dijkstra, esto significa que el gráfico subyacente es denso. Algunas aplicaciones pueden ser intrínsecamente decrecientes_intensivas; Quería probar el algoritmo de corte mínimo de Nagomochi-Ibaraki porque aparentemente genera muchas teclas decreciente, pero fue demasiado esfuerzo hacer funcionar una comparación de tiempos.

Advertencia : puedo haber hecho algo mal. Es posible que desee intentar reproducir estos resultados usted mismo.

Nota teórica : el rendimiento mejorado de los montones de Fibonacci en decremento_clave es importante para aplicaciones teóricas, como el tiempo de ejecución de Dijkstra. Los montones de Fibonacci también superan a los montones binarios en la inserción y fusión (ambos amortizados en tiempo constante para montones de Fibonacci). La inserción es esencialmente irrelevante, porque no afecta el tiempo de ejecución de Dijkstra, y es bastante fácil modificar los montones binarios para que también tengan inserción en tiempo constante amortizado. Combinar en tiempo constante es fantástico, pero no es relevante para esta aplicación.

Nota personal : un amigo mío y yo una vez escribimos un artículo explicando una nueva cola prioritaria, que intentaba replicar el tiempo de ejecución (teórico) de los montones de Fibonacci sin su complejidad. El documento nunca se publicó, pero mi coautor implementó montones binarios, montones de Fibonacci y nuestra propia cola prioritaria para comparar las estructuras de datos. Los gráficos de los resultados experimentales indican que los montones de Fibonacci superaron ligeramente los montones binarios en términos de comparaciones totales, lo que sugiere que los montones de Fibonacci funcionarían mejor en una situación en la que el costo de comparación excede los gastos generales. Desafortunadamente, no tengo el código disponible, y presumiblemente en su situación la comparación es barata, por lo que estos comentarios son relevantes pero no directamente aplicables.

Por cierto, recomiendo tratar de hacer coincidir el tiempo de ejecución de los montones de Fibonacci con su propia estructura de datos. Descubrí que simplemente reinventé los montones de Fibonacci. Antes pensaba que todas las complejidades de los montones de Fibonacci eran algunas ideas aleatorias, pero luego me di cuenta de que todas eran naturales y bastante forzadas.

Knuth hizo una comparación entre el montón de fibonacci y los montones binarios para árboles de expansión mínima en 1993 para su libro Stanford Graphbase . Encontró que los fibonacci son 30 a 60 por ciento más lentos que los montones binarios en los tamaños de gráficos que estaba probando, 128 vértices a diferentes densidades.

El código fuente está en C (o más bien CWEB, que es un cruce entre C, matemáticas y TeX) en la sección MILES_SPAN.

Descargo de responsabilidad

Sé que los resultados son bastante similares y "parece que el tiempo de ejecución está totalmente dominado por algo más que el montón" (@Alpedar). Pero no pude encontrar nada de eso en el código. El código está abierto, así que si puede encontrar algo que pueda afectar el resultado de la prueba, dígamelo.

Tal vez hice algo mal, pero escribí una prueba , basada en A.Rex y comparando:

• Montón de Fibonacci
• Montón D-Ary (4)
• Binary-Heap
• Montón relajado

Los tiempos de ejecución (solo para gráficos completos) para todos los montones fueron muy cercanos. La prueba se realizó para gráficos completos con 1000,2000,3000,4000,5000,6000,7000 y 8000 vértices. Para cada prueba se generaron 50 gráficos aleatorios y la salida es el tiempo promedio de cada montón:

Perdón por el resultado, no es muy detallado porque lo necesitaba para construir algunos gráficos a partir de archivos de texto.

Aquí están los resultados (en segundos):

También hice un pequeño experimento con el montón de Fibonacci. Aquí está el enlace para los detalles: Experimenting-with-dijkstras-Algoritmo . Acabo de buscar en Google los términos "Fibonacci Heap Java" e intenté algunas implementaciones de código abierto del montón de Fibonacci. Parece que algunos de ellos tienen algún problema de rendimiento, pero hay algunos que son bastante buenos. Al menos, están superando el rendimiento ingenuo y binario del PQ del montón en mi prueba. Tal vez puedan ayudar a implementar la eficiente.