如何在不创建临时副本的情况下按值对字典进行排序?

Question

我有一个字典，我需要按键排序。我身体上没有足够的内存来做这件事。

x = dict(sorted(x.items(), key=lambda item: item[1])

是否有一种方法可以对它进行排序，而不会在内存使用中产生暂时的峰值?我想我也许可以使用pop()，从原始的中删除项目，以保持内存中相同数量的数据?但我不知道是否有更简单的方法。

我的字典大约有10^8个对象，占用了大约100gb。我有大约20- 25gb的空闲内存。

Answer 1

不是没有额外的空间，但要少得多，所以可能对您或其他有相同问题的人仍然有用。10^5项的内存测量(峰值字节):

12,059,636 baseline
24,408,256 original
19,065,304 better 1
18,709,352 better 2
14,265,296 sort keys, sort vals
12,949,792 sort keys, sort vals 2

baseline用于创建原始字典。您的original溶液在额外的12.3 MB处达到峰值。我的最佳替代方案在额外的0.9 MB处达到峰值。

代码(在线试用!):

import tracemalloc as tm
from random import random
import gc
n = 10**5
def start(label):
global x, label_
label_ = label
gc.collect()
tm.start()
x = {random(): random() for _ in range(n)}
def stop():
global x
print(f'{tm.get_traced_memory()[1]:10,}', label_)
tm.stop()
if label_ != 'baseline':
assert len(x) == n
assert list(x.values()) == sorted(x.values()), list(x.values())
del x
gc.collect()
for _ in range(2):
start('baseline')
stop()
start('original')
x = dict(sorted(x.items(), key=lambda item: item[1]))
stop()
start('better 1')
x = list(x.items())
x.sort(key=lambda item: item[1])
x = dict(x)
stop()
start('better 2')
ks = list(x)
ks.sort(key=x.get)
x = dict(zip(ks, map(x.pop, ks)))
stop()
start('sort keys, sort vals')
keys = list(x)
keys.sort(key=x.get)
vals = list(x.values())
del x
vals.sort()
x = dict(zip(keys, vals))
stop()
start('sort keys, sort vals 2')
keys = list(x)
keys.sort(key=x.get, reverse=True)
vals = list(x.values())
del x
vals.sort(reverse=True)
x = {}
while keys:
x[keys.pop()] = vals.pop()
stop()
print()

Answer 2

您可能不希望在此用例中使用字典，因为尽管现代Python中的字典保持其顺序，但它们并不是真正为排序而构建的。

事实上，如果你没有足够的内存来为这个数据做一个额外的拷贝(甚至只是对它的引用)，你可能甚至不希望它以任何形式都在内存中。考虑将这些数据移到一个数据库中，该数据库将支持程序其余部分所需的任何操作，而不必将所有数据加载到内存中。 也就是说，如果你需要对字典进行排序，但又不消耗与字典大小成比例的空间，那么弹出条目并按顺序重新添加它们(即选择排序)似乎是一种方法;更有效的排序算法通常依赖于任意交换或重新排序项的能力(这在字典中是做不到的)，或者对数据子集进行临时复制(我们假设在我们的空间限制下不能这样做)。不幸的是，选择排序有O(N^2)的时间复杂度，但它确实有理想的O(1)的空间复杂度。

def inplace_dict_sort(d: dict) -> None:
def swap(i):
return i[1], i[0]
k, v = min(d.items(), key=swap)
while True:
d[k] = d.pop(k)
try:
k, v = min((i for i in d.items() if swap(i) > (v, k)), key=swap)
except ValueError:
return
d = {'a': 'foo', 'b': 'bar', 'c': 'foo', 'd': 'qux', 'e': 'ola'}
inplace_dict_sort(d)
print(d)
# {'b': 'bar', 'a': 'foo', 'c': 'foo', 'e': 'ola', 'd': 'qux'}