位置: 编程技术 - 正文

使用堆实现Top K算法(JS实现)(堆实现栈)

编辑:rootadmin

推荐整理分享使用堆实现Top K算法(JS实现)(堆实现栈),希望有所帮助,仅作参考,欢迎阅读内容。

文章相关热门搜索词:使用堆运算可以动态建立或删除对象,使用堆排序方法排序,堆的操作pta,使用堆运算可以动态建立或删除对象,堆的操作pta,用堆的数组表示法,使用堆排序对下面的列表排序,使用堆栈的例子,使用堆运算可以动态建立或删除对象,内容如对您有帮助,希望把文章链接给更多的朋友!

先来聊一聊Top K算法,具体内容如下

应用场景:

搜索引擎会通过日志文件把用户每次检索使用的所有检索串都记录下来,每个查询串的长度为1-字节。 假设目前有一千万个记录(这些查询串的重复度比较高,虽然总数是1千万,但如果除去重复后,不超过3百万个。一个查询串的重复度越高,说明查询它的用户越多,也就是越热门。),请你统计最热门的个查询串,要求使用的内存不能超过1G。

必备知识:什么是哈希表? 哈希表(Hash table,也叫散列表),是根据关键码值(Key value)而直接进行访问的数据结构。

也就是说,它通过把关键码值映射到表中一个位置来访问记录,以加快查找的速度。这个映射函数叫做散列函数,存放记录的数组叫做散列表。

哈希表的做法其实很简单,就是把Key通过一个固定的算法函数既所谓的哈希函数转换成一个整型数字,然后就将该数字对数组长度进行取余,取余结果就当作数组的下标,将value存储在以该数字为下标的数组空间里。 而当使用哈希表进行查询的时候,就是再次使用哈希函数将key转换为对应的数组下标,并定位到该空间获取value,如此一来,就可以充分利用到数组的定位性能进行数据定位。问题解析:

要统计最热门查询,首先就是要统计每个Query出现的次数,然后根据统计结果,找出Top 。所以我们可以基于这个思路分两步来设计该算法。

即,此问题的解决分为以下俩个步骤:

第一步:Query统计 (统计出每个Query出现的次数)Query统计有以下俩个方法,可供选择: 1)、直接排序法 (经常在日志文件中统计时,使用cat file|format key|sort | uniq -c | sort -nr | head -n ,就是这种方法)首先我们最先想到的的算法就是排序了,首先对这个日志里面的所有Query都进行排序,然后再遍历排好序的Query,统计每个Query出现的次数了。

但是题目中有明确要求,那就是内存不能超过1G,一千万条记录,每条记录是Byte,很显然要占据2.G内存,这个条件就不满足要求了。

让我们回忆一下数据结构课程上的内容,当数据量比较大而且内存无法装下的时候,我们可以采用外排序的方法来进行排序,这里我们可以采用归并排序,因为归并排序有一个比较好的时间复杂度O(NlgN)。

排完序之后我们再对已经有序的Query文件进行遍历,统计每个Query出现的次数,再次写入文件中。

综合分析一下,排序的时间复杂度是O(NlgN),而遍历的时间复杂度是O(N),因此该算法的总体时间复杂度就是O(N+NlgN)=O(NlgN)。

2)、Hash Table法 (这种方法统计字符串出现的次数非常好) 在第1个方法中,我们采用了排序的办法来统计每个Query出现的次数,时间复杂度是NlgN,那么能不能有更好的方法来存储,而时间复杂度更低呢?

使用堆实现Top K算法(JS实现)(堆实现栈)

题目中说明了,虽然有一千万个Query,但是由于重复度比较高,因此事实上只有万的Query,每个Query Byte,因此我们可以考虑把他们都放进内存中去,而现在只是需要一个合适的数据结构,在这里,Hash Table绝对是我们优先的选择,因为Hash Table的查询速度非常的快,几乎是O(1)的时间复杂度。

那么,我们的算法就有了:

维护一个Key为Query字串,Value为该Query出现次数的HashTable,每次读取一个Query,如果该字串不在Table中,那么加入该字串,并且将Value值设为1;如果该字串在Table中,那么将该字串的计数加一即可。最终我们在O(N)的时间复杂度内完成了对该海量数据的处理。

本方法相比算法1:在时间复杂度上提高了一个数量级,为O(N),但不仅仅是时间复杂度上的优化,该方法只需要IO数据文件一次,而算法1的IO次数较多的,因此该算法2比算法1在工程上有更好的可操作性。

第二步:找出Top (找出出现次数最多的个)算法一:普通排序(我们只用找出top,所以全部排序有冗余) 我想对于排序算法大家都已经不陌生了,这里不在赘述,我们要注意的是排序算法的时间复杂度是NlgN,在本题目中,三百万条记录,用1G内存是可以存下的。

算法二:部分排序 题目要求是求出Top ,因此我们没有必要对所有的Query都进行排序,我们只需要维护一个个大小的数组,初始化放入个Query,按照每个Query的统计次数由大到小排序,然后遍历这万条记录,每读一条记录就和数组最后一个Query对比,如果小于这个Query,那么继续遍历,否则,将数组中最后一条数据淘汰(还是要放在合适的位置,保持有序),加入当前的Query。最后当所有的数据都遍历完毕之后,那么这个数组中的个Query便是我们要找的Top了。

不难分析出,这样,算法的最坏时间复杂度是N*K, 其中K是指top多少。

算法三:堆 在算法二中,我们已经将时间复杂度由NlogN优化到N*K,不得不说这是一个比较大的改进了,可是有没有更好的办法呢?

分析一下,在算法二中,每次比较完成之后,需要的操作复杂度都是K,因为要把元素插入到一个线性表之中,而且采用的是顺序比较。这里我们注意一下,该数组是有序的,一次我们每次查找的时候可以采用二分的方法查找,这样操作的复杂度就降到了logK,可是,随之而来的问题就是数据移动,因为移动数据次数增多了。不过,这个算法还是比算法二有了改进。

基于以上的分析,我们想想,有没有一种既能快速查找,又能快速移动元素的数据结构呢?

回答是肯定的,那就是堆。 借助堆结构,我们可以在log量级的时间内查找和调整/移动。因此到这里,我们的算法可以改进为这样,维护一个K(该题目中是)大小的小根堆,然后遍历万的Query,分别和根元素进行对比。

思想与上述算法二一致,只是在算法三,我们采用了最小堆这种数据结构代替数组,把查找目标元素的时间复杂度有O(K)降到了O(logK)。 那么这样,采用堆数据结构,算法三,最终的时间复杂度就降到了N*logK,和算法二相比,又有了比较大的改进。

至此,算法就完全结束了,经过上述第一步、先用Hash表统计每个Query出现的次数,O(N);然后第二步、采用堆数据结构找出Top ,N*O(logK)。所以,我们最终的时间复杂度是:O(N) + N'*O(logK)。(N为万,N'为万)。

js如何使用堆实现Top K 算法&#;

1. 使用堆算法实现Top,时间复杂度为 O(LogN)

2. 调用K次堆实现,时间复杂度为 O(K * LogN)

3.测试

标签: 堆实现栈

本文链接地址:https://www.jiuchutong.com/biancheng/385552.html 转载请保留说明!

上一篇:js操作cookie保存浏览记录的方法(js cookie存取)

下一篇:JavaScript如何实现在文本框(密码框)输入提示语(javascript怎么写)

  • 哪些准备金支出可实现税前扣除?
  • 预提所得税的计税基础
  • 印花税会计分录怎么做
  • 行政单位基建管理办法
  • 附加税减征额怎么做分录
  • 固定资产做错了怎么办
  • 宣传费税前扣除标准
  • 研发支出费用化支出包括哪些
  • 多缴所得税返还现金流
  • 建帐时库存的原材料如何入帐?
  • 企业承担个人所得税账务处理
  • 预警税负率表
  • 企业为员工购买的补充医疗保险
  • gdp等于消费加储蓄加税收
  • 核定征收取消了
  • 自然人扣缴系统怎么删除企业
  • 小规模免征增值税政策2022
  • 小规模纳税人免税额度是多少
  • 电脑开机黑屏没信号怎么回事
  • 预提开发成本超过10%部分计算的销售成本转回
  • 固定资产未开发票怎么入账
  • 开办费摊销从什么时候开始
  • 公司运输车辆加油会计分录
  • win10无法上网,显示灰色的飞行模式
  • 调制解调器报告了一个错误怎么弄
  • 交际应酬费可以抵扣吗
  • 特许权使用费属于无形资产吗
  • wordpress site
  • cocos creator脚本开发指南
  • 废旧物资回收经营单位
  • 股权投资企业收益怎么算
  • vue3使用高德地图
  • 地方各项基金费(工会经费)可以不申报吗
  • 前端解决跨域问题的代理
  • three.js 入门
  • 计提租金怎么做会计分录
  • 机动车销售统一专票
  • 小规模纳税人可以开专票吗
  • 其他资本公积如何转出
  • 全年一次性奖金单独计税还是并入
  • 免税农产品的范围有哪些
  • 公司出售房子怎么交税
  • 帝国cms使用手册
  • 教育类财务工作内容
  • 浅谈数据库优化设计
  • 委托加工应税消费品是指委托方提供原料和主要材料
  • 企业哪些进项税不能抵扣
  • 上月计提多了怎么办
  • 再保后赔款支出
  • 国际货运代理免增值税
  • 固定资产变动方式名称
  • 公司为小规模纳税人
  • 村集体经济组织的银行存款可以向外单位或个人出租出借
  • 购入研发设备可以抵扣吗
  • 建账内容
  • sqlserver按时间段导出数据
  • sql server中的权限包括哪三种类型
  • 双系统没有选择
  • linux操作系统主要学什么
  • win8系统如何
  • centos6 iptables配置
  • linux系统的服务器有哪些
  • win7无法安装怎么办
  • win7系统计算机管理打不开
  • 怎么更换win系统
  • 结构 类型
  • cocos2dx运行原理
  • shell的实现
  • linux生成网卡配置文件
  • csm support
  • startactivity()
  • python脚本代码大全
  • 关于Colloder事件
  • javascript数据结构与算法
  • 实现断点续传的工具软件
  • 税务局网上申请开票
  • 更改税务购票员
  • 种子公司缴税吗多少钱
  • 怎么查询手机发票
  • 潍坊市的职工医保多少钱
  • 免责声明:网站部分图片文字素材来源于网络,如有侵权,请及时告知,我们会第一时间删除,谢谢! 邮箱:opceo@qq.com

    鄂ICP备2023003026号

    网站地图: 企业信息 工商信息 财税知识 网络常识 编程技术

    友情链接: 武汉网站建设