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

发布时间：2020-12-16 10:05:11 所属栏目：百科来源：网络整理

导读：我实现了一个算法,我使用优先级队列. 我被这个问题所激励： Transform a std::multimap into std::priority_queue 我将以其特定的优先级值存储多达1000万个元素. 然后我想迭代直到队列为空. 每次检索元素时,它也会从队列中删除. 在此之后,我重新计算元素prir

我实现了一个算法,我使用优先级队列.
我被这个问题所激励：
Transform a std::multimap into std::priority_queue

我将以其特定的优先级值存储多达1000万个元素.

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

在此之后,我重新计算元素pririty值,因为之前的迭代它可以改变.

如果值确实增加,我将元素againg插入队列.
这通常取决于进展. (在前25％它没有发生,在接下来的50％它确实发生,在过去的25％它将发生多次).

收到下一个元素而不重新插入后,我将处理它.这对于我不需要此元素的优先级值,而是此元素的技术ID.

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

在阅读上面的链接之后,我使用优先级队列类比重新实现了链接中的另一个问题.
我的运行时间似乎不是那么不平等(大约一个小时就有10个mio元素).
现在我想知道为什么std :: priority_queue会更快.

实际上,由于许多重新插入,我希望更快地成为std :: multimap.
也许问题是多图的重组太多了？

解决方法

总结一下：您的运行时配置文件涉及从抽象优先级队列中删除和插入元素,同时尝试使用std :: priority_queue和std :: multimap作为实际实现.

插入优先级队列和多重映射都具有大致相同的复杂性：对数.

但是,从多图表中删除下一个元素与优先级队列之间存在很大差异.使用优先级队列,这将是一个持续复杂的操作.底层容器是一个向量,你要从向量中移除最后一个元素,这将主要是一个无汉堡.

但是使用multimap,您将从多图的一个极端中删除该元素.

多图的典型底层实现是平衡的红/黑树.从多图的一个极端重复元素移除很有可能使树偏斜,需要频繁地重新平衡整个树.这将是一项昂贵的操作.

这可能是您看到明显的性能差异的原因.

（编辑：李大同）

【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!