高效排序百万级数据：Python内存内并行归并排序实战指南-Python教程-PHP中文网

高效排序百万级数据：Python内存内并行归并排序实战指南

本文介绍如何在内存充足前提下，通过多进程分块排序 + heapq.merge 归并，显著加速 python 中大规模列表（百万级）的排序过程，兼顾性能与代码简洁性，避免盲目引入 multiprocessing 反而拖慢速度的常见误区。

本文介绍如何在内存充足前提下，通过多进程分块排序 + heapq.merge 归并，显著加速 python 中大规模列表（百万级）的排序过程，兼顾性能与代码简洁性，避免盲目引入 multiprocessing 反而拖慢速度的常见误区。

当数据量达百万甚至千万级别但仍可完全载入内存时，Python 内置的 sorted() 或 list.sort() 虽然稳定可靠，但默认为单线程 Timsort，在多核 CPU 上无法充分利用硬件资源。此时，分治式并行排序是更优解：将大列表切分为多个子块，并行排序后，再以时间复杂度 O(N) 的方式归并——这正是 heapq.merge() 的核心优势。

以下是一个轻量、无第三方依赖（仅用标准库）的高效实现：

import os
from multiprocessing import Pool
from random import sample
import heapq

def sort_chunk(chunk):
    """对单个数据块执行内置排序（Timsort），返回已排序列表"""
    return sorted(chunk)

def chunked_list(lst, n):
    """生成长度为 n 的数据块迭代器"""
    for i in range(0, len(lst), n):
        yield lst[i:i + n]

def parallel_sort(lst, num_processes=None):
    """
    并行归并排序主函数
    :param lst: 待排序的可迭代对象（建议为 list）
    :param num_processes: 进程数，默认为系统逻辑 CPU 核心数
    :return: 全局升序排列的新列表
    """
    if not lst:
        return []

    if num_processes is None:
        num_processes = max(1, os.cpu_count() or 1)

    # 均匀分块（最后一块可能略小）
    chunk_size = max(1, len(lst) // num_processes)
    chunks = list(chunked_list(lst, chunk_size))

    # 多进程并发排序各块
    with Pool(processes=num_processes) as pool:
        sorted_chunks = pool.map(sort_chunk, chunks)

    # 高效归并：heapq.merge 接收多个已排序序列，惰性生成器式归并
    # 转为 list 以获得完整结果（如只需前 k 项，可用 islice 优化）
    return list(heapq.merge(*sorted_chunks))

# 使用示例
if __name__ == '__main__':
    # 模拟百万级随机整数数据集
    large_list = sample(range(10_000_000), 1_000_000)

    # 执行并行排序（注意：首次运行会触发进程启动开销）
    sorted_list = parallel_sort(large_list)

    print("前10项:", sorted_list[:10])  # [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]

✅ 关键优势说明：

不重复排序：各子块独立排序后，heapq.merge 利用堆结构逐个提取最小元素，避免二次全量比较；
内存友好：heapq.merge 返回迭代器，list(...) 仅在最终合并时一次性构建结果，中间无冗余副本；
自动负载均衡：multiprocessing.Pool.map 内部调度均衡，无需手动处理 chunk 分配偏差。

⚠️ 重要注意事项：

macOS UI 自动化技能包 —— 用 Python 控制你的 Mac

让 macOS 自动化像说话一样简单 —— 用代码控制你的 Mac，无需学习 AppleScript 系统要求 macOS 14+ (Sonoma) Python 3.9+ 需要开启：辅助功能 + 屏幕录制权限

下载

适用前提：数据必须能完整加载进内存。若超出物理内存（如 10GB 数据跑在 8GB RAM 机器上），应改用外部排序（如 pandas.read_csv(..., chunksize=...) + 临时文件归并）或数据库（SQLite/PostgreSQL ORDER BY）；
进程开销权衡：对于小于 10 万条的列表，并行化反而因进程创建/通信开销而变慢——务必实测基准（可用 timeit 或 perfplot）；
数据类型限制：所有元素需支持
Windows 兼容性：需确保 if __name__ == '__main__': 保护，防止 spawn 模式下无限递归创建进程。

? 进阶建议：