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


151

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.


25
Czy nie nauczyłeś się, że ci kolesie z algorytmów zawsze ukrywają swoje ogromne stałe za dużymi, dużymi och ?! :) W praktyce wydaje się, że w większości przypadków rzecz „n” nigdy nie zbliża się nawet do „n0”!
Mehrdad Afshari

Już wiem. Zaimplementowałem go, kiedy po raz pierwszy otrzymałem kopię „Wstępu do algorytmów”. Poza tym nie wybrałem Tarjana na kogoś, kto wymyśliłby bezużyteczną strukturę danych, ponieważ jego Splay-Drzewa są w rzeczywistości całkiem fajne.
mdm

mdm: Oczywiście nie jest to bezużyteczne, ale podobnie jak sortowanie przez wstawianie, które pokonuje szybkie sortowanie w małych zestawach danych, sterty binarne mogą działać lepiej z powodu mniejszych stałych.
Mehrdad Afshari

1
Właściwie program, którego potrzebowałem, znajdował drzewa Steinera do routingu w układach VLSI, więc zbiory danych nie były zbyt małe. Ale obecnie (poza prostymi rzeczami, takimi jak sortowanie) zawsze używałbym prostszego algorytmu, dopóki nie „zepsuje” zbioru danych.
mdm

1
Moja odpowiedź brzmi właściwie „tak”. (Cóż, mój współautor na papierze tak.) Nie mam teraz kodu, więc uzyskam więcej informacji, zanim faktycznie odpowiem. Patrząc jednak na nasze wykresy, zauważam, że stosy F dają mniej porównań niż sterty b. Czy korzystałeś z czegoś, gdzie porównanie było tanie?
A. Rex

Odpowiedzi:


136

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.


Dzięki! To pytanie od dawna tkwiło w mojej głowie. Właściwie zaimplementowałem Dijkstrę używając Fibonacciego-Heapsa, zanim spróbowałem Steiner-Trees. Wydaje się jednak, że moje wykresy są znacznie mniej gęste niż w twoim przykładzie. Mieli miliony węzłów, ale średni stopień to tylko 5-6.
mdm

Wydajność sterty Fib jest przewidywalna na podstawie sekwencji operacji. Napisałem algorytm ciężki jak Heap, który skończył szybciej w Fib Heap (w porównaniu do Bin Heap). Sztuczka polegała na podzieleniu pracy. Niezależnie od częstotliwości jakiejkolwiek operacji, różnica leży tutaj: DecreaseKey - ExtractMin - DecreaseKey - ExtractMin versus DecreaseKey - DecreaseKey - ExtractMin - ExtractMin (cd. Poniżej)
Gaminic

Ten ostatni będzie mniej więcej dwa razy szybszy, ponieważ 2nd ExtractMin jest prawie darmowy. Nasz algorytm wyodrębnia pakiet elementów Min, z których wiele jest odrzucanych; marnotrawstwo na stercie śmieci, ale lepsze na stercie Fib. Niestety, nie jest to wyraźnie odzwierciedlone w złożoności czasu, którą ludzie zapewniają, mówiąc o algorytmach opartych na sterty. Z amortyzowanymi granicami, całkowita złożoność nie jest po prostu # operacjami * złożonością operacji.
Gaminic

1
Czy jest szansa na wypróbowanie parowania stosów i / lub zrelaksowanych stosów?
Thomas Ahle

1
Nie jestem pewien, dlaczego twoje wyniki były tak blisko, użyłem STL priority_queue vs samodzielnie zaimplementowana sterta fibonacciego, a sterta binarna była w moich testach z dużym marginesem .
Nicholas Pipitone

33

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.


1

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

tabela wyników sterty


4
Ile krawędzi jest w każdym przypadku? A jaki dokładnie algorytm używasz? Twoje wyniki nie mają sensu, jeśli nie wiemy, z czym mamy do czynienia.
kokx

Niestety, wszystkie wykresy są kompletne, więc możesz obliczyć liczbę krawędzi dla każdego przypadku. Co masz na myśli, „czy biegniesz dokładnie”. Są na czele stołów.
Guilherme Torres Castro

22
Wygląda na to, że czas działania jest całkowicie zdominowany przez coś innego niż sterta (może to być generowanie wykresu lub niektóre operacje we / wy). Te prawie identyczne wyniki są niewiarygodne.
Alpedar

2
Cóż, może czas jest zdominowany przez coś innego, ale jestem pewien, że to nie jest IO ani generowanie wykresów. W każdym razie kod źródłowy jest dostępny i będę bardzo zadowolony, jeśli ktoś znajdzie błąd i poprawi wynik.
Guilherme Torres Castro

Te testy wydają się mierzyć coś zupełnie innego. Czy mógłbyś skomentować test, który przeprowadziłeś? Pamiętaj, że problem najkrótszej ścieżki na pełnym wykresie to O (1), jeśli odległości są geometryczne / euklidesowe.
Gaminic

0

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.

Korzystając z naszej strony potwierdzasz, że przeczytałeś(-aś) i rozumiesz nasze zasady używania plików cookie i zasady ochrony prywatności.
Licensed under cc by-sa 3.0 with attribution required.