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