Кто-нибудь действительно эффективно реализовал Fibonacci-Heap?

Ответ 1

Boost С++ libraries включают реализацию кучи Fibonacci в boost/pending/fibonacci_heap.hpp. Этот файл, по-видимому, находился в pending/ в течение многих лет, и мои прогнозы никогда не будут приняты. Кроме того, в этой реализации были ошибки, которые были зафиксированы моим знакомым и крутым крутым парнем Аароном Виндзором. К сожалению, в большинстве версий этого файла, который я мог найти в Интернете (и в пакете libbost-dev), все еще были ошибки; Мне пришлось вытащить чистую версию из репозитория Subversion.Забастовкa >

Поскольку версия 1.49 Boost С++ libraries добавила много новых структур куч, включая кукурузу фибоначчи.

Мне удалось скомпилировать dijkstra_heap_performance.cpp с измененной версией dijkstra_shortest_paths.hpp, чтобы сравнить кучи Фибоначчи и кучи. (В строке typedef relaxed_heap<Vertex, IndirectCmp, IndexMap> MutableQueue измените relaxed на fibonacci.) Сначала я забыл скомпилировать с оптимизацией, и в этом случае Fibonacci и двоичные кучи выполняют примерно то же самое, причем кучи Фибоначчи обычно превосходят незначительную сумму. После того, как я собрал очень сильную оптимизацию, бинарные кучи получили огромный импульс. В моих тестах кучи Фибоначчи только превосходили двоичные кучи, когда граф был невероятно большим и плотным, например:

Generating graph...10000 vertices, 20000000 edges.
Running Dijkstra with binary heap...1.46 seconds.
Running Dijkstra with Fibonacci heap...1.31 seconds.
Speedup = 1.1145.

Насколько я понимаю, это касается фундаментальных различий между кучками Фибоначчи и кучи двоичных. Единственное реальное теоретическое различие между двумя структурами данных состоит в том, что кучи Фибоначчи поддерживают сокращение-ключ в (амортизированном) постоянном времени. С другой стороны, двоичные кучи получают большую производительность от их реализации в виде массива; используя явную структуру указателя, означает, что кучи Фибоначчи имеют огромный успех.

Поэтому, чтобы извлечь выгоду из кучи Фибоначчи на практике, вы должны использовать их в приложении, где reduce_keys невероятно часты. В терминах Дейкстры это означает, что лежащий в основе граф является плотным. Некоторые приложения могут быть интенсивно уменьшены; Я хотел попробовать алгоритм минимального разреза Nagomochi-Ibaraki, потому что, по-видимому, он генерирует много уменьшенных_keys, но было слишком много усилий, чтобы получить временное сравнение работа.

Предупреждение: Возможно, я сделал что-то неправильно. Вы можете попробовать воспроизвести эти результаты самостоятельно.

Теоретическая заметка: улучшенная производительность кучи Fibonacci на reduce_key важна для теоретических приложений, таких как время исполнения Dijkstra. Кучи Фибоначчи также превосходят двоичные кучи при вставке и слиянии (оба амортизируются постоянным временем для кучи Фибоначчи). Вставка по существу не имеет значения, поскольку она не влияет на время исполнения Dijkstra, и довольно легко модифицировать двоичные кучи, чтобы иметь вставку в амортизированное постоянное время. Слияние в постоянное время фантастично, но не относится к этому приложению.

Личное примечание. Один мой друг и я как-то написали документ, объясняющий новую очередь приоритетов, которая пыталась воспроизвести (теоретическое) время работы кучи Фибоначчи без их сложности. Документ никогда не публиковался, но мой соавтор реализовал двоичные кучи, кучи Фибоначчи и нашу собственную очередь приоритетов для сравнения структур данных. Графики экспериментальных результатов показывают, что Фибоначчи кучи слегка вычеркнутых двоичных куч в терминах общих сравнений, предполагая, что кучи Фибоначчи будут лучше работать в ситуации, когда стоимость сравнения превышает накладные расходы. К сожалению, у меня нет кода, и, по-видимому, в вашей ситуации сравнение дешево, поэтому эти комментарии актуальны, но не применимы напрямую.

Кстати, я настоятельно рекомендую попробовать совместить время выполнения кучи Фибоначчи со своей собственной структурой данных. Я обнаружил, что я просто заново изобрел Фибоначчи. Прежде чем я подумал, что все сложности кучи Фибоначчи были некоторыми случайными идеями, но потом я понял, что они все естественны и довольно принудительны.

Ответ 2

Кнут сравнивал кучу фибоначчи и кучи двоичных кучей для минимальных остовных деревьев еще в 1993 году за свою книгу Stanford Graphbase. Он обнаружил, что фибоначчи были на 30-60% медленнее, чем бинарные кучи, при размерах графа, которые он тестировал, 128 вершин с разной плотностью.

Исходный код находится в C (или, скорее, CWEB, который является перекрестком между C, math и TeX) в разделе MILES_SPAN.

Ответ 3

Отказ

Я знаю, что результаты очень похожи и "похоже, что время работы полностью доминирует над чем-то, кроме кучи" (@Alpedar). Но я ничего не мог найти в коде. Код он открывается, поэтому, если вы можете найти что-нибудь, что может повлиять на результат теста, скажите мне.

Возможно, я сделал что-то не так, но я написал тест на основе A.Rex anwser:

• Фибоначчи-Heap
• D-Ary-heap (4)
• Binary-Heap
• Расслабление-Heap

Время выполнения (только для полных графиков) для всех куч было очень близко. Тест проводился для полных графиков с 1000 000 000 000 000 000 000 000 000 и 8000 вершин. Для каждого теста было создано 50 случайных графов, а выход - среднее время каждой кучи:

Извините за вывод, это не очень многословно, потому что мне нужно было создать некоторые диаграммы из текстовых файлов.

Вот результаты (в секундах):

Ответ 4

Я также сделал небольшой эксперимент с кучей Фибоначчи. Вот ссылка для деталей: Experimenting-with-dijkstras-algorithm. Я просто искал термины "куча кучи Fibonacci" и пробовал несколько существующих реализаций Fibonacci с открытым исходным кодом. Похоже, что некоторые из них имеют некоторые проблемы с производительностью, но есть некоторые, которые довольно хороши. По крайней мере, они избивают наивную и бинарную производительность PQ в моем тесте. Возможно, они могут помочь реализовать эффективный.