/* This over-allocates proportional to the list size, making room
* for additional growth. The over-allocation is mild, but is
* enough to give linear-time amortized behavior over a long
* sequence of appends() in the presence of a poorly-performing
* system realloc().
* The growth pattern is: 0, 4, 8, 16, 25, 35, 46, 58, 72, 88, ...
*/
new_allocated = (newsize >> 3) + (newsize < 9 ? 3 : 6);
打印长度为0-88的列表理解的大小,您可以看到模式匹配:
# create comprehensions for sizes 0-88
comprehensions = [sys.getsizeof([1 for _ in range(l)]) for l in range(90)]
# only take those that resulted in growth compared to prevIoUs length
steps = zip(comprehensions, comprehensions[1:])
growths = [x for x in list(enumerate(steps)) if x[1][0] != x[1][1]]
# print the results:
for growth in growths:
print(growth)
结果(格式为(list length, (old total size, new total size))
):
(0, (64, 96))
(4, (96, 128))
(8, (128, 192))
(16, (192, 264))
(25, (264, 344))
(35, (344, 432))
(46, (432, 528))
(58, (528, 640))
(72, (640, 768))
(88, (768, 912))
出于性能原因而进行了过度分配,从而允许列表增长而不会每次增长都分配更多的内存(更好的摊销性能)。
使用列表理解的差异的一个可能原因是列表理解不能确定性地计算所生成列表的大小,但是list()
可以。这意味着,在使用过度分配填充列表的过程中,理解力将不断增长,直到最终填充它。
一旦完成,有可能不会使用未分配的分配节点来增加过度分配缓冲区(实际上,在大多数情况下,这样做不会克服过度分配的目的)。
list()
但是,无论列表大小如何,都可以添加一些缓冲区,因为它事先知道最终的列表大小。
同样从源头获得的另一个支持证据是,我们看到列表理解正在调用LIST_APPEND
,它表示的使用list.resize
,而这又表明在不知道要填充多少预分配缓冲区的情况下消耗了预分配缓冲区。这与您看到的行为一致。
总而言之,list()
将根据列表大小预分配更多节点
>>> sys.getsizeof(list([1,2,3]))
60
>>> sys.getsizeof(list([1,2,3,4]))
64
列表理解不知道列表的大小,因此随着列表的增长,它会使用追加操作,从而耗尽了预分配缓冲区:
# one item before filling pre-allocation buffer completely
>>> sys.getsizeof([i for i in [1,2,3]])
52
# fills pre-allocation buffer completely
# note that size did not change, we still have buffered unused nodes
>>> sys.getsizeof([i for i in [1,2,3,4]])
52
# grows pre-allocation buffer
>>> sys.getsizeof([i for i in [1,2,3,4,5]])
68