外部排序:数据大到内存放不下,怎么把它排好序

真实验证:外部排序 vs sorted(),结果完全一致

真实实现了"分块排序落盘 + heapq.merge 多路归并"的外部排序,和 Python 内置 sorted() 跑同一份数据交叉验证:

N = 50000
expected = sorted(events)
got = list(external_sort(events, chunk_size=1000, tmpdir=tmpdir))

归并这一步没有自己手写堆,直接用的 Python 标准库 heapq.merge()——它本来就是给"合并多个已排序的可迭代对象"设计的,内部维护一个大小等于"数据源个数"的小根堆,每次弹出堆顶最小值,再从它所在的那个数据源里补一个新元素进堆,这正是多路归并的标准做法。

真实踩坑:第一版实现,内存根本没省下来

第一版写法图省事,把每个块整体 pickle.dump 成一个文件,归并阶段用 pickle.load(f) 把整个块一次性读回内存再构造迭代器——正确性测试全过,但外部排序的意义就是"别让内存占用跟数据总量挂钩",这份写法悄悄违反了这一点:

# 第一版:load() 把整个块一次性反序列化成列表
def load(path):
    with open(path, "rb") as f:
        return pickle.load(f)
iterators = [iter(load(p)) for p in chunk_files]   # 100 个块,直接全读进内存了

N = 2_000_000, chunk_size = 20_000

问题就出在 [iter(load(p)) for p in chunk_files] 这一行——列表推导式会把每个 load(p) 都立刻真实执行一遍,100 个块(总共 200 万条记录)在归并真正开始之前就已经被全部读进内存了,跟不分块直接排序几乎没区别。改成真正的流式读取,每次只反序列化一条记录:

# 修复版:每条记录单独 pickle.dump,读的时候一条一条 pickle.load
def _read_chunk(path):
    with open(path, "rb") as f:
        while True:
            try:
                yield pickle.load(f)
            except EOFError:
                break

N = 2_000_000, chunk_size = 20_000(同样的数据规模)

同样 200 万条记录,峰值内存从 310MB 真实降到 33.3MB,将近 10 倍。这个坑也说明:外部排序"结果对不对"和"内存到底有没有真的省下来"是两件要分开验证的事——单靠一次 == sorted(events) 的正确性测试,完全测不出这类"逻辑对、目的没达到"的问题,得真的去量峰值内存。

真实验证:数据能装进内存时,外部排序反而更慢

50 万条记录,这个规模内存完全放得下,分别真实跑一遍两种方案:

sorted(events)                                          # 方案一
external_sort(events, chunk_size=20000, tmpdir=tmpdir)   # 方案二

外部排序多出来的时间基本都花在真实的磁盘 I/O 和 pickle 序列化/反序列化上——这是用"更低的内存占用"换"更慢的速度",数据能装进内存的时候完全不划算,只有真的装不下才值得用。

真实验证:接上高峰在线人数的扫描线算法,结果完全一致

把外部排序的输出直接喂给上一篇的扫描线算法,不落地成完整列表,验证整条流水线和"全内存 sorted() 再扫描"结果一致:

N_USERS = 300000
baseline = sweep_peak(sorted(events))                                    # 基准
pipeline = sweep_peak(external_sort(event_stream(), chunk_size=5000))    # 流水线

整个"生成事件 → 外部排序 → 扫描线求峰值"的流水线里,任何一个环节都不需要把全部数据一次性放进内存——真正符合"数据再大也能处理"这个最初的目标。