TA貢獻(xiàn)2051條經(jīng)驗(yàn) 獲得超10個(gè)贊
沒(méi)有辦法做到這一點(diǎn)。字典現(xiàn)在是訂單保留，但只是保留 - 它們并非旨在支持復(fù)雜的訂單操作操作。
導(dǎo)致順序保留字典的字典實(shí)現(xiàn)更改從根本上說(shuō)在它可以支持的順序操作類(lèi)型方面非常有限。dict 的哈希表將索引存儲(chǔ)到一個(gè)密集的條目數(shù)組中，正是這個(gè)數(shù)組維護(hù)了 dict 的元素順序。
密集數(shù)組不能在不使哈希表失效的情況下任意重新排序。為了解決沖突，即使刪除條目也必須在其位置留下一個(gè)虛擬標(biāo)記，并且如果沒(méi)有完整的哈希表重建，該條目的位置就不能被重用。
即使您嘗試通過(guò)刪除和替換條目來(lái)執(zhí)行某種低效的手動(dòng)排序，您也會(huì)積累虛擬變量并觸發(fā)哈希表重建，從而消耗您不想使用的額外內(nèi)存。這是一個(gè)快速而骯臟的演示：
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
代替實(shí)際的排序（這會(huì)消耗額外的內(nèi)存或花費(fèi)大量額外的時(shí)間），我們使用已經(jīng)排序的 dict 并重復(fù)提取順序中的第一個(gè)鍵并將其放在順序的末尾，匹配訪(fǎng)問(wèn)模式將執(zhí)行刪除和替換排序來(lái)對(duì)此字典進(jìn)行排序。當(dāng)我們達(dá)到 dict 重建的閾值時(shí)，由于需要分配 dict 內(nèi)部數(shù)據(jù)結(jié)構(gòu)的第二個(gè)副本，峰值內(nèi)存使用量立即跳躍。
TA貢獻(xiàn)1842條經(jīng)驗(yàn) 獲得超22個(gè)贊
從技術(shù)上講，您可以對(duì)鍵進(jìn)行排序，然后pop重新插入值。這樣，對(duì)同一對(duì)象的其他引用也將看到更改。但是，它不會(huì)使您免于額外的內(nèi)存使用。
for key in sorted(d):
d[key] = d.pop(key)
根據(jù) dict 的負(fù)載因子，這可能會(huì)觸發(fā)相當(dāng)多的哈希表重建，從而減慢計(jì)算速度，如下例所示：
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)
舉報(bào)