c++ 为什么 std::multimap 比 std::priority_queue 慢
c++ Why std::multimap is slower than std::priority_queue
我实现了一种使用优先级队列的算法。
我被这个问题所激励：
Transform a std::multimap into std::priority_queue
我将存储多达 1000 万个具有特定优先级值的元素。
然后我想迭代直到队列为空。
每次检索一个元素时，它也会从队列中删除。
在此之后我重新计算元素的优先级值，因为之前的迭代它可能会改变。
如果值确实增加了，我将再次将该元素插入到队列中。
这种情况更经常发生取决于进度。 （前 25% 不会发生，接下来的 50% 会发生，最后 25% 会发生多次）。
收到下一个元素后没有重新插入，我准备处理。这是因为我不需要这个元素的优先级值，而是这个元素的技术 ID。
这就是我凭直觉选择 std::multimap 来实现此目的的原因，使用 .begin() 获取第一个元素，使用 .insert() 插入它，使用 .erase()去掉它。
此外，我没有凭直觉直接选择 std::priority_queue，因为该主题的其他问题回答 std::priority_queue 很可能仅用于单个值而不用于映射值。
在阅读了上面的 link 之后，我使用优先级队列类比 link 中的另一个问题重新实现了它。
我的运行时间似乎并没有那么不平衡（10 个 mio 元素大约需要一个小时）。
现在我想知道为什么 std::priority_queue 更快。
我实际上希望 std::multimap 更快，因为有很多重新插入。
也许问题是multimap的重组太多了？
总而言之：您的运行时配置文件涉及从抽象优先级队列中删除和插入元素，您尝试同时使用 std::priority_queue 和 std::multimap 作为实际实现。
插入优先级队列和插入多映射具有大致相同的复杂度：对数。
但是，从多重映射中删除下一个元素与从优先级队列中删除下一个元素有很大的不同。对于优先级队列，这将是一个 constant-complexity 操作。底层容器是一个向量，您要从向量中删除最后一个元素，该元素主要是 nothing-burger.
但是对于多图，您要从多图的极端之一中删除元素。
多图的典型底层实现是平衡的 red/black 树。从多图的一个极端中重复删除元素很可能会使树倾斜，需要对整个树进行频繁的重新平衡。这将是一项昂贵的操作。
这可能是您看到明显的性能差异的原因。
我认为主要区别来自两个事实：
- 优先级队列对元素顺序的约束较弱。它不必对 keys/priorities 的整个范围进行排序。 Multimap，必须提供。优先级队列只需要保证第一个/顶部元素最大。
因此，虽然两者操作的理论时间复杂度相同 O(log(size))，但我认为 erase 来自 multimap，并重新平衡 RB-tree 执行更多的操作，它只需要移动更多的元素。 （注意：RB-tree 不是强制性的，但经常被选为 multimap 的底层容器）
- 优先级队列的底层容器在内存中是连续的（默认是
vector）。
我怀疑重新平衡也比较慢，因为 RB-tree 依赖于节点（相对于 vector 的连续内存），这使得它容易出现缓存未命中，尽管必须记住堆上的操作没有完成以迭代的方式，它在向量中跳跃。我想真的有人必须对它进行分析。
以上几点对于插入和擦除都是正确的。我会说区别在于 big-O 表示法中丢失的常数因子。这是直觉。
对 map 较慢的抽象、高级解释是它做的更多。它始终保持整个结构排序。此功能是有代价的。如果您使用不对所有元素进行排序的数据结构，则无需支付该费用。
算法解释：
为了满足复杂性要求，map必须实现为基于节点的结构，而优先级队列可以实现为动态数组。 std::map 的实现是一个平衡的（通常是 red-black）树，而 std::priority_queue 是一个以 std::vector 作为默认底层容器的堆。
堆插入通常很快。与平衡树的 O(log n) 相比，插入堆的平均复杂度为 O(1)（尽管最坏情况相同）。创建 n 个元素的优先级队列的最坏情况复杂度为 O(n)，而创建平衡树为 O(n log n)。查看更多深度比较：Heap vs Binary Search Tree (BST)
另外，实现细节：
数组通常使用 CPU 缓存比树或列表等基于节点的结构更有效。这是因为数组的相邻元素在内存中相邻（高内存局部性），因此可能适合单个缓存行。然而，链接结构的节点存在于内存中的任意位置（低内存局部性），并且通常只有一个或很少的节点位于单个缓存行中。现代 CPUs 的计算速度非常非常快，但内存速度是一个瓶颈。这就是为什么基于数组的算法和数据结构往往比基于节点的算法和数据结构快得多。
虽然我同意@eerorika 和@luk32，但值得一提的是，在现实世界中，当使用默认的 STL 分配器时，内存管理成本很容易超过一些数据结构维护操作，例如更新指针到执行树旋转。根据实现，内存分配本身可能涉及树维护操作并可能触发系统调用，这将变得更加昂贵。
在 multi-map 中，内存分配和释放分别与每个 insert() 和 erase() 相关联，这通常比算法。
priority-queue 但是，默认情况下使用 vector ，一旦容量耗尽，它只会触发内存分配（虽然更广泛，涉及将所有存储的对象移动到新的内存位置） .在您的情况下，几乎所有分配仅发生在 priority-queue 的第一次迭代中，而 multi-map 一直在为每个 insert 和 erase.
支付内存管理成本
可以通过使用基于内存池的自定义分配器来缓解 map 内存管理的缺点。这也为您提供了与优先级队列相当的缓存命中率。当您的对象很容易移动或复制时，它的性能甚至可能优于 priority-queue。
我实现了一种使用优先级队列的算法。 我被这个问题所激励： Transform a std::multimap into std::priority_queue
我将存储多达 1000 万个具有特定优先级值的元素。
然后我想迭代直到队列为空。 每次检索一个元素时，它也会从队列中删除。
在此之后我重新计算元素的优先级值，因为之前的迭代它可能会改变。
如果值确实增加了，我将再次将该元素插入到队列中。 这种情况更经常发生取决于进度。 （前 25% 不会发生，接下来的 50% 会发生，最后 25% 会发生多次）。
收到下一个元素后没有重新插入，我准备处理。这是因为我不需要这个元素的优先级值，而是这个元素的技术 ID。
这就是我凭直觉选择 std::multimap 来实现此目的的原因，使用 .begin() 获取第一个元素，使用 .insert() 插入它，使用 .erase()去掉它。
此外，我没有凭直觉直接选择 std::priority_queue，因为该主题的其他问题回答 std::priority_queue 很可能仅用于单个值而不用于映射值。
在阅读了上面的 link 之后，我使用优先级队列类比 link 中的另一个问题重新实现了它。
我的运行时间似乎并没有那么不平衡（10 个 mio 元素大约需要一个小时）。
现在我想知道为什么 std::priority_queue 更快。
我实际上希望 std::multimap 更快，因为有很多重新插入。
也许问题是multimap的重组太多了？
总而言之：您的运行时配置文件涉及从抽象优先级队列中删除和插入元素，您尝试同时使用 std::priority_queue 和 std::multimap 作为实际实现。
插入优先级队列和插入多映射具有大致相同的复杂度：对数。
但是，从多重映射中删除下一个元素与从优先级队列中删除下一个元素有很大的不同。对于优先级队列，这将是一个 constant-complexity 操作。底层容器是一个向量，您要从向量中删除最后一个元素，该元素主要是 nothing-burger.
但是对于多图，您要从多图的极端之一中删除元素。
多图的典型底层实现是平衡的 red/black 树。从多图的一个极端中重复删除元素很可能会使树倾斜，需要对整个树进行频繁的重新平衡。这将是一项昂贵的操作。
这可能是您看到明显的性能差异的原因。
我认为主要区别来自两个事实：
- 优先级队列对元素顺序的约束较弱。它不必对 keys/priorities 的整个范围进行排序。 Multimap，必须提供。优先级队列只需要保证第一个/顶部元素最大。
因此，虽然两者操作的理论时间复杂度相同 O(log(size))，但我认为 erase 来自 multimap，并重新平衡 RB-tree 执行更多的操作，它只需要移动更多的元素。 （注意：RB-tree 不是强制性的，但经常被选为 multimap 的底层容器）
- 优先级队列的底层容器在内存中是连续的（默认是
vector）。
我怀疑重新平衡也比较慢，因为 RB-tree 依赖于节点（相对于 vector 的连续内存），这使得它容易出现缓存未命中，尽管必须记住堆上的操作没有完成以迭代的方式，它在向量中跳跃。我想真的有人必须对它进行分析。
以上几点对于插入和擦除都是正确的。我会说区别在于 big-O 表示法中丢失的常数因子。这是直觉。
对 map 较慢的抽象、高级解释是它做的更多。它始终保持整个结构排序。此功能是有代价的。如果您使用不对所有元素进行排序的数据结构，则无需支付该费用。
算法解释：
为了满足复杂性要求，map必须实现为基于节点的结构，而优先级队列可以实现为动态数组。 std::map 的实现是一个平衡的（通常是 red-black）树，而 std::priority_queue 是一个以 std::vector 作为默认底层容器的堆。
堆插入通常很快。与平衡树的 O(log n) 相比，插入堆的平均复杂度为 O(1)（尽管最坏情况相同）。创建 n 个元素的优先级队列的最坏情况复杂度为 O(n)，而创建平衡树为 O(n log n)。查看更多深度比较：Heap vs Binary Search Tree (BST)
另外，实现细节：
数组通常使用 CPU 缓存比树或列表等基于节点的结构更有效。这是因为数组的相邻元素在内存中相邻（高内存局部性），因此可能适合单个缓存行。然而，链接结构的节点存在于内存中的任意位置（低内存局部性），并且通常只有一个或很少的节点位于单个缓存行中。现代 CPUs 的计算速度非常非常快，但内存速度是一个瓶颈。这就是为什么基于数组的算法和数据结构往往比基于节点的算法和数据结构快得多。
虽然我同意@eerorika 和@luk32，但值得一提的是，在现实世界中，当使用默认的 STL 分配器时，内存管理成本很容易超过一些数据结构维护操作，例如更新指针到执行树旋转。根据实现，内存分配本身可能涉及树维护操作并可能触发系统调用，这将变得更加昂贵。
在 multi-map 中，内存分配和释放分别与每个 insert() 和 erase() 相关联，这通常比算法。
priority-queue 但是，默认情况下使用 vector ，一旦容量耗尽，它只会触发内存分配（虽然更广泛，涉及将所有存储的对象移动到新的内存位置） .在您的情况下，几乎所有分配仅发生在 priority-queue 的第一次迭代中，而 multi-map 一直在为每个 insert 和 erase.
可以通过使用基于内存池的自定义分配器来缓解 map 内存管理的缺点。这也为您提供了与优先级队列相当的缓存命中率。当您的对象很容易移动或复制时，它的性能甚至可能优于 priority-queue。