大量数据中心找出高频词

如何从大量数据中心找出高频词


题目

有1GB大小的文件,文件里每一行是一个词,每个词的大小不超过16个字节,内存大小限制是1MB,要求返回词频最高的100个词

思路

由于文件大小1GB,而内存大小1MB,因此不可能一次把所有的词读到内存中进行处理,需要采用分之的思想,把一个大文件分解成多个小文件,从而保证每个文件大小都小于1MB,进而可以直接读取到内存进行处理。具体思路:
1)遍历文件,对遍历到的每一个词,执行hash操作:hash(x)%2000,将结果为i的词放到文件ai中。通过这个分解步骤,可以使每个文件大小约400kb,如果这个操作后某个文件大小超过了1MB,那么就采用相同的方法对这个文件继续分解。
2)统计出每个文件中频率最高的100个词。最简单的方法是使用HashMap来实现:遍历文件中的所有词,对于遍历到的词,如果hashmap中不存在,那么将这个词放入haspmap中(键为这个词,值为1),如已经存在,那么将这个词对应的值加1。可以找到每个文件中频率最高的100个词。
3)对第二步找到的每个文件出现频率最高的100个词,可以通过维护一个小顶堆来找出所有文件中出现频率最高的100个词。具体做法:遍历第一个文件,把第一个文件中出现频率最高的100个词构成一个小顶堆,继续遍历,如果遍历到的词频率大于顶堆上出现的频率,则用遍历到的词替换顶堆上的词,然后调整这个小顶堆。遍历完所有文件,小顶堆中的词即为出现频率最高的100个词。

全部评论

相关推荐

07-22 11:12
门头沟学院 Java
不是,我就随手投的怎么还真发面试啊
皮格吉:大厂特别快的——来自已经被共享中
点赞 评论 收藏
分享
点赞 评论 收藏
分享
评论
1
1
分享

创作者周榜

更多
牛客网
牛客网在线编程
牛客网题解
牛客企业服务