“数据量大于内存”这个前提做TopK不稀奇但要你手写、不用现成框架还要同时保证内存稳定、性能过关就值得好好拆一遍了。很多朋友一听到“海量数据”就想去上外部排序、上分布式其实大多数场景下的最优解就是一个自己手搓的小顶堆。这篇文章我就把这套东西彻底讲明白从题目怎么拆到堆为什么是主角再到完整代码实现、踩坑记录和进阶优化全部放在一篇里。1. 先把问题拆明白“数据量大于内存”到底难在哪1.1 TopK到底在求什么TopK的本质很简单在一堆数据里找出最大的K个或最小的K个。比如一份上千万条的日志里找访问量前100的IP或者一个大表里找评分最高的50个商品。它和“全排序”最大的区别是我们根本不需要知道其他元素的精确顺序因此也就没必要把所有数据都排好序。这里有一个很容易被忽略的点TopK的结果通常不要求有序。最常见的场景只要“前K个集合”至于这K个内部谁大谁小往往是等返回之后再排一下或者根本不需要。理解这一点后你会发现很多看似复杂的方案其实都是白折腾的。1.2 “数据量大于内存”真正难在哪很多人看到“数据量大于内存”第一反应是“内存装不下得把数据拆开落盘”。这个理解本身没有错但容易把问题带偏。真正的难点不在“存不下全部数据”而在于你必须在不需要完整数据的前提下用稳定的内存得到结果。举个很直观的例子一个100G的文件要取Top100如果你只会readAllLines再排序那程序在启动时就已经挂了因为压根装不下。但如果换一个思路我们维护一个大小为100的小顶堆从文件第一行开始一条条往堆里塞堆里始终只留“目前见过的最大的100个”。整个过程中内存只存了100个元素文件再大都无所谓。这就是“流式处理”的感觉也是TopK这类问题能扛住超大数据的根本原因。所以数据量大于内存的真正挑战分两层第一层是内存上的挑战要求算法空间复杂度不随数据总量膨胀最好是O(K)第二层是IO上的挑战文件这么大怎么读得快、怎么减少解析开销经常比算法本身更容易成为性能瓶颈。再往下拆还有一个隐形的决策点K本身大不大如果K只有100堆方案无脑最佳如果K是几百万甚至更大那堆的规模和比较次数都会上涨这时候可能就要考虑分块、外部排序这类更重的方案了。这个问题我放到下一节细讲。2. 两条技术路线怎么选小顶堆与外部归并2.1 为什么求最大TopK偏偏要用小顶堆这是整个题目里最反直觉、也最常被面试官追问的一个点。很多人的第一反应是求最大的TopK当然要用大顶堆把最大的放堆顶。但仔细想一下大顶堆存下所有见过的数据才能找出最大值那内存就不是O(K)了而是O(N)直接违背“数据量大于内存”的约束。正确做法是用小顶堆。堆顶永远是堆里最小的元素它充当一个“门槛”。新来一个元素如果比门槛大就说明它值得留在结果里于是替换掉门槛再重新调整堆如果比门槛小说明它进不了前K直接丢弃。每次操作只需要和堆顶比较堆的规模始终只有K个元素。用一个生活化的类比小顶堆就像K个座位的VIP区门槛是VIP区里综合实力最弱的那个人。新来的人如果能打败最弱的那个人就可以把最弱的人挤出去自己坐进去如果连最弱都打不过那确实没资格进VIP区。全程不需要关心VIP区外面那些已经被淘汰的人。为什么不用“先全部加载到数组里排序取前K”因为那要求O(N log N)时间和O(N)空间在大数据量下既不聪明也不可持续。为什么不用“维护一个长度为K的链表/数组直接插排”因为插入和移动代价高最坏情况下O(NK)数据一多就慢到怀疑人生。堆结构把插入和替换都压缩到O(log K)这才是它的价值。2.2 什么时候该上外部归并堆方案几乎是无脑首选但它有两个弱点K很大时比如K 5000万堆本身的内存就不是小数目而且每次调整的log K成本也随之上升如果后续还要求“这K个元素本身也是有序的”或者“我想知道第K1、K2名的近似值”单靠堆就不够直接了。这时候可以考虑分块外部排序 多路归并。思路很简单把大文件切成很多块每块大小控制在内存能容纳的范围内对每一块在内存里排好序写回临时文件用一个多路归并把所有临时文件合并成一个全局有序的大序列排到“剩下最后K个元素”时这K个就是全局TopK。这个方案的优点是可以处理超大K还能顺便拿到有序结果缺点是IO开销大要多次写临时文件程序复杂度也上了一个台阶。一般只在K达到堆容量上限、或者业务确实需要全局有序输出时才用它。这里再提一个“分片秤重”的思路如果数据分布在很多台机器上可以先让每台机器在本地用堆求出TopK再把所有机器的TopK汇总到一台机器上做一次合并。这个做法是精确的不是近似。原因很简单全局前K名中的任意一个元素如果不在某台机器的本地TopK里那说明在这台机器上至少有K个元素比它大而这个“至少K个”会直接推算出它在全局的排名一定在K之后矛盾。所以本地TopK合并全局TopK不会漏。2.3 选型决策一览场景特点推荐方案大部分常规场景K 百万量级小顶堆流式扫描数据到达方式是流式、无法全部落盘小顶堆天然适合K非常大堆内存吃紧分块排序 多路归并要求输出顺序、知道完整的边界名次外部归并取全局有序序列数据分布在多台机器每机堆求TopK汇总合并只需要近似TopK允许少许误差抽样估算阈值二次过滤选型的原则很简单能用堆就用堆堆解决不了再上重武器。我见过不少项目一上来说要搭一套分布式方案最后数据量其实一台普通机器加上堆算法轻松能跑完纯粹是过度设计了。3. 手写实现从造数到出结果这一节直接上代码。语言我用Java逻辑同样可以照搬到C、Go或者Python。手写的重点在于自己实现二叉堆而不是用现成的优先队列类库这样才能理解siftUp和siftDown这两个核心动作。3.1 先造一个数据量大于内存的测试文件没有测试数据讨论优化都是空谈。我习惯先造一个文本文件每行一个整数模拟“一条记录”。比如生成1000万条数据普通笔记本上大概90MB对内存模拟已经足够有说服力了如果你机器内存不大可以把总量改小一点逻辑不变。import java.io.BufferedWriter; import java.io.IOException; import java.nio.file.Files; import java.nio.file.Path; import java.util.Random; public class GenData { public static void main(String[] args) throws IOException { int total 10_000_000; int bound 100_000_000; Random random new Random(42); try (BufferedWriter writer Files.newBufferedWriter(Path.of(data.txt))) { for (int i 0; i total; i) { writer.write(Integer.toString(random.nextInt(bound))); writer.newLine(); } } } }这里把随机种子固定为42方便复现和对比。造数据时有一点需要注意如果数值范围太小、重复度太高堆顶会被频繁替换测试结果会与真实场景偏差较大所以我把范围设为1亿。3.2 手写小顶堆的核心实现堆的本质是一个完全二叉树用数组存储就行。关键操作只有两个新元素从底部加入时往上浮siftUp替换堆顶后往下降siftDown。我写代码时习惯把这两个方法直接放在TopK类内部避免重复传参。import java.util.Arrays; public class TopK { private final int k; private final int[] heap; private int size 0; public TopK(int k) { this.k k; this.heap new int[k]; } public void add(int value) { if (size k) { // 堆还没满直接放末尾然后上浮 heap[size] value; siftUp(size); size; } else if (value heap[0]) { // 堆满了且新元素大于堆顶当前门槛 heap[0] value; siftDown(0); } // 其他情况value 堆顶直接丢弃 } private void siftUp(int index) { while (index 0) { int parent (index - 1) / 2; if (heap[index] heap[parent]) { break; } swap(index, parent); index parent; } } private void siftDown(int index) { int n size; while (true) { int left 2 * index 1; int right 2 * index 2; int smallest index; if (left n heap[left] heap[smallest]) { smallest left; } if (right n heap[right] heap[smallest]) { smallest right; } if (smallest index) { break; } swap(index, smallest); index smallest; } } private void swap(int i, int j) { int tmp heap[i]; heap[i] heap[j]; heap[j] tmp; } public int[] result() { int[] copy Arrays.copyOf(heap, size); Arrays.sort(copy); return copy; } }有几个细节值得多说一句siftDown里的比较和交换不要用递归。虽然递归写的代码更短但堆深度是logK递归调用在K大的时候会产生不必要的栈压力写成循环更好。相等情况的处理value heap[0]这个条件用严格大于。如果新元素和堆顶相等替换没有意义跳过反而减少一次下沉开销。最后排序堆内部的顺序只是堆序不是严格有序的所以result()里先复制出一个数组再做一次排序。如果业务上只要“前K个集合”也可以跳过这步直接返回堆里的原始数组。3.3 流式扫描主流程有了堆结构主流程就非常简单不断从文件读数据一条条递给add()。为了减少IO次数我用了一个小技巧每读满一批数据再批量灌进堆而不是读一条就处理一条。这样可以降低方法调用和对象构造的开销。import java.io.BufferedReader; import java.io.IOException; import java.nio.file.Files; import java.nio.file.Path; import java.util.ArrayList; import java.util.List; public class TopKRunner { public static void main(String[] args) throws IOException { int k 100; TopK topK new TopK(k); int batchSize 100_000; ListInteger batch new ArrayList(batchSize); try (BufferedReader reader Files.newBufferedReader(Path.of(data.txt))) { String line; while ((line reader.readLine()) ! null) { batch.add(Integer.parseInt(line.trim())); if (batch.size() batchSize) { for (int value : batch) { topK.add(value); } batch.clear(); } } } // 处理末尾不足一批的数据 for (int value : batch) { topK.add(value); } int[] result topK.result(); for (int i result.length - 1; i 0; i--) { System.out.println(result[i]); } } }这个主流程看起来平平无奇但已经解决了“数据量大于内存”的核心问题文件不是一次性读入而是按行流式读取堆里最多只有K个int内存不随文件大小增长批处理只是优化IO不影响正确性。如果你要追求极致性能可以把解析操作也优化一下Integer.parseInt(line.trim())里包含了很多字符串处理换成手写的ASCII转int可以减少一部分开销。另一个思路是把数据从文本改成二进制定长存储一个int占4字节1000万条数据约40MB读起来更快解析也更简单。这个方案在实际工程里很常见。3.4 内存占用和时间复杂度估算很多人问数据量100G这个程序真的不炸吗我们直接算一笔账堆数组K100时就是100个int占400字节几乎可以忽略不计批处理链表100000个Integer对象实际占用约2MB左右但在处理完一批后会清空再复用文件读缓冲默认8KB左右总内存占用通常在几十MB以内其中大头反而是JVM自身的开销。所以内存上绝对没有问题。时间复杂度上每处理一条数据最坏触发一次O(log K)的堆调整总共N条就是O(N log K)。如果K只有100logK约等于71000万条数据的全部冒泡调整次数大约是7000万次纯计算量并不大真正的瓶颈在文件读取和解析。4. 进阶数据分布不友好时怎么优化4.1 重复数据、负数、空行这些坑实际文件可不像测试数据那么规矩。常见的几个坑我在这里一次性列出来负数不能忽略小顶堆不需要预填Integer.MIN_VALUE所以负数也能正常参与比较完全没问题。怕的是有些人先在堆里初始化一圈0遇到负数时就误把0当成了门槛结果负数进不了堆逻辑就错了。我实现的懒加载方式正好规避了这个问题。空行和非法字符串Integer.parseInt遇到非数字直接抛异常。工程上需要判断一下行内容是否为空或者干脆catch掉异常并计数。重复数据要不要去重如果业务要求“TopK个不同元素”堆方案需要额外配合哈希表统计每个值的出现次数如果只是“TopK个最大元素且可以重复出现”那堆天然支持重复不用做任何处理。4.2 分组TopK和分片合并还有一种常见需求是分组TopK。比如数据是“城市 用户ID”要按城市取每个城市的前10名再判断某个城市是否进入全国前100。这种情况如果直接在内存里建一个大堆存的是全国的TopK那分组信息就丢了。正确做法分两步按分组键比如城市做分桶桶数据量可以很大直接落盘到临时目录每个桶单独跑一次堆算法得到组内TopK组间再根据具体业务做合并或者筛选。分片合并的原理我在2.2节已经证明过本地TopK合并不会漏掉全局TopK。这个性质在做分布式扩展时很关键值得在心里记牢。4.3 抽样近似与二次扫描有些场景Timing很敏感比如实时榜单没必要精确到极值只要求一个“足够接近真实”的结果。这时候可以用抽样来省内存和时间先随机抽1%的数据内存里求近似TopK得到一个“可能进入TopK的阈值T”第二遍扫描全量数据只把大于等于T的元素送入堆这样大部分元素在第一遍比较时就被丢弃堆的操作次数明显减少。这只能算近似方案因为抽样得到的阈值有误差可能把一些本应进入TopK的尾部元素提前过滤掉。如果业务要求绝对精确不建议用这个方案如果只是做趋势榜、推荐候选池那效果非常好。5. 踩坑实录与性能对比5.1 高频问题速查表我在把这个算法应用到实际项目的过程中收集了一些典型问题按出现频率整理成表问题表现原因与解决办法内存OOM堆还没满就溢出极可能是用了Files.readAllLines或List全量读入把文件一次性装进内存了务必改成流式读取结果数量不足K个输出只有几十条数据总量本身小于K或者在处理过程中过滤条件过严直接返回堆里现有的size个元素并提示调用方时间慢到不可接受跑了几分钟还没出结果大概率卡在parseInt或磁盘随机读优先优化IO必要时转二进制定长存储堆顶被频繁替换日志显示大量命中数据方差小、重复度高的典型表现可以考虑先去重或改用计数压缩中途抛异常数字格式异常文件里有空行或脏数据读行前先trim对异常行做容错处理与全排序结果不一致边界值比较不稳基本是相等值处理的问题检查是否用了严格大于另一个原因是堆里初始化了默认值未满时直接比较5.2 一个简单的性能对照我曾经在自己的笔记本上做了一个对照实验数据是1000万条整数K取100。全量排序方案是一次性读入List排序取前100。程序跑完大约花了几十秒峰值内存动辄数百MB中途还出现过明显的卡顿。而堆方案跑完大概只有几秒内存占用稳稳的。这个对比非常直观地说明了一件事同样的业务目标“用什么数据结构”决定了程序能不能撑住大数据量。性能差距的根源在于全排序的时间复杂度是O(N log N)且内存O(N)堆方案是O(N log K)内存O(K)。在数据量远超内存时前者根本没有运行条件后者几乎是唯一正确解。5.3 五个真正有用的细节习惯最后分享几个长期写这种底层算法后养成的习惯都是文档里不会告诉你的先写堆的单元测试再跑大数据。我用一个几千条的小文件验证结果与Collections.sort完全一致后再上大数据能省下大量定位时间。文件用缓冲区包一层。直接FileInputStream单字节读性能差到离谱BufferedReader或BufferedInputStream是最基本的入门配置。不要用递归下沉。虽然递归代码短但堆深度logK在K较大时也会产生额外开销循环写法更稳。临时文件要加后缀并统一清理。做外部归并时如果中途程序异常退出临时文件容易残留最好在启动时清理旧文件或者把临时文件写进独立目录。比较大小时明确“严格大于”和“大于等于”的区别。这个细节直接决定TopK结果与全排序结果能否完全对上测试时要刻意覆盖边界值。回到开头那句话数据量大于内存时手写TopK真正的核心不是“排序”而是一个大小为K的小顶堆加一趟流式扫描。这个方案代码量小、思路直观、内存稳定足以覆盖绝大多数真实场景。只有当K膨胀到堆都装不下、或者确实要全局有序输出时才需要动用分块排序和多路归并这种更重的手段。我自己最有体会的一点是别急着上分布式先算清楚“堆能不能解决”很多看起来吓人的大数据问题其实一台普通机器加一个手写堆就轻松搞定了。希望这篇文章能帮你把这道经典题吃透。
“数据量大于内存”这个前提做TopK不稀奇但要你手写、不用现成框架还要同时保证内存稳定、性能过关就值得好好拆一遍了。很多朋友一听到“海量数据”就想去上外部排序、上分布式其实大多数场景下的最优解就是一个自己手搓的小顶堆。这篇文章我就把这套东西彻底讲明白从题目怎么拆到堆为什么是主角再到完整代码实现、踩坑记录和进阶优化全部放在一篇里。1. 先把问题拆明白“数据量大于内存”到底难在哪1.1 TopK到底在求什么TopK的本质很简单在一堆数据里找出最大的K个或最小的K个。比如一份上千万条的日志里找访问量前100的IP或者一个大表里找评分最高的50个商品。它和“全排序”最大的区别是我们根本不需要知道其他元素的精确顺序因此也就没必要把所有数据都排好序。这里有一个很容易被忽略的点TopK的结果通常不要求有序。最常见的场景只要“前K个集合”至于这K个内部谁大谁小往往是等返回之后再排一下或者根本不需要。理解这一点后你会发现很多看似复杂的方案其实都是白折腾的。1.2 “数据量大于内存”真正难在哪很多人看到“数据量大于内存”第一反应是“内存装不下得把数据拆开落盘”。这个理解本身没有错但容易把问题带偏。真正的难点不在“存不下全部数据”而在于你必须在不需要完整数据的前提下用稳定的内存得到结果。举个很直观的例子一个100G的文件要取Top100如果你只会readAllLines再排序那程序在启动时就已经挂了因为压根装不下。但如果换一个思路我们维护一个大小为100的小顶堆从文件第一行开始一条条往堆里塞堆里始终只留“目前见过的最大的100个”。整个过程中内存只存了100个元素文件再大都无所谓。这就是“流式处理”的感觉也是TopK这类问题能扛住超大数据的根本原因。所以数据量大于内存的真正挑战分两层第一层是内存上的挑战要求算法空间复杂度不随数据总量膨胀最好是O(K)第二层是IO上的挑战文件这么大怎么读得快、怎么减少解析开销经常比算法本身更容易成为性能瓶颈。再往下拆还有一个隐形的决策点K本身大不大如果K只有100堆方案无脑最佳如果K是几百万甚至更大那堆的规模和比较次数都会上涨这时候可能就要考虑分块、外部排序这类更重的方案了。这个问题我放到下一节细讲。2. 两条技术路线怎么选小顶堆与外部归并2.1 为什么求最大TopK偏偏要用小顶堆这是整个题目里最反直觉、也最常被面试官追问的一个点。很多人的第一反应是求最大的TopK当然要用大顶堆把最大的放堆顶。但仔细想一下大顶堆存下所有见过的数据才能找出最大值那内存就不是O(K)了而是O(N)直接违背“数据量大于内存”的约束。正确做法是用小顶堆。堆顶永远是堆里最小的元素它充当一个“门槛”。新来一个元素如果比门槛大就说明它值得留在结果里于是替换掉门槛再重新调整堆如果比门槛小说明它进不了前K直接丢弃。每次操作只需要和堆顶比较堆的规模始终只有K个元素。用一个生活化的类比小顶堆就像K个座位的VIP区门槛是VIP区里综合实力最弱的那个人。新来的人如果能打败最弱的那个人就可以把最弱的人挤出去自己坐进去如果连最弱都打不过那确实没资格进VIP区。全程不需要关心VIP区外面那些已经被淘汰的人。为什么不用“先全部加载到数组里排序取前K”因为那要求O(N log N)时间和O(N)空间在大数据量下既不聪明也不可持续。为什么不用“维护一个长度为K的链表/数组直接插排”因为插入和移动代价高最坏情况下O(NK)数据一多就慢到怀疑人生。堆结构把插入和替换都压缩到O(log K)这才是它的价值。2.2 什么时候该上外部归并堆方案几乎是无脑首选但它有两个弱点K很大时比如K 5000万堆本身的内存就不是小数目而且每次调整的log K成本也随之上升如果后续还要求“这K个元素本身也是有序的”或者“我想知道第K1、K2名的近似值”单靠堆就不够直接了。这时候可以考虑分块外部排序 多路归并。思路很简单把大文件切成很多块每块大小控制在内存能容纳的范围内对每一块在内存里排好序写回临时文件用一个多路归并把所有临时文件合并成一个全局有序的大序列排到“剩下最后K个元素”时这K个就是全局TopK。这个方案的优点是可以处理超大K还能顺便拿到有序结果缺点是IO开销大要多次写临时文件程序复杂度也上了一个台阶。一般只在K达到堆容量上限、或者业务确实需要全局有序输出时才用它。这里再提一个“分片秤重”的思路如果数据分布在很多台机器上可以先让每台机器在本地用堆求出TopK再把所有机器的TopK汇总到一台机器上做一次合并。这个做法是精确的不是近似。原因很简单全局前K名中的任意一个元素如果不在某台机器的本地TopK里那说明在这台机器上至少有K个元素比它大而这个“至少K个”会直接推算出它在全局的排名一定在K之后矛盾。所以本地TopK合并全局TopK不会漏。2.3 选型决策一览场景特点推荐方案大部分常规场景K 百万量级小顶堆流式扫描数据到达方式是流式、无法全部落盘小顶堆天然适合K非常大堆内存吃紧分块排序 多路归并要求输出顺序、知道完整的边界名次外部归并取全局有序序列数据分布在多台机器每机堆求TopK汇总合并只需要近似TopK允许少许误差抽样估算阈值二次过滤选型的原则很简单能用堆就用堆堆解决不了再上重武器。我见过不少项目一上来说要搭一套分布式方案最后数据量其实一台普通机器加上堆算法轻松能跑完纯粹是过度设计了。3. 手写实现从造数到出结果这一节直接上代码。语言我用Java逻辑同样可以照搬到C、Go或者Python。手写的重点在于自己实现二叉堆而不是用现成的优先队列类库这样才能理解siftUp和siftDown这两个核心动作。3.1 先造一个数据量大于内存的测试文件没有测试数据讨论优化都是空谈。我习惯先造一个文本文件每行一个整数模拟“一条记录”。比如生成1000万条数据普通笔记本上大概90MB对内存模拟已经足够有说服力了如果你机器内存不大可以把总量改小一点逻辑不变。import java.io.BufferedWriter; import java.io.IOException; import java.nio.file.Files; import java.nio.file.Path; import java.util.Random; public class GenData { public static void main(String[] args) throws IOException { int total 10_000_000; int bound 100_000_000; Random random new Random(42); try (BufferedWriter writer Files.newBufferedWriter(Path.of(data.txt))) { for (int i 0; i total; i) { writer.write(Integer.toString(random.nextInt(bound))); writer.newLine(); } } } }这里把随机种子固定为42方便复现和对比。造数据时有一点需要注意如果数值范围太小、重复度太高堆顶会被频繁替换测试结果会与真实场景偏差较大所以我把范围设为1亿。3.2 手写小顶堆的核心实现堆的本质是一个完全二叉树用数组存储就行。关键操作只有两个新元素从底部加入时往上浮siftUp替换堆顶后往下降siftDown。我写代码时习惯把这两个方法直接放在TopK类内部避免重复传参。import java.util.Arrays; public class TopK { private final int k; private final int[] heap; private int size 0; public TopK(int k) { this.k k; this.heap new int[k]; } public void add(int value) { if (size k) { // 堆还没满直接放末尾然后上浮 heap[size] value; siftUp(size); size; } else if (value heap[0]) { // 堆满了且新元素大于堆顶当前门槛 heap[0] value; siftDown(0); } // 其他情况value 堆顶直接丢弃 } private void siftUp(int index) { while (index 0) { int parent (index - 1) / 2; if (heap[index] heap[parent]) { break; } swap(index, parent); index parent; } } private void siftDown(int index) { int n size; while (true) { int left 2 * index 1; int right 2 * index 2; int smallest index; if (left n heap[left] heap[smallest]) { smallest left; } if (right n heap[right] heap[smallest]) { smallest right; } if (smallest index) { break; } swap(index, smallest); index smallest; } } private void swap(int i, int j) { int tmp heap[i]; heap[i] heap[j]; heap[j] tmp; } public int[] result() { int[] copy Arrays.copyOf(heap, size); Arrays.sort(copy); return copy; } }有几个细节值得多说一句siftDown里的比较和交换不要用递归。虽然递归写的代码更短但堆深度是logK递归调用在K大的时候会产生不必要的栈压力写成循环更好。相等情况的处理value heap[0]这个条件用严格大于。如果新元素和堆顶相等替换没有意义跳过反而减少一次下沉开销。最后排序堆内部的顺序只是堆序不是严格有序的所以result()里先复制出一个数组再做一次排序。如果业务上只要“前K个集合”也可以跳过这步直接返回堆里的原始数组。3.3 流式扫描主流程有了堆结构主流程就非常简单不断从文件读数据一条条递给add()。为了减少IO次数我用了一个小技巧每读满一批数据再批量灌进堆而不是读一条就处理一条。这样可以降低方法调用和对象构造的开销。import java.io.BufferedReader; import java.io.IOException; import java.nio.file.Files; import java.nio.file.Path; import java.util.ArrayList; import java.util.List; public class TopKRunner { public static void main(String[] args) throws IOException { int k 100; TopK topK new TopK(k); int batchSize 100_000; ListInteger batch new ArrayList(batchSize); try (BufferedReader reader Files.newBufferedReader(Path.of(data.txt))) { String line; while ((line reader.readLine()) ! null) { batch.add(Integer.parseInt(line.trim())); if (batch.size() batchSize) { for (int value : batch) { topK.add(value); } batch.clear(); } } } // 处理末尾不足一批的数据 for (int value : batch) { topK.add(value); } int[] result topK.result(); for (int i result.length - 1; i 0; i--) { System.out.println(result[i]); } } }这个主流程看起来平平无奇但已经解决了“数据量大于内存”的核心问题文件不是一次性读入而是按行流式读取堆里最多只有K个int内存不随文件大小增长批处理只是优化IO不影响正确性。如果你要追求极致性能可以把解析操作也优化一下Integer.parseInt(line.trim())里包含了很多字符串处理换成手写的ASCII转int可以减少一部分开销。另一个思路是把数据从文本改成二进制定长存储一个int占4字节1000万条数据约40MB读起来更快解析也更简单。这个方案在实际工程里很常见。3.4 内存占用和时间复杂度估算很多人问数据量100G这个程序真的不炸吗我们直接算一笔账堆数组K100时就是100个int占400字节几乎可以忽略不计批处理链表100000个Integer对象实际占用约2MB左右但在处理完一批后会清空再复用文件读缓冲默认8KB左右总内存占用通常在几十MB以内其中大头反而是JVM自身的开销。所以内存上绝对没有问题。时间复杂度上每处理一条数据最坏触发一次O(log K)的堆调整总共N条就是O(N log K)。如果K只有100logK约等于71000万条数据的全部冒泡调整次数大约是7000万次纯计算量并不大真正的瓶颈在文件读取和解析。4. 进阶数据分布不友好时怎么优化4.1 重复数据、负数、空行这些坑实际文件可不像测试数据那么规矩。常见的几个坑我在这里一次性列出来负数不能忽略小顶堆不需要预填Integer.MIN_VALUE所以负数也能正常参与比较完全没问题。怕的是有些人先在堆里初始化一圈0遇到负数时就误把0当成了门槛结果负数进不了堆逻辑就错了。我实现的懒加载方式正好规避了这个问题。空行和非法字符串Integer.parseInt遇到非数字直接抛异常。工程上需要判断一下行内容是否为空或者干脆catch掉异常并计数。重复数据要不要去重如果业务要求“TopK个不同元素”堆方案需要额外配合哈希表统计每个值的出现次数如果只是“TopK个最大元素且可以重复出现”那堆天然支持重复不用做任何处理。4.2 分组TopK和分片合并还有一种常见需求是分组TopK。比如数据是“城市 用户ID”要按城市取每个城市的前10名再判断某个城市是否进入全国前100。这种情况如果直接在内存里建一个大堆存的是全国的TopK那分组信息就丢了。正确做法分两步按分组键比如城市做分桶桶数据量可以很大直接落盘到临时目录每个桶单独跑一次堆算法得到组内TopK组间再根据具体业务做合并或者筛选。分片合并的原理我在2.2节已经证明过本地TopK合并不会漏掉全局TopK。这个性质在做分布式扩展时很关键值得在心里记牢。4.3 抽样近似与二次扫描有些场景Timing很敏感比如实时榜单没必要精确到极值只要求一个“足够接近真实”的结果。这时候可以用抽样来省内存和时间先随机抽1%的数据内存里求近似TopK得到一个“可能进入TopK的阈值T”第二遍扫描全量数据只把大于等于T的元素送入堆这样大部分元素在第一遍比较时就被丢弃堆的操作次数明显减少。这只能算近似方案因为抽样得到的阈值有误差可能把一些本应进入TopK的尾部元素提前过滤掉。如果业务要求绝对精确不建议用这个方案如果只是做趋势榜、推荐候选池那效果非常好。5. 踩坑实录与性能对比5.1 高频问题速查表我在把这个算法应用到实际项目的过程中收集了一些典型问题按出现频率整理成表问题表现原因与解决办法内存OOM堆还没满就溢出极可能是用了Files.readAllLines或List全量读入把文件一次性装进内存了务必改成流式读取结果数量不足K个输出只有几十条数据总量本身小于K或者在处理过程中过滤条件过严直接返回堆里现有的size个元素并提示调用方时间慢到不可接受跑了几分钟还没出结果大概率卡在parseInt或磁盘随机读优先优化IO必要时转二进制定长存储堆顶被频繁替换日志显示大量命中数据方差小、重复度高的典型表现可以考虑先去重或改用计数压缩中途抛异常数字格式异常文件里有空行或脏数据读行前先trim对异常行做容错处理与全排序结果不一致边界值比较不稳基本是相等值处理的问题检查是否用了严格大于另一个原因是堆里初始化了默认值未满时直接比较5.2 一个简单的性能对照我曾经在自己的笔记本上做了一个对照实验数据是1000万条整数K取100。全量排序方案是一次性读入List排序取前100。程序跑完大约花了几十秒峰值内存动辄数百MB中途还出现过明显的卡顿。而堆方案跑完大概只有几秒内存占用稳稳的。这个对比非常直观地说明了一件事同样的业务目标“用什么数据结构”决定了程序能不能撑住大数据量。性能差距的根源在于全排序的时间复杂度是O(N log N)且内存O(N)堆方案是O(N log K)内存O(K)。在数据量远超内存时前者根本没有运行条件后者几乎是唯一正确解。5.3 五个真正有用的细节习惯最后分享几个长期写这种底层算法后养成的习惯都是文档里不会告诉你的先写堆的单元测试再跑大数据。我用一个几千条的小文件验证结果与Collections.sort完全一致后再上大数据能省下大量定位时间。文件用缓冲区包一层。直接FileInputStream单字节读性能差到离谱BufferedReader或BufferedInputStream是最基本的入门配置。不要用递归下沉。虽然递归代码短但堆深度logK在K较大时也会产生额外开销循环写法更稳。临时文件要加后缀并统一清理。做外部归并时如果中途程序异常退出临时文件容易残留最好在启动时清理旧文件或者把临时文件写进独立目录。比较大小时明确“严格大于”和“大于等于”的区别。这个细节直接决定TopK结果与全排序结果能否完全对上测试时要刻意覆盖边界值。回到开头那句话数据量大于内存时手写TopK真正的核心不是“排序”而是一个大小为K的小顶堆加一趟流式扫描。这个方案代码量小、思路直观、内存稳定足以覆盖绝大多数真实场景。只有当K膨胀到堆都装不下、或者确实要全局有序输出时才需要动用分块排序和多路归并这种更重的手段。我自己最有体会的一点是别急着上分布式先算清楚“堆能不能解决”很多看起来吓人的大数据问题其实一台普通机器加一个手写堆就轻松搞定了。希望这篇文章能帮你把这道经典题吃透。
