时间戳

首页 > 解决方案 > 这句话是否与python范式“不应该初始化列表”相矛盾？

python - 这句话是否与python范式“不应该初始化列表”相矛盾？

问题描述

从其他编码语言到 python 的人经常问他们应该如何预分配或初始化他们的列表。对于来自 Matlab 的人来说尤其如此，其中代码为

l = []
for i = 1:100
    l(end+1) = 1;
end

返回一个警告，明确建议您初始化列表。

SO上有几篇文章解释（并通过测试显示）python中不需要列表初始化。一个经过大量讨论的好例子是这个（但列表可能很长）：Create a list with initial capacity in Python

然而，前几天，在寻找 python 中的操作复杂性时，我在官方 python wiki上偶然发现了这句话：

最大的 [列表操作成本] 来自超出当前分配大小的增长（因为一切都必须移动），

这似乎表明确实列表确实具有预分配大小，并且超过该大小会导致整个列表移动。

这有点动摇了我的基础。列表预分配能否降低代码的整体复杂性（就操作数量而言）？如果不是，那句话是什么意思？

编辑：

显然我的问题是关于（非常常见的）代码：

container = ... #some iterable with 1 gazilion elements
new_list = []
for x in container:
    ... #do whatever you want with x
    new_list.append(x) #or something computed using x

在这种情况下，编译器无法知道 中有多少项container，因此new_list如果该句子中所说的是真的，可能会要求他分配的内存更改令人难以置信的次数。

我知道这对于列表理解是不同的

标签： python

解决方案

列表预分配能否降低代码的整体复杂性（就操作数量而言）？

不，代码的整体时间复杂度将是相同的，因为重新分配列表的时间成本是 O(1)，当分摊到所有增加列表大小的操作时。

如果不是，那句话是什么意思？

原则上，通过避免多次重新分配，预先分配列表可以将运行时间减少一些常数因子。这并不意味着复杂性较低，但可能意味着代码在实践中更快。如果有疑问，请对代码的相关部分进行基准测试或分析，以比较两个选项；在大多数情况下，这无关紧要，而且当它发生时，无论如何都可能有更好的替代方案（例如 NumPy 数组）来实现相同的目标。

new_list可能需要他分配的内存改变难以置信的次数

列表重新分配遵循几何级数，因此如果列表的最终长度为n，则列表在此过程中仅重新分配 O(log n ) 次；不是“难以置信的次数”。数学计算的方式是，每个元素被复制到新的底层数组的平均次数是一个常数，无论列表有多大，因此附加到列表的 O(1) 摊销成本。

推荐阅读