免费注册 查看新帖 |

Chinaunix

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

[算法] 统计单词的访问频度,我觉得散列表比Trie树快啊 [复制链接]

论坛徽章:
2
2015年迎新春徽章
日期:2015-03-04 10:16:532015元宵节徽章
日期:2015-03-06 15:53:22
发表于 2017-10-11 00:40 |显示全部楼层
Trie树的介绍一般都会带一句说:寻找热门查询,300万个查询字符串中统计最热门的10个查询,可以用trie树

但是我感觉,用散列表,类似C++的unordered_map,每个单词进来,计算一次散列值,value+1就行了。
如果用trie树实现,那么每次查找都要经过若干个节点的跳转和比较,这个比计算一次hash要重多了。

为什么说,“”寻找热门查询,300万个查询字符串中统计最热门的10个查询”这样的问题更适合于用trie树呢?
求解释。

论坛徽章:
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
发表于 2017-10-11 08:31 |显示全部楼层
为什么总有人觉得hash快?遇到 hash冲突、二次冲突(取决于实现)、容量不足 等问题时特别耗时。
而 trie 嘛,我觉得缺点也大,第一它限定了字符(如果只考虑26个字母还行,如果是unicode,那只能分解成字节考虑了),第二是效率,它内存结构松散(类似于list),内存页面切换比较耗时。
以上皆废话,你为什么不写两段代码实际测量一下耗时?

论坛徽章:
14
水瓶座
日期:2014-06-10 09:51:0215-16赛季CBA联赛之江苏
日期:2017-11-27 11:42:3515-16赛季CBA联赛之八一
日期:2017-04-12 14:26:2815-16赛季CBA联赛之吉林
日期:2016-08-20 10:43:1215-16赛季CBA联赛之广夏
日期:2016-06-23 09:53:58程序设计版块每日发帖之星
日期:2016-02-11 06:20:00程序设计版块每日发帖之星
日期:2016-02-09 06:20:0015-16赛季CBA联赛之上海
日期:2015-12-25 16:40:3515-16赛季CBA联赛之广夏
日期:2015-12-22 09:39:36程序设计版块每日发帖之星
日期:2015-08-24 06:20:002015亚冠之德黑兰石油
日期:2015-08-07 09:57:302015年辞旧岁徽章
日期:2015-03-03 16:54:15
发表于 2017-10-11 10:56 |显示全部楼层
回复 1# cdsfiui

Trie比Hash更节约内存,但是如果都是要查找Top10,我觉得不额外维护个Heap貌似都不会快,Hash和Trie都没有Rank的概念
@windoze 猫大来答一发

论坛徽章:
136
2022北京冬奥会纪念版徽章
日期:2015-08-07 17:10:5719周年集字徽章-庆
日期:2019-08-27 13:28:5615-16赛季CBA联赛之福建
日期:2019-09-10 11:43:25
发表于 2017-10-11 11:56 来自手机 |显示全部楼层
hash本质是一个内存池,大数组

论坛徽章:
43
15-16赛季CBA联赛之四川
日期:2018-10-13 23:26:5015-16赛季CBA联赛之新疆
日期:2016-04-25 10:55:452016科比退役纪念章
日期:2016-04-23 00:51:2315-16赛季CBA联赛之山东
日期:2016-04-17 12:00:2815-16赛季CBA联赛之福建
日期:2016-04-12 15:21:2915-16赛季CBA联赛之辽宁
日期:2016-03-24 21:38:2715-16赛季CBA联赛之福建
日期:2016-03-18 12:13:4015-16赛季CBA联赛之佛山
日期:2016-02-05 00:55:2015-16赛季CBA联赛之佛山
日期:2016-02-04 21:11:36程序设计版块每日发帖之星
日期:2016-07-02 06:20:0015-16赛季CBA联赛之天津
日期:2016-11-02 00:33:1215-16赛季CBA联赛之浙江
日期:2017-01-13 01:31:49
发表于 2017-10-11 14:22 |显示全部楼层
Hash和Trie没有顺序啊?你要找top 10的话它们能帮你干什么呢?你总归得有一个ordered数据结构才能找top N不是,要不然你得把所有entry都遍历一遍才知道哪个是top。
对于找top N这种活,heap貌似是最省的,如果你真的特别在乎log N的话试试斐波那契堆吧。
再说你可以一边heap一边hash/trie,这两个东西又不会打架。

论坛徽章:
36
子鼠
日期:2013-08-28 22:23:29黄金圣斗士
日期:2015-12-01 11:37:51程序设计版块每日发帖之星
日期:2015-12-14 06:20:00CU十四周年纪念徽章
日期:2015-12-22 16:50:40IT运维版块每日发帖之星
日期:2016-01-25 06:20:0015-16赛季CBA联赛之深圳
日期:2016-01-27 10:31:172016猴年福章徽章
日期:2016-02-18 15:30:3415-16赛季CBA联赛之福建
日期:2016-04-07 11:25:2215-16赛季CBA联赛之青岛
日期:2016-04-29 18:02:5915-16赛季CBA联赛之北控
日期:2016-06-20 17:38:50技术图书徽章
日期:2016-07-19 13:54:03程序设计版块每日发帖之星
日期:2016-08-21 06:20:00
发表于 2017-10-11 22:54 |显示全部楼层
关键不是这个。
关键是输入不是单个key,比如关键字 "abc",但输入的是 "xxabcde",trie包含了从"xxabcde"中找出abc的过程,map没有这个过程

论坛徽章:
36
子鼠
日期:2013-08-28 22:23:29黄金圣斗士
日期:2015-12-01 11:37:51程序设计版块每日发帖之星
日期:2015-12-14 06:20:00CU十四周年纪念徽章
日期:2015-12-22 16:50:40IT运维版块每日发帖之星
日期:2016-01-25 06:20:0015-16赛季CBA联赛之深圳
日期:2016-01-27 10:31:172016猴年福章徽章
日期:2016-02-18 15:30:3415-16赛季CBA联赛之福建
日期:2016-04-07 11:25:2215-16赛季CBA联赛之青岛
日期:2016-04-29 18:02:5915-16赛季CBA联赛之北控
日期:2016-06-20 17:38:50技术图书徽章
日期:2016-07-19 13:54:03程序设计版块每日发帖之星
日期:2016-08-21 06:20:00
发表于 2017-10-11 22:56 |显示全部楼层
常见的场景是敏感词过滤,用trie是为了找出一个字符串中的所有敏感词
您需要登录后才可以回帖 登录 | 注册

本版积分规则 发表回复

SACC2019中国系统架构师大会

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




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

大会官网>>
  

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

清除 Cookies - ChinaUnix - Archiver - WAP - TOP