同步操作将从 林炯潮/advanced-java 强制同步,此操作会覆盖自 Fork 仓库以来所做的任何修改,且无法恢复!!!
确定后同步将在后台操作,完成时将刷新页面,请耐心等待。
有一个 1GB 大小的文件,文件里每一行是一个词,每个词的大小不超过 16B,内存大小限制是 1MB,要求返回频数最高的 100 个词(Top 100)。
由于内存限制,我们依然无法直接将大文件的所有词一次读到内存中。因此,同样可以采用分治策略,把一个大文件分解成多个小文件,保证每个文件的大小小于 1MB,进而直接将单个小文件读取到内存中进行处理。
思路如下:
首先遍历大文件,对遍历到的每个词 x,执行 hash(x) % 5000
,将结果为 i 的词存放到文件 ai 中。遍历结束后,我们可以得到 5000 个小文件。每个小文件的大小为 200KB 左右。如果有的小文件大小仍然超过 1MB,则采用同样的方式继续进行分解。
接着统计每个小文件中出现频数最高的 100 个词。最简单的方式是使用 HashMap 来实现。其中 key 为词,value 为该词出现的频率。具体方法是:对于遍历到的词 x,如果在 map 中不存在,则执行 map.put(x, 1)
;若存在,则执行 map.put(x, map.get(x)+1)
,将该词频数加 1。
上面我们统计了每个小文件单词出现的频数。接下来,我们可以通过维护一个小顶堆来找出所有词中出现频数最高的 100 个。具体方法是:依次遍历每个小文件,构建一个小顶堆,堆大小为 100。如果遍历到的词的出现次数大于堆顶词的出现次数,则用新词替换堆顶的词,然后重新调整为小顶堆,遍历结束后,小顶堆上的词就是出现频数最高的 100 个词。
此处可能存在不合适展示的内容,页面不予展示。您可通过相关编辑功能自查并修改。
如您确认内容无涉及 不当用语 / 纯广告导流 / 暴力 / 低俗色情 / 侵权 / 盗版 / 虚假 / 无价值内容或违法国家有关法律法规的内容,可点击提交进行申诉,我们将尽快为您处理。