预先分配无列表 [英] Pre-allocating a list of None

问题描述

假设你想编写一个产生一个对象列表的函数，并提前知道这个列表的长度 n 。

在python中，列表支持O（1）中的索引访问，因此可以预先分配列表并使用索引访问它，而不是分配空列表并使用 append（）方法。这是因为如果空间不够，我们可以避免扩展整个列表的负担。

如果我使用python，可能性能在任何情况下都不相关但是，预先分配列表的方法是什么？

我知道这些可能的候选人：

• [无] * n →分配两个列表


• [无for x在范围（n）] - 或 xrange 在python2→建立另一个对象

一个明显好于另一个？

如果我们在这种情况下，如果 n = len（input） ？由于输入已经存在， [无输入中的x] 具有更好的性能w.r.t. [无] * len（输入）？

解决方案

两个选项第一个显然更好，因为没有涉及到Python for循环。

 >>> ％timeit [无] * 100 
 1000000循环，最佳3：469 ns每循环
>>> ％timeit [范围（100）中的x无] 
 100000循环，最好3：4.8 us每循环
  

更新：

而 list.append 也是一个href =https://wiki.python.org/moin/TimeComplexity#list> O（1）复杂性，它可能会更好如果您将 list.append 方法分配给变量，则选择比预创建列表。

 >>> n = 10 ** 3 
>>>> %% timeit 
 lis = [None] * n 
 for _ in range（n）：
 lis [_] = _ 
 ... 
 10000循环，最好的3：73.2 us per loop 
>>>> %% timeit 
 lis = [] 
 for _ in range（n）：
 lis.append（_）
 ... 
 10000循环，最好是3 ：92.2 us per loop 
>>> %% timeit 
 lis = []; app = lis.append 
 for _ in range（n）：
 app（_）
 ... 
 10000循环，最好3：59.4我们每循环
 
>>>> n = 10 ** 6 
>>>> ％n timeit 
 lis = [None] * n 
 for _ in range（n）：
 lis [_] = _ 
 ... 
 10个循环，最佳3：106 ms每循环
>>>> %% timeit 
 lis = [] 
 for _ in range（n）：
 lis.append（_）
 ... 
 10循环，最好是3 ：每循环122 ms 
>>> %% timeit 
 lis = []; app = lis.append 
 for _ in range（n）：
 app（_）
 ... 
 10个循环，最好3：每循环91.8 ms 
  

Suppose you want to write a function which yields a list of objects, and you know in advance the length n of such list.

In python the list supports indexed access in O(1), so it is arguably a good idea to pre-allocate the list and access it with indexes instead of allocating an empty list and using the append() method. This is because we avoid the burden of expanding the whole list if the space is not enough.

If I'm using python, probably performances are not that relevant in any case, but what is the better way of pre-allocating a list?

I know these possible candidates:

• [None] * n → allocating two lists
• [None for x in range(n)] — or xrange in python2 → building another object

Is one significantly better than the other?

What if we are in the case n = len(input)? Since input exists already, would [None for x in input] have better performances w.r.t. [None] * len(input)?

解决方案

In between those two options the first one is clearly better as no Python for loop is involved.

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

Update:

And list.append has an O(1) complexity too, it might be a better choice than pre-creating list if you assign the list.append method to a variable.

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

这篇关于预先分配无列表的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！