内存不足时如何无临时内存峰值地对Python字典按值排序？

针对10^8级、100GB内存占用的字典，在仅剩余20-25GB空闲内存的场景下，以下是几种无需高内存峰值的排序方案：

1. 堆排序+原地内存释放 #

利用heapq模块实现逐步排序，同时释放原字典的内存，避免一次性生成全量排序列表：

import heapq

# 初始化堆，迭代原字典的键（避免一次性生成items列表占内存）
heap = []
for key in list(x.keys()):  # 转list避免迭代时字典大小变化报错
    val = x.pop(key)
    heapq.heappush(heap, (val, key))

# 从堆中逐个取出最小元素，构建排序后的字典
sorted_dict = {}
while heap:
    val, key = heapq.heappop(heap)
    sorted_dict[key] = val

这个方法的内存峰值仅为堆的内存占用（与原字典元素总量相当，但原字典在逐步释放，实际总内存不会超过原字典大小太多），剩余20-25GB的空闲内存足够应对堆的少量额外开销。

2. 分批次外部排序 #

如果堆排序的内存占用仍有压力，可以采用分批次写入磁盘再归并的方式：

1. 分批处理并排序写入临时文件：

import os
import tempfile
import pickle

batch_size = 10**7  # 按剩余内存调整批次大小，比如每批处理约10GB数据
temp_files = []

# 迭代字典，分批取出键值对排序后写入临时文件
keys = list(x.keys())
for i in range(0, len(keys), batch_size):
    batch_keys = keys[i:i+batch_size]
    batch_items = [(x.pop(k), k) for k in batch_keys]
    batch_items.sort()  # 对当前批次排序
    # 写入临时文件
    with tempfile.NamedTemporaryFile(mode='wb', delete=False) as f:
        pickle.dump(batch_items, f)
        temp_files.append(f.name)

2. 多路归并生成最终字典：

import heapq
import pickle

# 打开所有临时文件，生成迭代器
iterators = []
for fname in temp_files:
    f = open(fname, 'rb')
    iterators.append(pickle.load(f).__iter__())

# 用heapq.merge归并多个有序迭代器
sorted_dict = {}
for val, key in heapq.merge(*iterators):
    sorted_dict[key] = val

# 清理临时文件
for fname in temp_files:
    os.unlink(fname)

这种方法的内存峰值仅为单个批次的大小，完全适配剩余20-25GB的内存空间，适合超大规模字典的排序需求。

3. 优化版pop()手动排序 #

如果你倾向于用pop()的思路，可以结合选择排序的思路，但效率较低（O(n²)），仅适合对效率要求不高的场景：

sorted_dict = {}
while x:
    # 找到当前值最小的键
    min_key = min(x, key=x.get)
    sorted_dict[min_key] = x.pop(min_key)

但这种方法的时间复杂度远高于前两种，不建议用于10^8级别的数据量。

内容的提问来源于stack exchange，提问作者user15555955