你如何就地對字典進行排序？它沒有類似的排序方法list.sort？d = {3: 'three', 1: 'one', 2: 'two'}tmp = dict(sorted(d.items()))d.clear()d.update(tmp)想要這樣的結果 ^ 但應該是適當的，即不占用雙倍內存。對同一對象的其他引用應該看到重新排序！
2 回答
侃侃無極
TA貢獻2051條經驗 獲得超10個贊
沒有辦法做到這一點。字典現在是訂單保留，但只是保留 - 它們并非旨在支持復雜的訂單操作操作。
導致順序保留字典的字典實現更改從根本上說在它可以支持的順序操作類型方面非常有限。dict 的哈希表將索引存儲到一個密集的條目數組中，正是這個數組維護了 dict 的元素順序。
密集數組不能在不使哈希表失效的情況下任意重新排序。為了解決沖突，即使刪除條目也必須在其位置留下一個虛擬標記，并且如果沒有完整的哈希表重建，該條目的位置就不能被重用。
即使您嘗試通過刪除和替換條目來執行某種低效的手動排序，您也會積累虛擬變量并觸發哈希表重建，從而消耗您不想使用的額外內存。這是一個快速而骯臟的演示：
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')
輸出：
VmPeak: 15092 kB
VmPeak: 20224 kB
VmPeak: 20224 kB
VmPeak: 24832 kB
VmPeak: 24832 kB
代替實際的排序（這會消耗額外的內存或花費大量額外的時間），我們使用已經排序的 dict 并重復提取順序中的第一個鍵并將其放在順序的末尾，匹配訪問模式將執行刪除和替換排序來對此字典進行排序。當我們達到 dict 重建的閾值時，由于需要分配 dict 內部數據結構的第二個副本，峰值內存使用量立即跳躍。
茅侃侃
TA貢獻1842條經驗 獲得超22個贊
從技術上講，您可以對鍵進行排序，然后pop重新插入值。這樣，對同一對象的其他引用也將看到更改。但是，它不會使您免于額外的內存使用。
for key in sorted(d):
d[key] = d.pop(key)
根據 dict 的負載因子，這可能會觸發相當多的哈希表重建，從而減慢計算速度，如下例所示：
In [1]: def inplace(d):
...: for key in sorted(d):
...: d[key] = d.pop(key)
...:
In [2]: def create_new(d):
...: return dict(sorted(d.items()))
...:
In [3]: import math
In [4]: limit = (2/3) * 2**20
In [5]: load_factor_low = {i: i for i in range(math.ceil(limit) + 1)}
In [6]: load_factor_high = {i: i for i in range(math.floor(limit) - 1)}
In [7]: %timeit create_new(load_factor_low)
116 ms ± 1.31 ms per loop (mean ± std. dev. of 7 runs, 10 loops each)
In [8]: %timeit inplace(load_factor_low)
104 ms ± 2.19 ms per loop (mean ± std. dev. of 7 runs, 10 loops each)
In [9]: %timeit create_new(load_factor_high)
89.8 ms ± 1.45 ms per loop (mean ± std. dev. of 7 runs, 10 loops each)
In [10]: %timeit inplace(load_factor_high)
128 ms ± 1.52 ms per loop (mean ± std. dev. of 7 runs, 10 loops each)
添加回答
舉報
0/150
提交
取消