在大数据时代,处理超大规模数据是算法工程师需要面对的重要问题。本文将以在内存受限环境下,求一个大文件中词频最高的Top N词为例,探讨一种基于堆结构与外部排序的解决方案。...问题描述
给定一个1G大小的文件file.txt,里面每行是一个词,词的大小不超过16字节。内存限制为1M。要求返回文件中词频最高的100个词。...常规方法及不足
最简单的方法是将文件全部读入内存,统计每个词的频数,最后取频数最大的100个词。但文件大小远超内存限制,无法操作。
一种改进是分批读入文件,每次统计一批词频,最后合并结果。...每次从文件中读取一定大小的词,统计词频保存到一个哈希表中。然后遍历这个哈希表,把词频作为值,词语作为键,逐个插入小根堆。如果堆大小超过N,则移除堆顶最小的元素。...逐批从文件中读取一定行数的词,统计到哈希表F中
遍历F,将词频作为值,词语作为键,插入小根堆
堆大小超过N,则移除堆顶最小元素
重复步骤2-4,直到文件读完
堆中的N个元素即为全局topk结果