如何提高 Boost Fibonacci Heap 性能

Question

我正在实现 Fast Marching 算法，它是某种连续 Dijkstra 算法。正如我在许多论文中读到的那样，斐波那契堆是最适合此目的的堆。

然而，当使用 callgrind 分析我的代码时，我发现以下函数占用了 58% 的执行时间：

int popMinIdx () {
    const int idx = heap_.top()->getIndex();
    heap_.pop();
    return idx; 
}

具体来说，它pop()占用了整个执行时间的 57.67%。

heap_定义如下：

boost::heap::fibonacci_heap<const FMCell *, boost::heap::compare<compare_cells>> heap_;

花费“那么多”时间是否正常，或者我可以做些什么来提高性能？

抱歉，如果没有提供足够的信息。我尝试尽可能简短。如果需要，我会添加更多信息。

谢谢你！

Answer 1

其他答案没有提到重要的部分：当然 pop() 占用了您的大部分时间：它是唯一执行任何实际工作的函数！

您可能已经读到，斐波那契堆的操作范围是摊销范围。这意味着，如果您以良好的顺序执行足够的操作，则边界将达到平均水平。然而，实际成本完全被隐藏。

每次插入元素时，都不会发生任何事情。它只是被扔到根列表中。繁荣，O(1) 时间。每次合并两棵树时，它的根都会链接到根列表中。繁荣，O(1) 时间。但是等等，您的结构不是有效的斐波那契堆！这就是 pop() （或 extract-root）发挥作用的地方：每次调用此操作时，整个堆都会重新构造为正确的形状。根被删除，它的子节点被切到根列表，然后我们开始合并根列表中的树，以便根列表中不存在具有相同度数（子节点数量）的两棵树。

因此，Insert(e) 和 Merge(t) 的所有工作实际上都会延迟到调用 Pop() 为止，然后由 Pop() 完成所有工作。其他操作呢？

删除（e）很漂亮。我们执行 Decrease-Key(e, -inf) 使元素 e 成为根。现在我们执行 Pop()！同样，这项工作是由 Pop() 完成的。

Decrease-Key(e, v) 自行完成工作：它将 e 剪切到根列表，并启动剪切级联将其子项也放入根列表（这也可以剪切它们的子项列表）。因此 Decrease-Key 将大量元素放入根列表中。你能猜出哪个函数必须解决这个问题吗？

TL;DR：Pop() 是斐波那契堆的主力。所有其他操作都可以高效完成，因为它们为 Pop() 操作创建了工作。Pop() 收集工作并一次性执行它（最多可能需要 O(n)）。这实际上非常有效，因为“分组”工作可以比单独的每个操作更快地完成。

所以，是的，Pop() 很自然地占用了你的大部分时间！