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

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

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

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

Библиотеки 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.) Сначала я забыл скомпилировать с оптимизациями, и в этом случае Фибоначчи и двоичные кучи работают примерно одинаково, причем кучи Фибоначчи обычно опережают на незначительную величину. После того, как я скомпилировал с очень сильными оптимизациями, двоичные кучи получили огромный импульс. В моих тестах кучи Фибоначчи превосходили только двоичные кучи, когда граф был невероятно большим и плотным, например:

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, математике и текс) в разделе MILES_SPAN.

отказ

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

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

• Фибоначчи-Heap
• D-Ary-heap (4)
• Binary-Heap
• Relaxed-Heap

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

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

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

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