位置: 编程技术 - 正文

使用堆实现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怎么写)

  • 补缴以前年度附加税如何入账
  • 可供出售金融资产和长期股权投资
  • 公司没有收入怎么报销
  • 购买方已抵扣怎么作废
  • 保本理财收益计入什么科目
  • 一般纳税人收入会计分录
  • 建筑工程免税项目
  • 企业所得税纳税人包括哪些类型
  • 单位和职工个人缴费基数如何确定的规定
  • 小企业无形资产取得的账务处理
  • 公司按揭购车可以抵扣税吗
  • 风险溢价包括哪些违约风险溢价 流动性风险溢价
  • 税控盘上开完发票发的邮件在哪查看
  • 劳务公司差额征税怎么计算
  • 发票选择确认平台怎么选
  • 企业员工用自己手机发送工作
  • 小规模未开票收入如何申报增值税
  • 进口增值税内销可以抵扣吗
  • 在建工程暂估转固定资产
  • dell笔记本如何恢复系统
  • 一寸照片尺寸是几乘几
  • Google Bard VS ChatGPT:哪个是更好的AI聊天机器人?
  • 软件充值怎么申请退款
  • 公司转账到支付宝有记录么
  • 个人所得税投诉电话是多少
  • PHP:mb_convert_variables()的用法_mbstring函数
  • 银行存款总账怎么登记图片
  • 支出的科目有哪些
  • php和aspnet哪个好
  • 收到的税费返还减少说明什么
  • 其他综合收益的构成项目如何
  • 尚硅谷docker笔记
  • 用python处理图像
  • php判断时间区间
  • 商业企业常用会计科目
  • 适用于windows7的更新程序会更新到windows10吗
  • ps2021和cs6有什么区别
  • 员工离职补偿怎么入账
  • 电影院是否征收文化建设事业费
  • 预先支付的房租
  • 电子商业汇票业务
  • 个人所得税纳税记录怎么查询
  • 技术研发费用包括哪些
  • sql优化常用的15种方法
  • 公司向个人支付居间费用
  • 进项税通俗易懂
  • 未确认融资费用怎么算
  • 信用减值损失在贷方表示什么
  • 兼职人员工资需要交个税吗
  • 小规模纳税人专票开1%还是3%
  • 筹建期间业务招待费的财税处理规定
  • 应税污染物的计算公式
  • 年底进项比销项大要做账么
  • 政府拆迁赔款会计上怎样做账
  • 预计产品质量保证损失计入什么
  • 现金付给对方没写收据怎么办
  • 可供出售金融资产和交易性金融资产
  • 外购货物用于在建工程分录
  • 企业中征码怎么生成
  • 月末都应该计提哪些税费
  • winXP系统截图
  • win7自带xp虚拟机怎么安装驱动
  • WINDOWS系统中删除放入回收站的文件占用什么空间
  • linux中,什么命令可以控制口令的存活时间?
  • win7系统怎么给C盘扩容
  • xp系统无线网络连接怎么没有
  • g++.exe error
  • Win10 Mobile 10586.312提前体验
  • win7系统电脑无声音
  • ajax 编码
  • 模拟监控app
  • cocos 3.x android下home键后,切回游戏时黑屏太久的问题
  • 数据结构分析时间复杂度
  • vbs运行cmd命令
  • javascript总结笔记
  • 学习JavaScript事件流和事件处理程序
  • 顺丰收取关税合理吗
  • 广东省地方税务局电子办税服务厅
  • a级纳税人和一级的区别
  • 云开票怎么报税
  • 免责声明:网站部分图片文字素材来源于网络,如有侵权,请及时告知,我们会第一时间删除,谢谢! 邮箱:opceo@qq.com

    鄂ICP备2023003026号

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

    友情链接: 武汉网站建设