免费注册 查看新帖 |

Chinaunix

  平台 论坛 博客 文库
最近访问板块 发新帖
查看: 1950 | 回复: 7

[算法] STL priority_queue与multiset [复制链接]

论坛徽章:
0
发表于 2014-09-18 15:43 |显示全部楼层
5可用积分
想用优先级队列,应用场景为:有大量的数据会进入到队列中等待后续操作,这时候来了高优先级的数据,要能插对到最前面
数据基本元素为Class,在比较函数中增加了计数器
priority_queue:这个就叫优先级队列,但是测试发现,采用vector<Class>时,入队执行的Class之间的比较操作非常多,非常耗时,出队也是一样问题。
multiset,入队的比较操作还好,大概平均入队一个,比较30次的样子,出队只取最大的元素,不会执行任何比较操作
想问下:
1、我这个场景,还有没其他的数据结构可供选择?
2、priority_queue应用场景在哪?感觉数据几千就非常慢了

最佳答案

查看完整内容

这得看具体库的实现,要不你试试 deque

论坛徽章:
14
巨蟹座
日期:2013-11-19 14:09:4615-16赛季CBA联赛之青岛
日期:2016-07-05 12:36:0515-16赛季CBA联赛之广东
日期:2016-06-29 11:45:542015亚冠之全北现代
日期:2015-07-22 08:09:472015年辞旧岁徽章
日期:2015-03-03 16:54:15巨蟹座
日期:2014-12-29 08:22:29射手座
日期:2014-12-05 08:20:39狮子座
日期:2014-11-05 12:33:52寅虎
日期:2014-08-13 09:01:31巳蛇
日期:2014-06-16 16:29:52技术图书徽章
日期:2014-04-15 08:44:01天蝎座
日期:2014-03-11 13:06:45
发表于 2014-09-18 15:43 |显示全部楼层
这得看具体库的实现,要不你试试 deque

论坛徽章:
0
发表于 2014-09-18 16:12 |显示全部楼层
试了,也是一样问题。我是用VS2008测试的
因为基本元素是类,比较在意比较操作的次数。
bruceteen 发表于 2014-09-18 16:09
这得看具体库的实现,要不你试试 deque

论坛徽章:
4
水瓶座
日期:2013-09-06 12:27:30摩羯座
日期:2013-09-28 14:07:46处女座
日期:2013-10-24 14:25:01酉鸡
日期:2014-04-07 11:54:15
发表于 2014-09-18 16:15 |显示全部楼层
priority_queue是堆, 问题就是不支持随机查找删除.

论坛徽章:
0
发表于 2014-09-18 16:33 |显示全部楼层
我的场景不会用到随机查询
刚测试了下压入10w数据,multiset:
初始化数据耗时毫秒:1408
总共执行了2821561次比较操作
priority_queue<Node,vector<Node>,cmp> 10w数据没出来,改为1万:
初始化数据耗时毫秒:25746
总共执行了50004816次比较操作
linux_c_py_php 发表于 2014-09-18 16:15
priority_queue是堆, 问题就是不支持随机查找删除.

论坛徽章:
0
发表于 2014-09-18 16:47 |显示全部楼层
建议用multiset,存储指针类型的数据(避免无意义的拷贝构造),然后自定义比较函数。仔细测试一下到底是不是比较很耗时。

论坛徽章:
0
发表于 2014-09-18 17:01 |显示全部楼层
各位,刚刚到Unix下测试了下,priority_queue速度很快,跟multiset没明显差异
难道被微软的实现坑到了? 回复 1# 2009从-1开始


   
您需要登录后才可以回帖 登录 | 注册

本版积分规则 发表回复

SACC2019中国系统架构师大会

【数字转型 架构演进】SACC2019中国系统架构师大会,8.5折限时优惠重磅来袭!
2019年10月31日~11月2日第11届中国系统架构师大会(SACC2019)将在北京隆重召开。四大主线并行的演讲模式,1个主会场、20个技术专场、超千人参与的会议规模,100+来自互联网、金融、制造业、电商等领域的嘉宾阵容,将为广大参会者提供一场最具价值的技术交流盛会。

限时8.5折扣期:2019年9月30日前


----------------------------------------

大会官网>>
  

北京盛拓优讯信息技术有限公司. 版权所有 16024965号-6 北京市公安局海淀分局网监中心备案编号:11010802020122
中国互联网协会会员  联系我们:huangweiwei@it168.com
感谢所有关心和支持过ChinaUnix的朋友们 转载本站内容请注明原作者名及出处

清除 Cookies - ChinaUnix - Archiver - WAP - TOP