海量数据统计topK
有一个1G大小的一个文件，里面每一行是一个词，词的大小不超过16字节，内存限制大小是1M。返回频数最高的100个词。
思路：
把这1G的数据一次性全部读入内存是不可能了，可以每次读一行，然后将该词存到一个哈希表里去，哈希表的value是词出现的次数。
现在的问题是，这个哈希表有多大，能不能装载1M的内存中去。
假设这1G文件里每个词都不一样，那么最多有不同的1G/1Byte = 1G个词，一个哈希表的节点中包含了单词(key)，频率(value),next指针，则内存至少要24bytes * 1G，这显然大大超了。不过如果题目告诉我们顶多有一百万个不同的词，那么 24bytes*1M=24M，对于大多数的机器，这个哈希表是可以建立的，当然此题内存只有1M，连24M的哈希表都装不下。
因此我们的第一步是将所有的词分到不同的文件中去，相同的词要分到相同的文件中去。这样文件的规模小了，建立的哈希表也就小了。
将单词的哈希值对5000取模，根据结果将单词分配到5000个文件中去。这样，平均情况下，一个文件中有1G/5000 = 0.2M个词，哈希表基本上能装得下了。
对每个文件进行hashmap统计，将词与频率写到一个新的文件中，得到5000个新文件。
维护一个100个节点的最小堆，依次读5000个文件中的每一条记录。如果频率小于堆顶，证明该词比堆里的100个单词频率都低，不可能进top100，舍弃。如果频率大于堆顶，就将该词至于堆顶，然后调用维护函数，维护最小堆的性质。所有的记录遍历完了，最小堆中的单词就是结果。
总结：
哈希表的大小不是根据单词的数量，而是根据不同单词的数量。
最大的topK用最小堆，最小的topK用最大堆。
算法的时间复杂度：
分小文件 O(n)
hashmap统计 O(n)
维护最小堆 O(n'logK) n'是不同的单词数，K是topK
最新文章
- 曲演杂坛--当ROW_NUMBER遇到TOP
- 脚本tips
- 通过 Redis 实现 RPC 远程方法调用(支持多种编程语
- php分享（三十六）mysql中关联表更新
- 最新Velocity使用和Velocity语法
- c# 相对路径的一些资料
- linux里添加locate命令
- php--如何解决网站分页导致的SEO问题
- 【浏览器渲染原理】渲染树构建之渲染树和DOM树的关系（转载 学习中。。。）
- 数组包含字典-根据key排序
- CSS3实现jquery的特效
- CDN库地址搜集2
- Excel 2010高级应用-折线图（二）
- 【Unity3D与23种设计模式】单例模式（Singleton）
- spring boot正常启动但是访问会找不到“ localhost 的网页”的错误
- OpenCV3计算机视觉Python语言实现笔记（二）
- Java Web 域名
- Android Glide 源码分析系列（待完成）
- 测试那些事儿—selenium自动化实战之登录验证码处理
- vue插件开发实践与要点