2017-08-02 86 views
8

顯然刪除字典中的條目不會觸發任何調整大小。只有在添加條目後纔會觸發調整大小。爲什麼字典沒有在刪除後調整大小?

這可以從下面可以看出:

# Drastic example, nobody does such 
# things with dicts FWIK 
from sys import getsizeof 

d = {i:i for i in range(100)} 
print(getsizeof(d)) # 4704 
for i in range(100): 
    del d[i] # similarly with pop 
print(getsizeof(d)) # 4704 
d[0] = 1 # triggers resize 

以及來自a question on SO(從我所發現的)。 set以類似的方式表現出來,預計這將符合什麼樣的標準。另一方面,當新大小變成已分配的一半時,調整大小;這是在list_resize comment說:

/* Bypass realloc() when a previous overallocation is large enough 
    to accommodate the newsize. If the newsize falls lower than half 
    the allocated size, then proceed with the realloc() to shrink the list. 
*/ 

爲什麼是它的字典(並間接套)不採用類似的技巧,而是等待一個新條目被插入?描述的行爲適用於Python 2.7和3.x(直到Python 3.7.0a0)。

+1

哪個版本?所有? –

+0

@cᴏʟᴅsᴘᴇᴇᴅ是。這就是爲什麼我沒有添加任何特定於版本的標籤。 :-) –

+0

'd.clear()'確實調整了大小,儘管 –

回答

12

這在一定程度上Objects/dictnotes.txt解釋的,包含在字典執行各種音符伴隨文件:

僅涉及單個密鑰字典操作可以是O(1)除非 調整大小是可能的。通過僅在 字典可以增長(並且可能要求調整大小)時檢查調整大小,其他操作 保持O(1),並且減小調整大小抖動或內存碎片 的機率。特別是,通過重複調用.pop清空字典 的算法將看不到調整大小,根本不需要調整大小,因爲字典最終完全被丟棄 。

一個重要的考慮是縮小列表的緩衝區非常簡單,而縮小字典的內部哈希表是一個非常複雜的操作。

+0

爲了補充這一點,似乎很明顯,作者們對這樣一個事實進行了對衝,即刪除調整大小不會帶來任何實際好處,除非在這種情況下大量的項目被刪除,因此假定字典最終將被丟棄。 –

+0

我掩蓋了這些代碼,完全錯過了*調整抖動或內存碎片*,我需要睡眠。謝謝。順便說一句:任何想法是什麼調整顛簸是什麼? –

+1

@JimFasarakisHilliard:一遍又一遍地調整大小。對列表來說,這也是一個問題,但他們似乎已經決定權衡交易的方式是用於詞典和用於列表的其他方式,這可能是由於字典大小調整的比較費用或他們在實踐中使用他們想法的字典和列表的方式。 – user2357112

相關問題