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

Кто-нибудь из вас когда-либо реализовал Фибоначчи-Кучу ? Я сделал это несколько лет назад, но это было на несколько порядков медленнее, чем использование BinHeaps на базе массива.

В то время я думал об этом как ценном уроке в том, как исследование не всегда так хорошо, как кажется. Тем не менее, многие исследовательские работы требуют времени работы их алгоритмов на основе использования Fibonacci-Heap.

Вы когда-нибудь смогли создать эффективную реализацию? Или вы работали с наборами данных настолько большими, что Fibonacci-Heap был более эффективным? Если да, то некоторые детали будут оценены.

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

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

Я смог скомпилировать dijkstra_heap_performance.cpp против модифицированной версии dijkstra_shortest_paths.hpp, чтобы сравнить кучи Фибоначчи и двоичные кучи. (В строке typedef relaxed_heap MutableQueue , измените relaxed на 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. 

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

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

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

Теоретическая заметка : улучшенная производительность кучи Fibonacci на reduce_key важна для теоретических приложений, таких как время исполнения Dijkstra. Кучи Фибоначчи также превосходят двоичные кучи при вставке и слиянии (оба амортизируются постоянным временем для кучи Фибоначчи). Вставка по существу не имеет значения, поскольку она не влияет на время работы 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 000 000 000 000 000 000 000 000 и 8000 вершин. Для каждого теста было создано 50 случайных графов, а выход – среднее время каждой кучи:

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


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

таблица результатов кучи

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

Давайте будем гением компьютера.