Dijkstra na Java: Uzyskiwanie interesujących wyników przy użyciu sterty Fibonacciego vs. PriorityQueue

Question

Niedawno dokonałem wstępnego porównania czasu działania algorytmu Dijkstry przy użyciu dwóch struktur danych, opartego na Javie PriorityQueue (opartego na binarnej stercie, jeśli ja ' nie mylę się) i stertę Fibonacciego. Użyłem currentTimeMillis() Java, aby wykonać moje obliczenia. Rezultaty, które otrzymałem, są całkiem interesujące. Jest to wyjście do jednego z moich testami:

Running Dijkstra's with 8 nodes and 27 links 
- Execution time with binary heap: 1 miliseconds 
- Execution time with Fibonacci heap: 4 miliseconds 

Trzeba przyznać, że jestem mało zestawów danych w tej chwili, z powyższego wykresu jest moja największa (mam zamiar zrobić więcej wkrótce). Ale czy to ma jakiś sens? Zawsze uważałem, że stosy Fibonacciego były szybsze niż inne struktury danych ze względu na ich amortyzowany czas działania w porównaniu z innymi strukturami danych. Nie jestem pewien, skąd się bierze ta 3-milisekundowa różnica. (Używam go na procesorze Intel Core Ivy Bridge i7-3630M, jeśli to pomaga.)

Uwaga: natknąłem się na this thread, co może wyjaśnić problem, chociaż nadal nie jestem pewien, dlaczego sterty Fibonacci Wersja trwa dłużej. Zgodnie z tym wątkiem może to wynikać z tego, że mój wykres nie jest wystarczająco gęsty i dlatego liczba operacji zmniejszania liczby kluczowych nie jest wystarczająco duża, aby wydajność sterty Fibonacciego naprawdę się świeciła. Czy byłby to jedyny wiarygodny wniosek, czy może jest coś, czego mi brakuje?

Answer 1

Fibonacciego stosy są asymptotycznie szybciej niż hałdy binarnych (struktura danych wykorzystywana w pierwszej kolejki Java), w algorytmu Dijkstry weźmie O (m + n log n) ze sterty Fibonacciego ale O (m log n) z binarną stertą. Oznacza to, że w przypadku dużych, gęstych wykresów, w najgorszym przypadku, stosy Fibonacciego będą szybsze.

Chociaż hałdy Fibonacciego są asymptotycznie szybsze od hałd dwuskładnikowych, mają one bardzo duże stałe czynniki i wiele podstawowych operacji na stosach Fibonacciego zajmuje dużo czasu. Na dłuższą metę będą one przewyższać binarne stosy, ale w przypadku małych wykresów stałe warunki mogą być tak duże, że stertę Fibonacciego będzie wolniej.

Po drugie, porównaj asymptotyczne czasy działania (O (m + n log n) względem O (m log n)). Jeśli wykres, którego używasz jest rzadki (to jest m = O (n)), to oba te asymptotyczne środowiska wykonawcze są takie same (O (n log n)). W takim przypadku teoretyczna przewaga stosów Fibonacciego nie występuje, a kupa binarna może być lepszym wyborem.

Wreszcie należy zauważyć, że notacja big-o odnosi się do najgorszego przypadku w tym przypadku, a nie do przeciętnego przypadku. Jakiś czas temu pojawił się artykuł, który pokazał, że dla losowych wykresów pewnego typu algorytm Dijkstry na oczekiwaniu zajmuje znacznie mniej niż najgorsza liczba operacji zmniejszania klucza i usuwania. W takim przypadku binarna kupa może przewyższyć stertę Fibonacciego nawet na dużych wykresach, ponieważ zachowanie najgorszego przypadku nigdy nie zostanie wyzwolone.

Mam nadzieję, że to pomoże!

Answer 2

Stosy Fibonacciego mają szybsze asymptotykę, ale ich stałe czynniki niekoniecznie są świetne. Na śmiesznie dużych nakładach powyżej miliona, mogą być szybsze, ale przy niewielkich nakładach binarne stosy będą prawdopodobnie zauważalnie szybsze.