预分配一个None的列表

19 投票

3 回答

15022 浏览

数据工程师

提问于 2025-04-17 21:07

假设你想写一个函数，这个函数会生成一个对象的列表，而且你已经知道这个列表的长度 n。

在Python中，列表可以通过索引快速访问，时间复杂度是O(1)，所以提前分配好列表并通过索引访问是个不错的主意。这样做的好处是，如果空间不够，我们就不需要扩展整个列表，避免了不必要的开销。

虽然在Python中，性能可能不是特别重要，但提前分配列表的更好方法是什么呢？

我知道有以下几种方法：

[None] * n → 这种方法会分配两个列表
[None for x in range(n)] — 或者在Python2中用 xrange → 这种方法会构建另一个对象

这两种方法有哪个明显更好吗？

如果我们在 n = len(input) 的情况下呢？因为 input 已经存在了，使用 [None for x in input] 的性能会比 [None] * len(input) 更好吗？

性能优化数据结构内存管理时间复杂度空间复杂度索引访问列表预分配对象生成

3 个回答

显然，第一种方式更好。让我来解释一下原因。

当你使用 [None] * n 时，Python 在内部会创建一个大小为 n 的列表对象，并且它会把同一个对象（这里是 None）复制到所有的内存位置。这就是为什么你应该只在处理不可变对象时使用这种方法的原因。所以内存分配只进行一次。之后，它只需要遍历一次列表，把这个对象复制到所有的元素上。对应这种列表创建方式的函数是 list_repeat。
```
# Creates the list of specified size
np = (PyListObject *) PyList_New(size);
....
...
items = np->ob_item;
if (Py_SIZE(a) == 1) {
    elem = a->ob_item[0];
    for (i = 0; i < n; i++) {
        items[i] = elem;       // Copies the same item
        Py_INCREF(elem);
    }
    return (PyObject *) np;
}
```
而当你使用列表推导式来构建列表时，Python 无法知道要创建的列表的实际大小，所以它最开始会分配一块内存，并在列表中存储一个新的对象副本。当列表的大小超过了最初分配的长度时，它就需要重新分配内存，并继续创建新的对象并将其存储在列表中。

回答于 2025-04-17 由 Python大师

分享举报

当你往一个列表里添加一个项目时，Python会提前分配一些空间。你可以查看列表对象的源代码。这意味着，比如说你往一个有8个项目的列表里再加1个项目，实际上它会为8个新项目腾出空间，但只用到其中的第一个。接下来的7次添加就相当于“免费”的。

在很多编程语言中（比如旧版本的Matlab，新的JIT可能会更好），你总是被告知需要提前分配你的向量，因为在循环中添加项目的成本很高。在最坏的情况下，往一个长度为n的列表中添加一个项目可能需要O(n)的时间，因为你可能需要创建一个更大的列表，并把所有现有的项目复制过去。如果你在每次循环中都这样做，添加n个项目的总成本就会变成O(n^2)，这可真是太贵了。Python的提前分配方案把扩展数组的成本分摊到很多次单独的添加中（可以参考摊销成本），这样单次添加的成本就变成了O(1)，而添加n个项目的总成本则是O(n)。

此外，你的Python代码其他部分的开销通常很大，因此通过提前分配获得的微小速度提升几乎可以忽略不计。所以在大多数情况下，除非你的性能分析工具告诉你添加列表的操作是瓶颈，否则就忘了提前分配这件事吧。

其他回答展示了一些关于列表预分配的性能分析，但这其实没什么用。最重要的是分析你完整的代码，看看在循环中所有计算的情况下，有没有提前分配的影响。如果我的预测是对的，差别会小到几乎不值得一提，考虑、编写和维护那些额外的提前分配代码所花的时间，可能比你节省的计算时间还要多。

回答于 2025-04-17 由 Python大师

分享举报

在这两个选项之间，第一个显然更好，因为它没有使用Python的for循环。

>>> %timeit [None] * 100
1000000 loops, best of 3: 469 ns per loop
>>> %timeit [None for x in range(100)] 
100000 loops, best of 3: 4.8 us per loop

更新：

而且，list.append的时间复杂度也是O(1)，如果你把list.append这个方法赋值给一个变量，那么它可能比提前创建列表更好。

>>> n = 10**3
>>> %%timeit
lis = [None]*n           
for _ in range(n):
    lis[_] = _
... 
10000 loops, best of 3: 73.2 us per loop
>>> %%timeit
lis = []                 
for _ in range(n):
    lis.append(_)
... 
10000 loops, best of 3: 92.2 us per loop
>>> %%timeit
lis = [];app = lis.append
for _ in range(n):
    app(_)
... 
10000 loops, best of 3: 59.4 us per loop

>>> n = 10**6
>>> %%timeit
lis = [None]*n
for _ in range(n):
    lis[_] = _
... 
10 loops, best of 3: 106 ms per loop
>>> %%timeit
lis = []      
for _ in range(n):
    lis.append(_)
... 
10 loops, best of 3: 122 ms per loop
>>> %%timeit
lis = [];app = lis.append
for _ in range(n):
    app(_)
... 
10 loops, best of 3: 91.8 ms per loop

回答于 2025-04-17 由 Python大师

分享举报

预分配一个None的列表

3 个回答

撰写回答