Кто-нибудь на самом деле реализовал Фибоначчи-кучу эффективно?

The Boost C++ библиотеки включить реализацию куч Фибоначчи в boost/pending/fibonacci_heap.hpp. Этот файл, по-видимому, был в pending/ в течение многих лет и по моим прогнозам никогда не будет принято. Кроме того, в этой реализации были ошибки, которые были исправлены моим знакомым и все вокруг крутым парнем Аароном Виндзором. К сожалению, большинство версий этого файла, которые я мог найти в интернете (и в пакете libboost-dev Ubuntu), все еще имели ошибки; мне пришлось тянуть чистая версия из репозитория Subversion.

начиная с версии 1.49Boost C++ библиотеки добавлено много новых структур куч, включая кучу Фибоначчи.

мне удалось скомпилировать dijkstra_heap_performance.cpp против измененной версии dijkstra_shortest_paths.ГЭС для сравнения куч Фибоначчи и двоичных куч. (В строке typedef relaxed_heap<Vertex, IndirectCmp, IndexMap> MutableQueue, изменения relaxed до 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.

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

поэтому, чтобы извлечь выгоду из кучи Фибоначчи на практике, вы должны использовать их в приложении, где decrease_keys невероятно часто. В терминах Дейкстры это означает, что лежащий в основе граф плотен. Некоторые приложения могут быть внутренне decrease_key-intense; я хотел попробовать алгоритм минимального разреза Нагомочи-Ибараки потому что, по-видимому, он генерирует много decrease_keys, но это было слишком много усилий, чтобы получить сравнение времени работы.

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

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

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

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