大量数据中心找出高频词
如何从大量数据中心找出高频词
题目
有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个词。