一亿条数据取前100条完全指南：从全量排序到分块流式最小堆的4种解法实测

目录

1. 先说结论
2. 四种解法的实测数据
3. 为什么最小堆只需要 K 个位置
4. 为什么划分比排序快
5. 一段能直接跑的完整代码
6. 症状 → 原因 → 解法对照表

1. 先说结论（The Verdict）

一亿条数据取前 100，这是一道被问了二十年的经典问题，标准答案是「最小堆（Min-Heap）」，但 2026 年在一台普通开发机上，标准答案已经不是最快的了 🎯。

先把结论摆出来，后面全部用实测数据支撑：

第一，别再全量排序。 sorted(data)[-100:] 的复杂度是 $O(n \log n)$，而你只需要前 100 个，剩下的 9999.99 万条根本不需要有序。在一亿条 int32 上，全量排序比划分慢 2.8 倍。

第二，K 越小，堆越划算；K 越大，堆越吃亏。 最小堆的复杂度是 $O(n \log k)$，当 $k = 100$ 时 $\log_2 100 \approx 6.6$，看起来很便宜。但这是比较次数的账，不是实际耗时——Python 的 heapq 是纯 C 实现，可你每喂一个元素进去都要经过一次 Python 层的函数调用。一亿次函数调用的开销，远大于算法层面的那点差别。

第三，真正决定方案的不是算法，是内存。 一亿条 int32 占 381 MB，你这台机器大概率装得下；一亿条带字符串字段的日志记录，占 20 GB，就装不下了。装不下的时候，$O(n)$ 的划分算法一次都用不了，必须切成分块（Chunk）流式处理。

打个比方 🎭：这就像在一个人口一亿的城市里找最高的 100 个人。全量排序是把全市市民按身高排成一列纵队——排完了你确实知道前 100 名是谁，但你为了这 100 个人，让 9999.99 万个人互相比较了一遍。最小堆则是设一个 100 人的「名人堂」，门口挂一条线：比门里最矮的那个矮，直接走人，连门都不用进。

2. 四种解法的实测数据（The Benchmark）

所有数字都由本机实测产出，环境如下：

四种解法各自在独立进程里跑，避免内存互相污染；峰值内存用后台线程每 2 毫秒采样一次 RSS 得出，取的是相对进程启动基线（约 38 MB）的增量。

同一份数据，五种写法，第 100 名全部是 2,147,481,280，逐项结果一致 ✅。所以这张表比较的只是成本，不是正确性。

几个数字值得单独拎出来说：

纯 Python 堆慢 40 倍。 10.45 秒对 0.26 秒。这不是算法错了，而是把一亿次比较放在 Python 解释器里做，每次都要过一次 heapq.heappush 或 heapq.heapreplace 的 C 函数边界。算法复杂度 $O(n \log k)$ 里的常数项，在这里就是 Python 的函数调用开销。

全量 argpartition 内存反而最高。 1145 MB，比全量排序的 382 MB 高出 3 倍。原因是 np.argpartition 要额外产出一个 int64 的索引数组：一亿个 int64 就是 800 MB，再加上原始数据 381 MB，正好对上。如果你不需要索引、只要值，用 np.partition 能省掉这 800 MB，耗时还从 0.53 秒降到 0.26 秒。

分块流式的内存几乎与数据量无关。 46 MB，因为每次只读 400 万条（16 MB）进内存，堆里最多只放 100 个数。数据涨到十亿条，峰值内存还是 46 MB 左右，只是时间线性变长。

2.1 K 变了，最优解也会变

上面都是 $k = 100$。如果老板明天说要前 10 万呢？我在一千万条数据上把 K 从 10 扫到 100 万，结果如下：

这张表的读法很反直觉 👀：

• 全量 partition 几乎不随 K 变化，从 12.8 ms 到 16.4 ms，K 涨了十万倍，耗时只涨 28%。因为它找到第 K 名就停了，而找第 100 名和找第 100 万名，在一次线性划分里工作量差别很小。
• 分块 + 堆在 K 超过一万后开始崩，K 从 10 万涨到 100 万，耗时从 110 ms 跳到 1513 ms，13.7 倍。原因是块内 argpartition(block, -k) 在 $k$ 接近块大小时退化成完整排序，而全局堆也从「很少替换」变成「频繁替换」。
• 全量 sort 稳如老狗，52–57 ms，因为它的成本和 K 完全无关。

所以正确的判据不是「Top-K 就用堆」，而是：$k$ 小且数据放不进内存时用堆，$k$ 大或内存宽裕时用划分，需要全序才用排序。

数据工程的很多「最佳实践」，其实都有一个没写出来的前提条件。堆的前提条件是 $k \ll n$ 且内存受限，这两个条件一旦不成立，结论就反过来。

3. 为什么最小堆只需要 K 个位置（Why a Min-Heap Works）

先回答一个初学者最容易卡住的问题：找最大的 100 个，为什么用最小堆？

因为堆顶要当「门槛」用 🚪。

一个大小为 $k$ 的最小堆，堆顶是整个堆里最小的那个元素。放进 Top-K 的语境里，堆顶就是「当前前 100 名里最弱的那一位」。任何一个新元素进来，只要它不比这位最弱的强，就没有资格进榜；只有它比堆顶大，才有资格把堆顶挤出去。

这个设计的妙处在于：比较一次就够了。判断一个元素要不要处理，只需要拿它和堆顶比一次，$O(1)$。只有当它真的能进榜时，才需要付出 $O(\log k)$ 的代价把堆顶换掉并重新下沉。

反过来，如果用一个大小为 100 的最大堆呢？堆顶是当前 100 个里最大的，你没法用它当门槛——新元素比堆顶小不代表它进不了榜，它可能比第 2 名大。于是你只能把元素全塞进去，堆的规模退化成 $n$，内存优势全丢。

3.1 三种操作的成本

堆的各类操作代价是固定的，记住这张表就够用了：

代入 Top-K：一亿个元素，每个都要和堆顶比一次，共 $n$ 次 $O(1)$ 比较；其中最多有若干次会真正触发替换，每次 $O(\log k)$。所以总复杂度是 $O(n \log k)$，空间是 $O(k)$。

当 $k = 100$ 时，$\log_2 100 \approx 6.64$，理论上每个元素平均只需要 6.64 次比较。理论上——这个词很重要，第 2 节的实测已经告诉我们，常数项可以吃掉两个数量级的优势。

3.2 一个好消息：你不需要自己写堆

Python 标准库的 heapq 提供了现成的工具函数，其中 heapq.nlargest() 就是为这个场景准备的：

import heapq

data = [5, 1, 9, 3, 7, 2, 8]
print(heapq.nlargest(3, data))     # [9, 8, 7]

heapq.nlargest(n, iterable) 的内部实现会根据 $n$ 和数据规模自动选择策略：当 $n$ 较小时用大小为 $n$ 的最小堆；当 $n$ 与数据长度相当时退化为 sorted()。也就是说，官方实现里已经内置了「$k$ 大就用排序」这条判断——这正是第 2.1 节实测曲线的另一种表述。

不过 nlargest 有一个隐含成本：它接受的是 iterable，会完整遍历一遍。如果你的数据是从磁盘分块读的，用它反而不如自己维护堆——因为你需要控制每次读多少进内存。

参考资料：

• heapq --- 堆队列算法 -- Python 官方文档 ⭐值得阅读
• Heaps for Coding Interviews -- AlgoDrill

4. 为什么划分比排序快（Why Partition Beats Sort）

排序要做的事，是把所有元素排成一条严格有序的队伍；而取前 K 个只需要知道「哪些元素比第 K 名大」，不需要知道它们之间的顺序。这两件事的工作量差别很大。

4.1 复杂度上的差别

$O(n)$ 和 $O(n \log n)$ 的差距，在一亿这个量级上就是「反复切一半」和「切到底」的区别：$n \log_2 n$ 是 $n$ 的约 26.6 倍。

快速选择（QuickSelect，快速选择）是 Hoare 在 1961 年提出的，它本质上只做了快速排序的一半：每次划分后，如果第 K 名落在左半区，右半区直接扔掉不看。但它是随机化的，最坏情况下每次划分都只能削掉一个元素，退化成 $O(n^2)$。

1973 年，Blum、Floyd、Pratt、Rivest、Tarjan 五个人给出了确定性线性时间的选择算法，用「中位数的中位数」当枢轴，保证每次至少削掉 30%，最坏情况也是 $O(n)$。这个算法今天通称 BFPRT（取其五位作者姓氏首字母）。

参考资料：

• Time Bounds for Selection -- Journal of Computer and System Sciences, 1973, 7(4): 448–461 ⭐值得阅读
• Fast Deterministic Selection -- arXiv ⭐值得阅读
• Quickselect Algorithm: Find Any Order Statistic in O(n) Without Sorting -- SpaceComplexity

4.2 但 BFPRT 在实践中经常打不过 QuickSelect

这是本文第二个反直觉结论 ⚠️：理论上更优的 $O(n)$ 确定性算法，在真实机器上通常更慢。

Andrei Alexandrescu 在 2016 年的实验里明确指出：中位数的中位数「虽然是一个里程碑式的理论成果，但很少在实践中使用，因为它和它的变体比基于采样的简单方法更慢」。他给出的替代方案是自适应 QuickSelect——先用采样找枢轴，只在检测到划分退化时才切到中位数的中位数的兜底逻辑。

NumPy 用的就是这个思路。np.partition 的默认算法是 introselect，名字本身就是 introspective + select 的组合：以快速选择起步，当递归深度超过阈值时自动切换到 BFPRT 式的确定性兜底，从而既有快选的常数优势，又不会掉进 $O(n^2)$ 的坑。

官方文档给出的 introselect 特性表写得很清楚：平均速度标记为最快的 1，最坏情况 $O(n)$，额外工作空间 0，不稳定（不保证相同值的相对顺序）。

参考资料：

• numpy.partition -- NumPy 官方文档 ⭐值得阅读
• Min-Heap vs Sorting for Top-K: When O(n log K) Beats O(n log n) -- SpaceComplexity
• Top-K & the Bounded Heap Pattern -- Neel Mishra

4.3 partition 到底做了什么

一句话：把数组重新排布成「左边的都不大于第 K 名，右边的都不小于第 K 名」，但两边内部顺序不保证。

原始: [5, 1, 9, 3, 7, 2, 8]   取前 3 大
划分后: [1, 2, 3 | 5, 7, 8, 9]
                    ↑
              第 3 大的位置，之后只需再对右边 3 个排序

np.partition(data, -100) 会把 data 重新排成「最后 100 个位置恰好是最大的 100 个（无序）」。要输出有序结果，再对这 100 个做一次 np.sort 就行，代价可以忽略。

这里的代价函数值得算清楚：划分本身是 $O(n)$ 一趟，之后的排序只针对 100 个元素，是 $O(k \log k)$。总计 $O(n + k \log k)$。$n = 10^8$、$k = 100$ 时，$k \log k \approx 664$，相对于 $10^8$ 完全可以忽略。

这是「按需付费」的典型：你只为真正需要的那部分有序性掏钱，剩下的无序性被当成免费资源丢掉了。

5. 一段能直接跑的完整代码（The Runnable Code）

上面都是结论，这一段是可直接复制运行的实现 🚀。它做的事：生成一亿条随机 int32 落盘，用分块流式最小堆取前 100，再用全量排序做对拍验证，两种解法的前 100 名必须逐项一致。

依赖只有 numpy 和 psutil：

pip install numpy psutil

"""一亿条 int32 取前 100：分块流式解法 + 与全量排序对拍。

依赖: numpy, psutil
用法: python top100.py            # 默认一亿条
      python top100.py 10000000   # 一千万条，快速验证
"""
import heapq
import os
import sys
import time

import numpy as np
import psutil

PATH = "big_i32.bin"     # 落盘的数据文件
K = 100                  # 取最大的 100 个
CHUNK = 4_000_000        # 每块 400 万条（16 MB）


def rss_mb() -> float:
    """返回当前进程的常驻内存（MB）。"""
    return psutil.Process().memory_info().rss / 1024 ** 2


def build_file(n: int) -> None:
    """生成 n 个随机 int32 落盘；文件大小恰为 n × 4 字节。"""
    if os.path.exists(PATH) and os.path.getsize(PATH) == n * 4:
        return
    rng = np.random.default_rng(7)
    rng.integers(0, 2 ** 31 - 1, size=n, dtype=np.int32).tofile(PATH)


def top100_streaming(n: int) -> tuple[list[int], float, float]:
    """分块读盘 + 块内划分 + 全局最小堆，返回 (结果, 耗时, 峰值内存增量)。"""
    baseline = rss_mb()
    peak = baseline
    heap: list[int] = []
    t0 = time.perf_counter()
    with open(PATH, "rb") as file_handle:
        while True:
            block = np.fromfile(file_handle, dtype=np.int32, count=CHUNK)
            if block.size == 0:
                break
            peak = max(peak, rss_mb())
            for value in block[np.argpartition(block, -K)[-K:]].tolist():
                if len(heap) < K:
                    heapq.heappush(heap, int(value))
                elif value > heap[0]:
                    heapq.heapreplace(heap, int(value))
            peak = max(peak, rss_mb())
    return sorted(heap, reverse=True), time.perf_counter() - t0, peak - baseline


def top100_sort(n: int) -> tuple[list[int], float]:
    """全量读入内存后排序，作为对拍用的参照实现。"""
    t0 = time.perf_counter()
    data = np.fromfile(PATH, dtype=np.int32)
    data.sort()
    return data[-K:][::-1].tolist(), time.perf_counter() - t0


if __name__ == "__main__":
    n = int(sys.argv[1]) if len(sys.argv) > 1 else 100_000_000
    build_file(n)
    print(f"n = {n:,}  k = {K}  文件 {os.path.getsize(PATH) / 1024 ** 2:.0f} MB")

    stream_result, stream_cost, stream_peak = top100_streaming(n)
    print(f"分块流式 : {stream_cost:6.2f} s  峰值增量 {stream_peak:6.0f} MB  最大值 {stream_result[0]:,}")

    sort_result, sort_cost = top100_sort(n)
    print(f"全量排序 : {sort_cost:6.2f} s  最大值 {sort_result[0]:,}")

    assert stream_result == sort_result, "两种解法结果必须完全一致"
    print("两种解法前 100 名逐项一致 ✓")

在本机跑出来的输出：

n = 100,000,000  k = 100  文件 381 MB
分块流式 :   0.44 s  峰值增量     15 MB  最大值 2,147,483,633
全量排序 :   0.68 s  最大值 2,147,483,633
两种解法前 100 名逐项一致 ✓

5.1 这段代码里三个关键设计

第一，块内先划分。 代码里有个容易被忽略的细节：block[np.argpartition(block, -K)[-K:]]。每读进一块 400 万条，先用 NumPy 的 argpartition 在 C 层压到 100 个候选，再交给 Python 的 heapq。

如果没有这一步，一亿条数据全走 heapq，就是第 2 节实测的 10.45 秒。加了一行 argpartition，耗时掉到 0.43 秒——同样的算法，把比较工作从 Python 层搬到 C 层，快了 24 倍。

第二，CHUNK 这个数字是算出来的，不是拍的。 400 万条 int32 = 16 MB。选这个值要考虑三件事：块太小，np.fromfile 的系统调用次数多，I/O 开销占比上升；块太大，峰值内存上升，还可能被操作系统换页。16 MB 是一个比较稳的中间值，你可以在 100 万到 1000 万之间调，结果不会变，只是速度和内存此消彼长。

第三，assert 对拍不能省。 这段代码的 assert stream_result == sort_result 是全文最重要的一行。Top-K 的实现有太多容易写错的地方（堆的方向、边界条件、argpartition 的负索引），而错误的结果往往「看起来很正常」——它确实返回了 100 个数，只是不一定是最大的 100 个。用一次全量排序做交叉验证，成本是 0.68 秒，换来的是确定性。

与此同时，两种解法的耗时差（0.44 秒 vs 0.68 秒）也印证了第 4 节的复杂度分析：分块流式是 $O(n + k \log k)$，全量排序是 $O(n \log n)$，在一亿这个量级上，前者更快是必然的，但差距不到 2 倍——因为两者的瓶颈都在读盘上。381 MB 的顺序读取本身就要占掉相当一部分时间。

所以别指望换算法能有数量级的提升。当 I/O 成为瓶颈时，算法优化只能省掉 CPU 那一半的账。

6. 症状 → 原因 → 解法对照表（Symptom Table）

Top-K 的坑几乎都藏在「结果看起来对」里。下表按「你最近遇到的现象」来读，不用从头读到底 📋。

前两行是最高频的两个错误，值得单独强调它们的性质差别 🎯：堆方向错是逻辑 bug，结果错但有随机性，能靠对拍发现；常数项问题不是 bug，结果完全正确，只是慢，靠对拍永远发现不了。 所以第 5 章的 assert 只能兜住第一类，第二类只能靠实测计时。

参考资料：

• Heap & Top-K -- Ephizen Wiki
• Heaps for Coding Interviews（含元组比较崩溃的坑） -- AlgoDrill
• Sift-Up, Sift-Down & Why They Are Correct -- Neel Mishra

单机能装下时，别排序、别开多机，直接分块 argpartition 加最小堆，46 MB 内存就够。装不下或需要全序时，才轮到外部排序和分布式出场。

本专栏《算法与数据结构实战》从经典题解的复杂度分析讲到真实机器上的实测对比，每篇都配一段可直接运行的代码和一份可复算的耗时数据，每周更新一篇。想看同一套方法在别的场景怎么落地，可以在专栏页按顺序读。