Python列表内存重新分配问题

Question

Python列表内存重新分配问题

3

如果我使用C-Python或jython（在Python 2.7中），对于列表（[]）数据结构，如果我不断添加新元素，是否会出现内存重新分配问题，就像Java ArrayList一样（因为Java ArrayList需要连续的内存空间，如果当前预先分配的空间已满，则需要重新分配新的更大的连续大内存空间，并将现有元素移动到新分配的空间中）？

链接：http://grepcode.com/file/repository.grepcode.com/java/root/jdk/openjdk/6-b14/java/util/ArrayList.java#ArrayList.ensureCapacity%28int%29 问候，林

- Lin Ma

1

CPython中的列表是作为数组列表实现的，但是append操作的摊销时间是常数时间。请参见此处。 - juanpa.arrivillaga

1

如果你能读懂C语言，那么你应该看看CPython源码listobject.c。持有Python列表项指针的结构成员是ob_item。当列表增长时，ob_item可能会被重新分配，旧的项被复制，但这是在C级别进行的，所以速度很快。当然，Python列表对象本身的内存位置并不会受到影响。 - PM 2Ring

@juanpa.arrivillaga，在阅读后对“摊销”这个词感到困惑，你能再解释一下吗？ - Lin Ma

@PM2Ring，如果由于无法找到连续的内存块而无法进行扩展，则会执行重量级的重新分配操作——即移动到新位置需要O(n)时间（其中n是列表中元素的数量）？ - Lin Ma

1

正如我之前所说，任何所需的复制都是在 C 级别进行的，因此比 Python 的 for 循环快得多。请记住，现代 CPU 对于复制数组具有高效的操作码。 - PM 2Ring

@PM2Ring，我只是想确认一下是否发生了重新分配和移动所有元素，因为当我处理大量数据（1-2G）加载到列表中时，我遇到了这样的问题。 - Lin Ma

2个回答

1

在Python内部，列表是指针数组，如hpaulj所述。

接下来的问题是如何扩展C中的数组，如answer所解释的那样。它解释了可以使用C中的realloc函数来完成这个操作。

这引导我研究realloc的行为，它提到：

该函数可能会将内存块移动到一个新的位置（函数返回其地址）。

从这里我理解到，如果连续的内存可用，那么数组对象就会被扩展，否则内存块（包含数组对象而不是列表对象）将被复制到新分配的更大的内存块中。

这是我的理解，如果我错了，欢迎指正。

- shanmuga

谢谢 Shanmuga，假设由于找不到连续的内存块而无法进行扩展，并且移动到新位置需要 O(n) 的时间（n 是列表中元素的数量）？ - Lin Ma

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

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

- hpaulj · Accepted Answer

基本故事，至少对于主要的Python来说，是列表包含指向内存中其他位置的对象的指针。该列表创建时具有一定的自由空间（例如8个指针）。当它填满时，它会分配更多的内存，依此类推。它是否将指针从一个内存块移动到另一个内存块，这是大多数用户忽略的细节。在实践中，我们只是根据需要附加/扩展列表，不用担心内存使用。

为什么从列表创建列表会使其变大？

我假设jython使用相同的方法，但您必须深入其代码以了解其如何转换为Java。

我主要回答numpy问题。这是一个创建固定大小的多维数组的数字包。如果用户需要逐步构建这样的数组，我们通常建议他们从列表开始并附加值。最后，他们创建数组。附加到列表比多次重建数组要便宜得多。