就地对字典进行排序

如何就地对字典进行排序？它没有像这样的排序方法list.sort?

d = {3: 'three', 1: 'one', 2: 'two'}
tmp = dict(sorted(d.items()))
d.clear()
d.update(tmp)

想要这样的结果 ^ 但应该就地正确，即不使用双倍内存。对同一对象的其他引用应该会看到重新排序！

没有办法做到这一点。字典现在是保留顺序的，但只是保留 - 它们并不是为了支持复杂的顺序操作操作而设计的。

导致保留顺序的字典的字典实现更改从根本上来说在它可以支持的顺序操作类型方面非常有限。字典的哈希表将索引存储到一个密集的条目数组中，正是这个数组维护了字典的元素顺序。

在不使哈希表失效的情况下，密集数组不能任意重新排序。出于冲突解决的目的，即使删除条目也必须在其位置上留下虚拟标记，并且如果不重建完整的哈希表，则无法重用该条目的位置。

即使您尝试通过删除和替换条目来执行某种低效的手动排序，您也会积累虚拟数据并触发哈希表重建，从而消耗您不想使用的额外内存。这是一个简单的演示：

import os

os.system(f'grep VmPeak /proc/{os.getpid()}/status')

x = dict.fromkeys(range(2**16))

os.system(f'grep VmPeak /proc/{os.getpid()}/status')

for i in range(2**16):
    if i == 21845:
        os.system(f'grep VmPeak /proc/{os.getpid()}/status')
    k = next(iter(x))
    x[k] = x.pop(k)
    if i == 21845:
        os.system(f'grep VmPeak /proc/{os.getpid()}/status')

os.system(f'grep VmPeak /proc/{os.getpid()}/status')

Output:

VmPeak:    15092 kB
VmPeak:    20224 kB
VmPeak:    20224 kB
VmPeak:    24832 kB
VmPeak:    24832 kB

我们不使用实际的排序（这会消耗额外的内存或花费大量额外的时间），而是使用已经排序的字典并重复提取顺序中的第一个键并将其放置在顺序的末尾，以匹配访问模式将执行删除和替换排序来对该字典进行排序。当我们达到字典重建的阈值时，由于需要分配字典内部数据结构的第二个副本，峰值内存使用量立即跳跃。