为什么std::multimap比std::priority_queue慢？

Question

为什么std::multimap比std::priority_queue慢？

c++stdpriority-queuemultimap

6

我实现了一个算法，其中使用了优先队列。我受到了这个问题的启发：将std :: multimap转换为std :: priority_queue

我将存储多达1000万个具有特定优先级值的元素。

然后，我想要迭代直到队列为空。每次检索元素时，它也会从队列中删除。

之后，我会重新计算元素的优先级值，因为由于以前的迭代，它可能会改变。

如果值增加，我会再次将该元素插入队列。这取决于进度而发生得更加频繁。（在前25％时不会发生，在接下来的50％中会发生，在最后25％中会发生多次）。

在接收到下一个元素并且没有重新插入它之后，我将对其进行处理。为此，我不需要该元素的优先级值，而是需要技术ID。

这就是我直觉地选择使用 std::multimap 来实现这一点的原因，使用 .begin() 获取第一个元素，.insert() 插入它，.erase() 删除它。此外，我没有直觉地选择 std::priority_queue，因为其他问题回答了与该主题相关的问题，指出 std::priority_queue 最可能仅用于单个值而不是映射值。

阅读上面的链接后，我使用与链接中其他问题类似的优先队列重新实现了它。我的运行时间似乎不那么不平等（在1000万个元素上大约需要一个小时）。现在我想知道为什么 std::priority_queue 总体上更快。

实际上，我期望 std::multimap 更快，因为有许多重新插入。也许问题在于 multimap 的重新组织过于频繁？

- Kaspatoo

我很难理解你的算法。优先队列和multimap在语义上有很大的区别。一个是排序的关联容器，可以保存多个相同键的项。它必须通过键提供相当快的查找。另一个本质上是一个int，T对容器，旨在选择极端的int。它的约束较少。我希望它能更快一些。你的multimap中的键是否像链接问题中的那样是队列中的优先级？我理解得对吗？ - luk32

是的，在 multimap 中，键是特定元素的优先级值，并且优先级值可以（并且确实）多次出现。如果优先级值存在多次，则选择“组”的哪个元素首先并不重要。 - Kaspatoo

4个回答

2

我认为主要区别在于两个事实：

优先队列对元素的顺序约束较弱。它不必对键/优先级的整个范围进行排序，而multimap则必须提供该功能。优先队列只需保证第一/顶部元素最大。

因此，尽管它们的操作的理论时间复杂度相同（O(log(size) )），但我认为从multimap中删除和重新平衡RB树会执行更多操作，因为它只是需要移动更多的元素。（注意：RB-tree不是强制使用的，但往往被选择作为multimap的底层容器）

优先队列的底层容器在内存中是连续的（默认情况下是vector）。

我怀疑重新平衡可能也更慢，因为RB树依赖于节点（而不是向量的连续内存），这使其容易出现缓存未命中，尽管人们必须记住堆上的操作不是以迭代方式完成的，而是通过向量跳过。我想要确切地确定，就需要进行性能分析。

以上观点都适用于插入和删除。我认为差异在于大O符号中失去的常数因子。这是直观的思考。

- luk32

2

“map” 比较慢的抽象、高级解释是因为它做了更多的事情。它始终保持整个数据结构排序。这种特性是有代价的。如果您使用一个不保持所有元素排序的数据结构，那么您就不需要支付这个代价。

算法解释：

为满足复杂度要求，地图必须作为基于节点的结构实现，而优先队列可以作为动态数组实现。实现std::map是一个平衡（通常是红黑）树，而std::priority_queue是一个带有std::vector作为默认底层容器的堆。

堆插入通常非常快。堆插入的平均复杂度为O(1)，而平衡树的插入复杂度为O(log n)（最坏情况相同）。创建n个元素的优先队列的最坏情况复杂度为O(n)，而创建平衡树的复杂度为O(n log n)。更深入的比较请见：Heap vs Binary Search Tree (BST)。

额外说明：

通常，数组比基于节点的结构（如树或列表）更有效地使用CPU缓存。这是因为数组中相邻元素在内存中也是相邻的（高内存局部性），因此可以适合于单个缓存行。然而，链接结构的节点存在于内存中的任意位置（低内存局部性），通常只有一个或很少几个在单个缓存行中。现代CPU计算速度非常快，但内存速度是瓶颈。这就是为什么基于数组的算法和数据结构往往比基于节点的更快的原因。

- eerorika

1

虽然我同意@eerorika和@luk32的观点，但值得一提的是，在现实世界中，使用默认的STL分配器时，内存管理成本很容易超过一些数据结构维护操作，如更新指针以执行树旋转。根据实现，内存分配本身可能涉及树维护操作，并且可能触发系统调用，这会使成本更高。

在multi-map中，每个insert()和erase()都与内存分配和释放相关联，这通常比算法中的额外步骤慢得多。

然而，默认情况下，priority-queue使用向量，只有在容量耗尽时才触发内存分配（尽管这是一个更昂贵的内存分配，需要将所有存储的对象移动到新的内存位置）。在您的情况下，几乎所有分配都发生在priority-queue的第一次迭代中，而multi-map则在每个insert和erase中付出内存管理成本。

使用基于内存池的自定义分配器可以减轻地图内存管理方面的缺点。这也使您的缓存命中率与优先队列相当。当您的对象移动或复制开销较大时，它甚至可以胜过priority-queue。

- xiay

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Sam Varshavchik · Accepted Answer

总之，运行时配置文件包括从抽象优先队列中删除和插入元素的操作，您试图使用std::priority_queue和std::multimap作为实际实现。向优先队列和multimap中插入元素的复杂度大致相同：对数级别。但是，从multimap和priority queue中删除下一个元素存在很大差异。使用优先队列进行删除将是一个常数时间复杂度操作。底层容器是向量，您正在从向量中删除最后一个元素，这主要是无关紧要的。但是，从multimap的两个极端之一删除元素会导致树失衡并需要经常重新平衡整棵树。这将是一个昂贵的操作。这可能是您看到明显性能差异的原因。