为什么list（）和[]之间的getsizeof结果不同

Question

工作时，我注意到一件奇怪的事：

from sys import getsizeof as gs

list1=[1]
list2=list([1])

list1==list2 #true
gs(list1)    #80.  (I guess 72 overhead +8 of the int)
gs(list2)    #104. (I guess 72 + 8 as above + 24 of...?)


list3=[1,2,3,4,5]
list4=list(list3)

gs(list3)    #112
gs(list4)    #136

所以总是有24个字节的差异，我真的不明白它们是从哪里来的。你知道吗

当然，这和内部结构有关，但有人能解释一下引擎盖下面发生了什么吗？你知道吗

Answer 1

TL；DR：列出over-allocate，以便它们可以提供摊销常量时间（O(1)）追加操作。过度分配的数量取决于列表的创建方式和实例的追加/删除历史记录。列表文本总是预先知道大小，并且不会过度分配（或者只是稍微分配）。list函数并不总是知道结果的长度，因为它必须迭代参数，所以最终的过度分配取决于所使用的（依赖于实现的）过度分配方案。你知道吗

要理解我们所看到的内容，必须知道sys.getsizeof只报告实例的大小。它不查看实例的内容。因此内容的大小（在本例中是ints）没有考虑在内。

实际影响列表大小的因素是（假设为64位系统）：

• 8字节：引用计数。你知道吗
• 8字节：指向类的指针。你知道吗
• 8字节：存储列表中元素的数量（相当于len(your_list)）。你知道吗
• 8字节：存储保存列表中元素的数组的大小（这是len(your_list) + over_allocation）。你知道吗
• 8字节：指向存储指向内容的指针的数组的指针。你知道吗

• 列表的每个插槽8字节：保存指向列表中每个元素的指针（或NULL）。

• 24字节：其他东西需要（我认为是垃圾收集）

这个解释可能有点难以理解，所以如果我添加一些图像（忽略用于垃圾收集的额外24字节），可能会更清楚。我根据我在cpython3.7.2windows64位上的发现创建了它们，python64位来自Anaconda。你知道吗

无过度分配，例如mylist = [1,2,3]：

对于过度分配，例如mylist = list([1,2,3])：

或手动appends：

mylist = []
mylist.append(1)
mylist.append(2)
mylist.append(3)

这意味着一个空列表已经占用64字节，假设空列表没有过度分配。对于添加的每个元素，必须添加对Python对象的另一个引用（指针是8字节）。你知道吗

所以list的最小大小是：

size_min = 64 + 8 * n_items

Python列表的大小是可变的，如果它只分配同样多的空间来容纳当前数量的项，那么每当添加新项时，就必须复制整个数组（使之成为O(n)）。但是，如果您过度分配了内存，这意味着您实际占用的内存超过了存储元素所需的内存，那么您可以支持摊销O(1)追加，因为它只需要有时调整大小。参见示例Wikipedia "Amortized analysis"。你知道吗

下一点是，文本总是知道它的大小，你在文本中放入x项，在源代码解析时，它已经知道列表的大小。因此，您可以简单地为以下内容分配所需的内存：

l = [1, 2, 3]

然而，由于list是一个可调用的函数，即使参数只是一个文本（我的意思是您可以为名称list分配一些不同的内容），Python也不会优化该调用，因此它必须真正调用list。你知道吗

list本身只是对参数进行迭代，并将项附加到它的内部数组中，在需要时调整大小并过度分配以使其分摊O(1)。list可以检查输入的大小，但由于（理论上）迭代对象时可能发生任何事情，因此它将长度估计作为粗略的准则，而不是保证。因此，虽然它可以避免重新分配，如果它可以预测参数中的项数，它仍然会过度分配（以防万一）。你知道吗

请注意，所有这些都是实现细节，在其他Python实现中可能完全不同，甚至在不同的CPython版本中也是如此。Python唯一能保证的（我想它能做到，我不是100%肯定）是append是分摊的O(1)，而不是它是如何实现的以及列表实例需要多少内存。你知道吗