Кто-нибудь на самом деле эффективно реализовал Фибоначчи-кучу?
Кто-нибудь из вас когда-либо реализовывал кучу Фибоначчи? Я сделал это несколько лет назад, но это было на несколько порядков медленнее, чем использование BinHeaps на основе массива.
Тогда я считал это ценным уроком о том, что исследования не всегда так хороши, как утверждают. Тем не менее, многие исследовательские работы утверждают, что время их алгоритмов основано на использовании Фибоначчи-кучи.
Вам когда-нибудь удавалось создать эффективную реализацию? Или вы работали с такими большими наборами данных, что куча Фибоначчи была более эффективной? Если это так, некоторые детали будут оценены.
5 ответов
Библиотеки Boost C++ включают в себя реализацию куч Фибоначчи в boost/pending/fibonacci_heap.hpp , Этот файл, очевидно, был в pending/ годами и по моим прогнозам никогда не будет принято. Кроме того, в этой реализации были ошибки, которые исправил мой знакомый и крутой парень Аарон Виндзор. К сожалению, в большинстве версий этого файла, которые я смог найти в Интернете (и в версии Ubuntu libboost-dev), все еще были ошибки; Мне пришлось вытащить чистую версию из хранилища Subversion.
Начиная с версии 1.49 библиотеки Boost C++ добавили много новых структур кучи, включая кучу Фибоначчи.
Мне удалось скомпилировать dijkstra_heap_performance.cpp с измененной версией dijkstra_shortest_paths.hpp, чтобы сравнить кучи Фибоначчи и двоичные кучи. (В соответствии typedef relaxed_heap<Vertex, IndirectCmp, IndexMap> MutableQueue, менять relaxed в fibonacci.) Сначала я забыл скомпилировать с оптимизациями, и в этом случае Fibonacci и двоичные кучи работают примерно одинаково, причем кучи Fibonacci, как правило, выигрывают незначительно. После того, как я скомпилировал с очень сильными оптимизациями, двоичные кучи получили огромный импульс. В моих тестах кучи Фибоначчи превосходили только двоичные кучи, когда граф был невероятно большим и плотным, например:
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.
Насколько я понимаю, это касается фундаментальных различий между кучами Фибоначчи и двоичными кучами. Единственное реальное теоретическое различие между этими двумя структурами данных заключается в том, что кучи Фибоначчи поддерживают постоянное время (амортизированное) с уменьшением ключа. С другой стороны, двоичные кучи получают большую производительность от своей реализации в виде массива; использование явной структуры указателя означает, что кучи Фибоначчи сильно страдают от производительности.
Поэтому, чтобы на практике использовать кучи Фибоначчи, вы должны использовать их в приложении, в котором невероятно часто используются кнопки В терминах Дейкстры это означает, что основной граф плотный. Некоторые приложения могут быть по сути уменьшением_ключа-интенсивным; Я хотел попробовать алгоритм минимального разреза Нагомочи-Ибараки, потому что, очевидно, он генерирует много ключей lower_keys, но это было слишком много усилий, чтобы заставить работать сравнение по времени.
Предупреждение: возможно, я сделал что-то не так. Вы можете попытаться воспроизвести эти результаты самостоятельно.
Теоретическое примечание: улучшенная производительность кучи Фибоначчи при уменьшении_ключа важна для теоретических приложений, таких как время выполнения Дейкстры. Кучи Фибоначчи также превосходят двоичные кучи при вставке и слиянии (обе амортизируются постоянным временем для кучи Фибоначчи). Вставка, по сути, не имеет значения, потому что она не влияет на время выполнения Dijkstra, и довольно легко изменить двоичные кучи, чтобы также вставлять в амортизированное постоянное время. Слияние в постоянное время является фантастическим, но не имеет отношения к этому приложению.
Личное примечание: мой друг и я однажды написали статью, объясняющую новую очередь приоритетов, в которой была предпринята попытка воспроизвести (теоретическое) время работы кучи Фибоначчи без их сложности. Документ так и не был опубликован, но мой соавтор реализовал двоичные кучи, кучи Фибоначчи и нашу собственную очередь приоритетов для сравнения структур данных. Графики экспериментальных результатов показывают, что кучи Фибоначчи немного превосходят двоичные кучи с точки зрения общего сравнения, что позволяет предположить, что кучи Фибоначчи будут работать лучше в ситуации, когда стоимость сравнения превышает накладные расходы. К сожалению, у меня нет доступного кода, и, по-видимому, в вашей ситуации сравнение дешево, поэтому эти комментарии актуальны, но не имеют прямого отношения.
Кстати, я настоятельно рекомендую попытаться сопоставить время выполнения кучи Фибоначчи с вашей собственной структурой данных. Я обнаружил, что просто заново изобрел кучи Фибоначчи. Раньше я думал, что все сложности кучи Фибоначчи были случайными идеями, но потом я понял, что все они были естественными и довольно вынужденными.
Кнут провел сравнение между кучей Фибоначчи и двоичными кучами для минимальных остовных деревьев еще в 1993 году для своей книги Stanford Graphbase. Он обнаружил, что фибоначчи на 30-60% ниже, чем двоичные кучи при размерах тестируемого им графа, 128 вершин с различной плотностью.
Исходный код находится на C (точнее CWEB, который представляет собой нечто среднее между C, math и TeX) в разделе MILES_SPAN.
отказ
Я знаю, что результаты довольно схожи и "похоже, что во время выполнения полностью доминирует нечто иное, чем куча" (@Alpedar). Но я не смог найти никаких доказательств этого в коде. Код открыт, поэтому, если вы можете найти что-то, что может повлиять на результат теста, пожалуйста, сообщите мне.
Возможно, я сделал что-то не так, но я написал тест, основанный на сравнении A.Rex и anwser:
- Фибоначчи-Heap
- D-Ary-heap (4)
- Binary-Heap
- Расслабление-Heap
Время выполнения (только для полных графиков) для всех куч было очень близко. Тест был выполнен для полных графов с 1000,2000,3000,4000,5000,6000,7000 и 8000 вершин. Для каждого теста было сгенерировано 50 случайных графиков, а на выходе - среднее время каждой кучи:
Извините за вывод, он не очень многословен, потому что он мне нужен для построения некоторых диаграмм из текстовых файлов.
Вот результаты (в секундах):
есть довольно исчерпывающий ответ, а также проверенная реализация алгоритма Дейкстры на С++ с кучами Фибоначчи.Здесь
Я также провел небольшой эксперимент с кучей Фибоначчи. Вот ссылка для деталей: Эксперимент-с-Дайкстра-алгоритм. Я просто погуглил термины "куча java Фибоначчи" и попробовал несколько существующих реализаций кучи Фибоначчи с открытым исходным кодом. Кажется, что у некоторых из них есть проблемы с производительностью, но есть и такие, которые весьма хороши. По крайней мере, они бьют в моем тесте производительность PQ в двоичном и кучном тестах. Может быть, они могут помочь реализовать эффективный.