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

heaps fibonacci

Question

¿Alguno de ustedes ha implementado alguna vez un Fibonacci-Heap ? Lo hice hace unos años, pero fue varios órdenes de magnitud más lento que el uso de BinHeaps basadas en arreglos.

En aquel entonces, pensé que era una lección valiosa sobre cómo la investigación no siempre es tan buena como dice ser. Sin embargo, muchos trabajos de investigación afirman que los tiempos de ejecución de sus algoritmos se basan en el uso de Fibonacci-Heap.

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

Answer 1

Knuth hizo una comparación entre el montón de fibonacci y montones binarios para árboles de expansión mínima en 1993 para su libro Stanford Graphbase . Encontró que el fibonacci era 30 a 60 veces más lento que los montones binarios en los tamaños de gráfico 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.

Answer 2

También hice un pequeño experimento con Fibonacci Heap. Aquí está el enlace para los detalles: Experimenting-with-dijkstras-algorithm . Acabo de buscar en Google los términos "Fibonacci heap java" y probé algunas implementaciones de código abierto existentes 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 ingenuo y el rendimiento PQ del montón binario en mi prueba. Tal vez puedan ayudar a implementar el eficiente.

Answer 3

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

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

Pude compilar dijkstra_heap_performance.cpp con 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 relaxed a fibonacci .) Primero olvidé compilar con optimizaciones, en cuyo caso Fibonacci y montones binarios funcionan más o menos igual, con montones de Fibonacci generalmente superando en una cantidad insignificante . Después de compilar con optimizaciones muy fuertes, montones binarios obtuvieron un impulso enorme. 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.

Por lo que yo 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 Fibonacci acumula la clave de disminución de soporte 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 golpe de 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 lower_key-intense; Quería probar el algoritmo de corte mínimo de Nagomochi-Ibaraki porque aparentemente genera muchas teclas para disminuir, pero era demasiado esfuerzo para lograr que la comparación de tiempos funcionara.

Advertencia : puedo haber hecho algo mal. Puede intentar reproducir estos resultados usted mismo.

Nota teórica : El rendimiento mejorado de los montones de Fibonacci en decrease_key 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 la fusión (ambos amortizados en tiempo constante para los 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 el tiempo constante amortizado. La combinación en tiempo constante es fantástica, pero no relevante para esta aplicación.

Nota personal : un amigo mío y yo una vez escribimos un artículo explicando una nueva cola de prioridad, 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 de prioridad para comparar las estructuras de datos. Las gráficas de los resultados experimentales indican que Fibonacci acumula un poco de rendimiento binario en términos de comparaciones totales, lo que sugiere que los montones de Fibonacci funcionarían mejor en una situación donde el costo de comparación excede la sobrecarga. 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.

A propósito, recomiendo tratar de hacer coincidir el tiempo de ejecución de montones de Fibonacci con su propia estructura de datos. Descubrí que simplemente reinventé montones de Fibonacci yo mismo. 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.

Answer 4

Renuncia

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 ninguna evidencia 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, por favor dígame.

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

• Fibonacci-Heap
• D-Ary-heap (4)
• Binario-Heap
• Relajado-Heap

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 el resultado es el tiempo promedio de cada pila:

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):