"growing"(追加到)序列对象

Question

在Matlab中，建议不要使用这种类型的算法("growing arrays")

mine = []
for i=1:100,
    mine = [mine,randn(1)]
end

然而似乎Python的许多示例都显示了这种算法(尽管这是一个非常糟糕的示例):

import numpy.random as rand
mine = []
for i in range(100):
    mine.append(rand.random(1)[0])

我想知道这是为什么——有什么区别?

Answer 1

区别在于:

• 在MATLAB中，循环的每次迭代都重新分配矩阵以增加大小1，并将整个内容复制到新分配的空间中。
• Python列表不会这样工作。在任何给定点分配的空间都比需要的要多，并且分配的空间以保证在平摊常数时间内完成追加操作的方式增长。

话虽如此，我认为差异主要是文化上的:

• 在MATLAB中使用大型数值矩阵是很常见的，并且每次一个元素(或一行/列)增长这样的矩阵确实会很昂贵。
• 另一方面，没有人会使用Python列表(或列表的列表)来表示一个大矩阵:这将非常慢，并且会占用非常少的内存。将使用Numerical Python的ndarray，而ndarray将提供与MATLAB矩阵完全相同的权衡。

Answer 2

在Matlab中附加到数组显然是非常低效的(它在二次时间内运行)，而在python中相应的列表操作更加高度优化。追加的次数是O(1)，直到列表满为止——此时列表的大小会翻倍以腾出更多的空间(这是一个O(n)的操作)。这意味着随着列表变长，追加操作的效率会越来越高(总效率是O(1)平摊)。这些类型的优化可能也可以在Matlab中实现，但似乎它们不是自动完成的。

为了更好的性能，python还有collections.deque容器类，它支持从两端有效地追加和删除(在两个方向上大约是O(1))。

Answer 3

您的MATLAB代码可以更好地编写。比较以下实现:

%# preallocation
tic
x = zeros(1,100000); for i=1:100000, x(i) = 99; end
toc
%# appending
tic
x = []; for i=1:100000, x(end+1) = 99; end
toc
%# concatenation
tic
x = []; for i=1:100000, x = [x, 99]; end
toc

我得到以下结果:

Elapsed time is  0.001844 seconds.    %# preallocated vector/matrix
Elapsed time is  0.109597 seconds.    %# appending using "end+1" syntax
Elapsed time is 35.226361 seconds.    %# appending using concatenation

请注意，以上是在R2011b上测试的，它引入了对生长矩阵的改进(没有预分配)。

您还应该检查前面的答案，以寻找结合预分配同时仍然允许动态增长的解决方案(想法是在大块大小中分配/增长)

另一方面，您应该注意到Python列表针对在末尾追加项进行了优化。如果你在开始时插入项目，你将得到非常不同的时间。例子:

>>> from timeit import timeit
>>> timeit('x.insert(0,99)', 'x=[]', number=100000)
5.3840245059078597
>>> timeit('x.append(99)', 'x=[]', number=100000)    # x.insert(len(x),99)
0.039047700196533697

Answer 4

你的两个例子并不完全相等。Matlab示例将两个列表连接到一个新列表中，每次都进行复制，而Python则将项目附加到列表中，而不会每次都进行复制。实际上，现在您可以编写与Matlab代码完全等价的Python代码，例如:

mine = mine + [newitem]

但是你不应该这样做，因为你每次都在复制一个不断增长的列表。这就是为什么列表有.append()方法(也有.extend()方法)。

出于类似的原因，Pythonistas建议您将单个字符串附加到列表中，然后对其使用``.join()，而不是通过连接来构建字符串。

顺便说一下，Python列表总是为额外的项分配空间，因此当添加新项时，它们并不总是需要增长。