list()比列表理解使用更多的内存

Question

所以我正在玩list对象,并发现一些奇怪的事情,如果list创建list()它使用更多的内存,而不是列表理解？我正在使用Python 3.5.2

In [1]: import sys
In [2]: a = list(range(100))
In [3]: sys.getsizeof(a)
Out[3]: 1008
In [4]: b = [i for i in range(100)]
In [5]: sys.getsizeof(b)
Out[5]: 912
In [6]: type(a) == type(b)
Out[6]: True
In [7]: a == b
Out[7]: True
In [8]: sys.getsizeof(list(b))
Out[8]: 1008

来自文档:

列表可以通过以下几种方式构建:

• 使用一对方括号表示空列表: []
• 使用方括号,用逗号分隔项目:[a],[a, b, c]
• 使用列表理解: [x for x in iterable]
• 使用类型构造函数:list()或list(iterable)

但似乎使用list()它会占用更多内存.

而且list越大越好,差距就越大.

为什么会这样？

更新#1

使用Python 3.6.0b2进行测试:

Python 3.6.0b2 (default, Oct 11 2016, 11:52:53) 
[GCC 5.4.0 20160609] on linux
Type "help", "copyright", "credits" or "license" for more information.
>>> import sys
>>> sys.getsizeof(list(range(100)))
1008
>>> sys.getsizeof([i for i in range(100)])
912

更新#2

使用Python 2.7.12进行测试:

Python 2.7.12 (default, Jul  1 2016, 15:12:24) 
[GCC 5.4.0 20160609] on linux2
Type "help", "copyright", "credits" or "license" for more information.
>>> import sys
>>> sys.getsizeof(list(xrange(100)))
1016
>>> sys.getsizeof([i for i in xrange(100)])
920

Answer 1

我认为你看到过度分配模式这是来自源的样本:

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

Answer 2

谢谢大家帮助我理解那个令人敬畏的Python.

我不想提出那么大的问题(这就是我发布答案的原因),只是想展示和分享我的想法.

正如@ReutSharabani正确指出:"list()确定性地确定列表大小".您可以从该图表中看到它.

当您append或使用列表理解时,您总是会遇到某种边界,当您达到某个点时,这些边界会延伸.并且list()你有几乎相同的界限,但它们是浮动的.

UPDATE

感谢@ReutSharabani,@ atavo,@ SmithFestersen

总结一下:list()预分配内存取决于列表大小,列表理解不能这样做(它在需要时请求更多内存,如.append()).这就是list()存储更多内存的原因.

还有一个图表,显示list()预分配内存.因此绿线显示list(range(830))逐个元素追加,一段时间内存不变.

更新2

作为@Barmar在评论中所指出的下方,list()必须我比列表理解快,于是我就timeit()用number=1000了长度list从4**0到4**10,结果是