Czy ktoś rzeczywiście skutecznie zaimplementował stertę Fibonacciego?

Czy ktoś z was kiedykolwiek wdrożył stertę Fibonacciego ? Zrobiłem to kilka lat temu, ale było to o kilka rzędów wielkości wolniejsze niż użycie BinHeaps opartego na tablicy.

Wtedy pomyślałem o tym jako o wartościowej lekcji pokazującej, że badania nie zawsze są tak dobre, jak się twierdzą. Jednak wiele prac badawczych podaje czasy działania ich algorytmów opartych na używaniu sterty Fibonacciego.

Czy kiedykolwiek udało Ci się stworzyć wydajną implementację? A może pracowałeś z zestawami danych tak dużymi, że Sterta Fibonacciego była bardziej wydajna? Jeśli tak, docenimy pewne szczegóły.

Biblioteki Boost C ++ zawierają implementację stert Fibonacciego w boost/pending/fibonacci_heap.hpp. Ten plik najwyraźniej istnieje pending/od lat i według moich prognoz nigdy nie zostanie zaakceptowany. Ponadto w tej implementacji pojawiły się błędy, które zostały naprawione przez mojego znajomego i ogólnie fajnego gościa, Aarona Windsora. Niestety, większość wersji tego pliku, które udało mi się znaleźć w sieci (i ta w pakiecie libboost-dev Ubuntu) nadal zawierała błędy; Musiałem pobrać czystą wersję z repozytorium Subversion.

Od wersji 1.49 biblioteki Boost C ++ dodały wiele nowych struktur stert, w tym stertę Fibonacciego.

Udało mi się skompilować dijkstra_heap_performance.cpp ze zmodyfikowaną wersją dijkstra_shortest_paths.hpp, aby porównać sterty Fibonacciego i sterty binarne. (W wierszu typedef relaxed_heap<Vertex, IndirectCmp, IndexMap> MutableQueuezmień relaxedna fibonacci.) Najpierw zapomniałem skompilować z optymalizacjami, w którym to przypadku stosy Fibonacciego i binarne działają mniej więcej tak samo, przy czym sterty Fibonacciego zwykle osiągają niewiele lepsze wyniki. Po skompilowaniu z bardzo silnymi optymalizacjami stosy binarne uzyskały ogromny wzrost. W moich testach stosy Fibonacciego przewyższały stosy binarne tylko wtedy, gdy wykres był niewiarygodnie duży i gęsty, np .:

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.

O ile rozumiem, dotyka to podstawowych różnic między stertami Fibonacciego a stertami binarnymi. Jedyną prawdziwą teoretyczną różnicą między tymi dwiema strukturami danych jest to, że sterty Fibonacciego obsługują klucz zmniejszania w (amortyzowanym) stałym czasie. Z drugiej strony, stosy binarne uzyskują dużą wydajność dzięki ich implementacji jako tablicy; użycie jawnej struktury wskaźnika oznacza, że ​​stosy Fibonacciego mają ogromny wpływ na wydajność.

Dlatego, aby w praktyce skorzystać ze stosów Fibonacciego , trzeba ich używać w aplikacji, w której klawisze zmniejszania są niezwykle częste. W przypadku Dijkstry oznacza to, że bazowy wykres jest gęsty. Niektóre aplikacje mogą z natury rzeczy intensywnie zmniejszać_klucz; Chciałem wypróbować algorytm minimalnego cięcia Nagomochi-Ibaraki, ponieważ najwyraźniej generuje on wiele klawiszy zmniejszania, ale uzyskanie porównania czasu było zbyt dużym wysiłkiem.

Ostrzeżenie : mogłem zrobić coś złego. Możesz spróbować samodzielnie odtworzyć te wyniki.

Uwaga teoretyczna : Poprawiona wydajność stert Fibonacciego na zmniejsz_klucz jest ważna dla zastosowań teoretycznych, takich jak środowisko uruchomieniowe Dijkstry. Sterty Fibonacciego również przewyższają sterty binarne przy wstawianiu i scalaniu (obie amortyzowane w czasie stałym dla stert Fibonacciego). Wstawianie jest zasadniczo nieistotne, ponieważ nie wpływa na czas działania Dijkstry i dość łatwo jest zmodyfikować sterty binarne, aby również wstawiać w amortyzowanym stałym czasie. Scalanie w stałym czasie jest fantastyczne, ale nie dotyczy tej aplikacji.

Uwaga osobista : Razem z moim przyjacielem napisaliśmy kiedyś artykuł wyjaśniający nową kolejkę priorytetową, która próbowała odtworzyć (teoretyczny) czas działania stosów Fibonacciego bez ich złożoności. Artykuł nigdy nie został opublikowany, ale mój współautor zaimplementował stosy binarne, sterty Fibonacciego i naszą własną kolejkę priorytetową do porównywania struktur danych. Wykresy wyników eksperymentalnych wskazują, że stosy Fibonacciego nieznacznie przewyższają wykonane stosy binarne pod względem całkowitych porównań, co sugeruje, że stosy Fibonacciego działałyby lepiej w sytuacji, gdy koszt porównania przewyższa koszty ogólne. Niestety nie mam dostępnego kodu i prawdopodobnie w twojej sytuacji porównanie jest tanie, więc te komentarze są istotne, ale nie mają bezpośredniego zastosowania.

Nawiasem mówiąc, bardzo polecam próbę dopasowania środowiska wykonawczego stosów Fibonacciego do własnej struktury danych. Odkryłem, że sam wymyśliłem na nowo stosy Fibonacciego. Wcześniej pomyślałem, że wszystkie zawiłości stosów Fibonacciego były przypadkowymi pomysłami, ale potem zdałem sobie sprawę, że wszystkie są naturalne i dość wymuszone.

Knuth porównał stertę Fibonacciego i sterty binarne dla minimalnych drzew rozpinających w 1993 roku w swojej książce Stanford Graphbase . Odkrył, że fibonacci jest o 30 do 60 procent wolniejszy niż stosy binarne przy testowanych rozmiarach wykresów, 128 wierzchołków przy różnych gęstościach.

Kod źródłowy jest C (lub raczej CWEB który jest pomiędzy C, matematyki TEX) w MILES_SPAN przekroju.

Zrzeczenie się

Wiem, że wyniki są dość podobne i „wygląda na to, że czas pracy jest całkowicie zdominowany przez coś innego niż stos” (@Alpedar). Ale nie mogłem znaleźć żadnego dowodu na to w kodzie. Kod jest otwarty, więc jeśli znajdziesz cokolwiek, co może wpłynąć na wynik testu, powiedz mi.

Może zrobiłem coś źle, ale napisałem test na podstawie porównania A.Rexa :

• Fibonacci-Heap
• D-Ary-kupa (4)
• Binary-Heap
• Relaxed-Heap

Czasy wykonania (tylko dla pełnych wykresów) dla wszystkich stert były bardzo zbliżone. Test został wykonany dla pełnych wykresów z 1000,2000,3000,4000,5000,6000,7000 i 8000 wierzchołków. Dla każdego testu wygenerowano 50 losowych wykresów, a wynikiem jest średni czas każdego sterty:

Przepraszamy za wynik, nie jest on zbyt szczegółowy, ponieważ potrzebowałem go do zbudowania niektórych wykresów z plików tekstowych.

Oto wyniki (w sekundach):

Zrobiłem też mały eksperyment ze stertą Fibonacciego. Oto link do szczegółów: Eksperymentowanie z algorytmem dijkstras . Właśnie wyszukałem w Google terminy „Fibonacci sterta java” i wypróbowałem kilka istniejących implementacji stosu Fibonacciego o otwartym kodzie źródłowym. Wygląda na to, że niektóre z nich mają problemy z wydajnością, ale są takie, które są całkiem dobre. Przynajmniej pokonują naiwne i binarne wyniki PQ w moim teście. Może pomogą wdrożyć ten skuteczny.