Adakah yang benar-benar mengimplementasikan Fibonacci-Heap secara efisien?

Apakah ada di antara Anda yang pernah menerapkan Fibonacci-Heap ? Saya melakukannya beberapa tahun yang lalu, tapi beberapa kali lipat lebih lambat daripada menggunakan BinHeaps berbasis array.

Saat itu, saya menganggapnya sebagai pelajaran berharga tentang bagaimana penelitian tidak selalu sebagus seperti yang diklaim. Namun, banyak makalah penelitian mengklaim waktu menjalankan algoritma mereka berdasarkan menggunakan Fibonacci-Heap.

Apakah Anda pernah berhasil menghasilkan implementasi yang efisien? Atau apakah Anda bekerja dengan set data yang sangat besar sehingga Fibonacci-Heap lebih efisien? Jika demikian, beberapa detail akan dihargai.

The Meningkatkan C ++ perpustakaan mencakup implementasi tumpukan Fibonacci di boost/pending/fibonacci_heap.hpp. File ini tampaknya sudah pending/bertahun-tahun dan dengan proyeksi saya tidak akan pernah diterima. Juga, ada bug dalam implementasi itu, yang diperbaiki oleh kenalan saya dan cowok keren yang serba bisa, Aaron Windsor. Sayangnya, sebagian besar versi file itu yang dapat saya temukan online (dan yang ada di paket libboost-dev Ubuntu) masih memiliki bug; Saya harus menarik versi bersih dari repositori Subversion.

Sejak versi 1.49 Boost C ++ libraries menambahkan banyak heaps struct baru termasuk fibonacci heap.

Saya dapat mengkompilasi dijkstra_heap_performance.cpp terhadap versi modifikasi dari dijkstra_shortest_paths.hpp untuk membandingkan tumpukan Fibonacci dan tumpukan biner. (Sejalan typedef relaxed_heap<Vertex, IndirectCmp, IndexMap> MutableQueue, ubah relaxedmenjadi fibonacci.) Saya pertama kali lupa mengkompilasi dengan optimisasi, dalam hal ini Fibonacci dan tumpukan biner berkinerja sama, dengan tumpukan Fibonacci biasanya mengungguli dengan jumlah yang tidak signifikan. Setelah saya kompilasi dengan optimasi yang sangat kuat, tumpukan biner mendapat dorongan besar. Dalam pengujian saya, Fibonacci tumpukan hanya mengungguli tumpukan biner ketika grafik sangat besar dan padat, misalnya:

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.

Sejauh yang saya mengerti, ini menyentuh perbedaan mendasar antara tumpukan Fibonacci dan tumpukan biner. Satu-satunya perbedaan teoretis nyata antara kedua struktur data adalah bahwa tumpukan Fibonacci mendukung penurunan kunci dalam waktu konstan (diamortisasi). Di sisi lain, tumpukan biner mendapatkan banyak kinerja dari implementasi mereka sebagai sebuah array; menggunakan struktur penunjuk eksplisit berarti tumpukan Fibonacci mengalami pukulan kinerja yang sangat besar.

Oleh karena itu, untuk mendapatkan manfaat dari tumpukan Fibonacci dalam praktiknya , Anda harus menggunakannya dalam aplikasi di mana penurunan_kunci sangat sering terjadi. Dalam hal Dijkstra, ini berarti bahwa grafik yang mendasarinya padat. Beberapa aplikasi bisa secara intrinsik mengurangi_kunci; Saya ingin mencoba algoritma pemotongan minimum Nagomochi-Ibaraki karena ternyata ia menghasilkan banyak penurunan_kunci, tetapi terlalu banyak upaya untuk membuat perbandingan waktu berfungsi.

Peringatan : Saya mungkin telah melakukan kesalahan. Anda mungkin ingin mencoba mereproduksi hasil ini sendiri.

Catatan Teoritis : Peningkatan kinerja tumpukan Fibonacci di penurunan_key penting untuk aplikasi teoretis, seperti runtutan Dijkstra. Fibonacci tumpukan juga mengungguli tumpukan biner pada penyisipan dan penggabungan (keduanya diamortisasi waktu-konstan untuk tumpukan Fibonacci). Penyisipan pada dasarnya tidak relevan, karena tidak memengaruhi runtuhnya Dijkstra, dan cukup mudah untuk memodifikasi tumpukan biner dan juga memasukkan waktu diamortisasi yang disisipkan. Menggabungkan dalam waktu yang konstan itu fantastis, tetapi tidak relevan dengan aplikasi ini.

Catatan pribadi : Seorang teman saya dan saya pernah menulis makalah yang menjelaskan antrian prioritas baru, yang mencoba mereplikasi waktu berjalan (secara teoritis) tumpukan Fibonacci tanpa kerumitan mereka. Makalah ini tidak pernah diterbitkan, tetapi rekan penulis saya mengimplementasikan tumpukan biner, tumpukan Fibonacci, dan antrian prioritas kami sendiri untuk membandingkan struktur data. Grafik dari hasil percobaan menunjukkan bahwa Fibonacci menumpuk sedikit melebihi kinerja biner dalam hal perbandingan total, menunjukkan bahwa tumpukan Fibonacci akan berkinerja lebih baik dalam situasi di mana biaya perbandingan melebihi overhead. Sayangnya, saya tidak memiliki kode yang tersedia, dan mungkin dalam perbandingan situasi Anda murah, jadi komentar ini relevan tetapi tidak secara langsung berlaku.

Secara kebetulan, saya sangat merekomendasikan untuk mencoba mencocokkan runtime dari tumpukan Fibonacci dengan struktur data Anda sendiri. Saya menemukan bahwa saya hanya menemukan kembali Fibonacci menumpuk sendiri. Sebelum saya berpikir bahwa semua kerumitan tumpukan Fibonacci adalah beberapa ide acak, tetapi setelah itu saya menyadari bahwa semuanya adalah alami dan cukup dipaksakan.

Knuth melakukan perbandingan antara fibonacci Heap dan tumpukan biner untuk pohon spanning minimum kembali pada tahun 1993 untuk bukunya Stanford Graphbase . Dia menemukan fibonacci menjadi 30 hingga 60 lebih lambat dari tumpukan biner pada ukuran grafik yang dia uji, 128 simpul pada kepadatan yang berbeda.

The kode sumber dalam C (atau lebih tepatnya CWEB yang merupakan persilangan antara C, matematika dan TeX) di bagian MILES_SPAN.

Penolakan

Saya tahu hasilnya sangat mirip dan "sepertinya waktu berjalan benar-benar didominasi oleh sesuatu selain tumpukan" (@Alpedar). Tetapi saya tidak dapat menemukan bukti apa pun dalam kode itu. Kode terbuka, jadi jika Anda dapat menemukan apa pun yang dapat memengaruhi hasil tes, beri tahu saya.

Mungkin saya melakukan sesuatu yang salah, tetapi saya menulis tes , berdasarkan A.Rex anwser membandingkan:

• Fibonacci-Heap
• D-Ary-heap (4)
• Biner-Tumpukan
• Santai-Tumpukan

Waktu eksekusi (hanya untuk grafik lengkap) untuk semua tumpukan sangat dekat. Tes ini dibuat untuk grafik lengkap dengan 1000.2000.3000.4000.5000.6000.7000 dan 8000 simpul. Untuk setiap tes 50 grafik acak dihasilkan dan output adalah waktu rata-rata setiap tumpukan:

Maaf tentang hasilnya, ini tidak terlalu bertele-tele karena saya membutuhkannya untuk membuat beberapa bagan dari file teks.

Inilah hasilnya (dalam detik):

Saya juga melakukan percobaan kecil dengan tumpukan Fibonacci. Berikut ini tautan untuk detailnya: Eksperimen-dengan-dijkstras-algoritme . Saya hanya googled istilah "Fibonacci heap java" dan mencoba beberapa implementasi open-source dari Fibonacci heap. Tampaknya beberapa dari mereka memiliki masalah kinerja, tetapi ada beberapa yang cukup bagus. Setidaknya, mereka mengalahkan kinerja PQ naif dan tumpukan biner dalam pengujian saya. Mungkin mereka dapat membantu menerapkan yang efisien.