为什么字典在删除后不重新调整大小？

Question

为什么字典在删除后不重新调整大小？

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

根据我所发现的SO上的一个问题，set的行为方式类似，这是符合字典的预期的。

另一方面，当新大小变为已分配大小的一半时，list会调整大小；这在list_resize注释中有说明：

/* 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。

- Dimitris Fasarakis Hilliard

1

哪个版本？全部吗？ - cs95

@cᴏʟᴅsᴘᴇᴇᴅ 是的，这就是为什么我没有添加任何特定版本的标签的原因。 :-) - Dimitris Fasarakis Hilliard

d.clear() 会重新调整大小。 - Jean-François Fabre

是的...对于“为什么”的答案涉及到一些推测 - 显然，作者们认为实现它所需的复杂性和由此产生的性能影响不值得其带来的好处。 - cs95

这是由于分期偿还。只有在删除多达一半的元素时才更改大小，并在先前的内存分配变满时添加两倍的内存。它有助于减少反复分配内存的总体操作成本。由于列表中有连续的内存。因此，如果我们在每次插入时调整列表大小，它将变得过于昂贵，因此如果现有分配的内存变满，则现有列表的大小仅加倍。删除使用相同的策略。 - Rajan Chauhan

4

@RajanChauhan说：我觉得你漏了些东西。列表和字典都使用调整大小策略来平摊调整大小的成本，但是字典在删除时不会调整大小。问题是为什么字典在删除时不进行调整大小，而不是关于平摊成本的策略。 - user2357112

1个回答

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- user2357112 · Accepted Answer

这在Objects/dictnotes.txt中得到了一定的解释。该文件是字典实现的附属文件，包含各种注释：

仅涉及单个键的字典操作可以是O(1)，除非需要调整大小。通过仅在字典可以增长（并且可能需要调整大小）时检查调整，其他操作仍然是O(1)，并且减少了调整大小或内存碎片化的可能性。特别是，通过重复调用.pop来清空字典的算法将不会看到调整大小，这可能根本不必要，因为字典最终将被完全丢弃。

一个重要的考虑因素是收缩列表缓冲区非常容易，而收缩字典的内部哈希表是一个更加复杂的操作。