预分配一个空列表

Question

假设您想编写一个函数，该函数生成一个对象列表，并且您预先知道这种列表的长度n。

在Python中，列表支持 O(1) 的索引访问，因此预先分配列表并使用索引访问它可能是个好主意，而不是分配一个空列表并使用 append() 方法。 这是因为我们避免了如果空间不足而扩展整个列表的负担。

如果我正在使用Python，则性能在任何情况下都可能不那么重要，但是预先分配列表的更好方法是什么？

我知道这些可能成为备选项：

- [None] * n → 分配两个列表 - [None for x in range(n)] 或者使用 Python2 中的 xrange → 构建另一个对象

其中一个比另一个显着更好吗？

如果我们处于 n=len(input) 的情况怎么办？由于 input 已经存在，是否 [None for x in input] 相对于 [None] * len(input) 有更好的性能？

- Dacav

---

你是对的，这不太可能成为你的性能限制因素。 - Corley Brigman

如果你遇到了性能问题，那就对你的代码进行分析。瓶颈往往不在你想象的地方。 - Max Noel

请参见https://dev59.com/XEzSa4cB1Zd3GeqPno0p。 - naught101

Answer 1

当您向列表中添加一个项目时，Python会进行“过度分配”，请参见列表对象的source-code。这意味着例如当向包含8个项目的列表中添加1个项目时，它实际上会为8个新项目腾出空间，并仅使用其中的第一个。接下来的7个添加操作就是“免费”的。

在许多语言中（例如旧版本的Matlab，新的JIT可能更好），您总是被告知需要预先分配向量，因为在循环期间进行追加非常昂贵。在最坏的情况下，将单个项目附加到长度为n的列表中的附加成本可以达到O(n)，因为您可能必须创建一个更大的列表并复制所有现有项目。如果您需要在每次迭代中执行此操作，则添加n个项的总成本为O(n^2)，痛苦。 Python的预分配方案将数组增长的成本分散到许多单个附加中（请参见摊销成本），从而有效地使单个附加的成本为O(1)，并且添加n项的总成本为O(n)。

此外，您的Python代码的开销通常非常大，可以通过预先分配获得微小的加速效果，这种效果微不足道。因此，在大多数情况下，只需忘记预分配，除非您的分析器告诉您向列表追加是瓶颈。

其他答案展示了一些关于预分配列表的性能分析，但这是无用的。唯一重要的是对你的完整代码进行分析，包括循环内所有计算，有或没有预分配。如果我的预测是正确的，那么差别是如此之小，以至于你节省的计算时间被花费在思考、编写和维护额外代码行的时间所淹没。

- Bas Swinckels

---

源代码提到了增长模式“0，4，8，16，25，35，46，58，72，88，...”，因此它可能是二次的（或者你该怎么称之），而不是指数的。 - Bas Swinckels

我的误解...不记得在哪里读到的了。我会删除这条评论。 - Corley Brigman

它是指数级的，只是非常缓慢。主要的增长率是(1.125)^k，但增长往往会被注释中显示的固定贡献(+3/+6)所主导。 - marshall.ward

Answer 2

在这两种选择之间，第一种显然更好，因为没有涉及Python的循环。

>>> %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

- Ashwini Chaudhary

---

一些非常好的答案。我接受了这个答案，因为它实际提供了一些数据，而且还提出了将方法保存到变量中的有趣想法。我也点赞了其他答案。 - Dacav

你使用“_”作为变量名称有特别的原因吗？ - naught101

@naught101 没有特别的原因。 - Ashwini Chaudhary

@AshwiniChaudhary 我不明白这个。为什么将方法保存到变量中会更快？ - not2qubit

动态扩展类似数组的数据结构，其元素存储在连续的内存位置中，可能会静默地重新定位数据，从而使持有指向数据的指针的变量失效。因此，L=[]后跟一系列L.append()调用会带来麻烦。 - undefined

Answer 3

显然，第一个版本。让我解释一下为什么。

1. When you do [None] * n, Python internally creates a list object of size n and it copies the the same object (here None) (this is the reason, you should use this method only when you are dealing with immutable objects) to all the memory locations. So memory allocation is done only once. After that a single iteration through the list to copy the object to all the elements. list_repeat is the function which corresponds to this type of list creation.

   # 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;
   }
   

2. When you use a list comprehension to build a list, Python cannot know the actual size of the list being created, so it initially allocates a chunk of memory and a fresh copy of the object is stored in the list. When the list grows beyond the allocated length, it has to allocate the memory again and continue with the new object creation and storing that in the list.

- thefourtheye