这样的代码经常发生:
l = []
while foo:
# baz
l.append(bar)
# qux
如果您要向列表中添加数千个元素,这将非常缓慢,因为列表必须不断调整大小以适应新元素。
在Java中,可以创建具有初始容量的ArrayList。如果你知道你的清单有多大,这将会更有效率。
我知道这样的代码通常可以被重构成一个列表理解式。但是,如果for/while循环非常复杂,这是不可行的。对于我们Python程序员来说,是否也有类似的方法?
这样的代码经常发生:
l = []
while foo:
# baz
l.append(bar)
# qux
如果您要向列表中添加数千个元素,这将非常缓慢,因为列表必须不断调整大小以适应新元素。
在Java中,可以创建具有初始容量的ArrayList。如果你知道你的清单有多大,这将会更有效率。
我知道这样的代码通常可以被重构成一个列表理解式。但是,如果for/while循环非常复杂,这是不可行的。对于我们Python程序员来说,是否也有类似的方法?
当前回答
如果使用NumPy,就会出现Python中的预分配问题,因为NumPy有更多类似c的数组。在这种情况下,预分配关注的是数据的形状和默认值。
如果要在大量列表上进行数值计算并希望获得性能,可以考虑NumPy。
其他回答
对于某些应用程序,字典可能是您正在寻找的。例如,在find_totient方法中,我发现使用字典更方便,因为我没有零索引。
def totient(n):
totient = 0
if n == 1:
totient = 1
else:
for i in range(1, n):
if math.gcd(i, n) == 1:
totient += 1
return totient
def find_totients(max):
totients = dict()
for i in range(1,max+1):
totients[i] = totient(i)
print('Totients:')
for i in range(1,max+1):
print(i,totients[i])
这个问题也可以用预分配的列表来解决:
def find_totients(max):
totients = None*(max+1)
for i in range(1,max+1):
totients[i] = totient(i)
print('Totients:')
for i in range(1,max+1):
print(i,totients[i])
我觉得这不是很优雅,而且容易产生错误,因为我存储的是None,如果我不小心错误地使用它们,它可能会抛出异常,而且因为我需要考虑映射让我避免的边缘情况。
没错,字典的效率不会那么高,但正如其他人评论的那样,速度上的微小差异并不总是值得冒重大维护风险。
简短版本:使用
pre_allocated_list = [None] * size
预先分配一个列表(也就是说,能够处理列表中的“size”元素,而不是通过追加逐渐形成列表)。这个操作非常快,即使是在大列表上。分配新对象,然后分配给列表元素将花费更长的时间,并将成为程序的性能瓶颈。
长版:
我认为初始化时间应该考虑在内。
因为在Python中,所有元素都是引用,所以不管你将每个元素设置为None还是某个字符串,它都只是一个引用。不过,如果您想为每个元素创建一个新对象来引用,则需要更长的时间。
对于Python 3.2:
import time
import copy
def print_timing (func):
def wrapper (*arg):
t1 = time.time()
res = func (*arg)
t2 = time.time ()
print ("{} took {} ms".format (func.__name__, (t2 - t1) * 1000.0))
return res
return wrapper
@print_timing
def prealloc_array (size, init = None, cp = True, cpmethod = copy.deepcopy, cpargs = (), use_num = False):
result = [None] * size
if init is not None:
if cp:
for i in range (size):
result[i] = init
else:
if use_num:
for i in range (size):
result[i] = cpmethod (i)
else:
for i in range (size):
result[i] = cpmethod (cpargs)
return result
@print_timing
def prealloc_array_by_appending (size):
result = []
for i in range (size):
result.append (None)
return result
@print_timing
def prealloc_array_by_extending (size):
result = []
none_list = [None]
for i in range (size):
result.extend (none_list)
return result
def main ():
n = 1000000
x = prealloc_array_by_appending(n)
y = prealloc_array_by_extending(n)
a = prealloc_array(n, None)
b = prealloc_array(n, "content", True)
c = prealloc_array(n, "content", False, "some object {}".format, ("blah"), False)
d = prealloc_array(n, "content", False, "some object {}".format, None, True)
e = prealloc_array(n, "content", False, copy.deepcopy, "a", False)
f = prealloc_array(n, "content", False, copy.deepcopy, (), False)
g = prealloc_array(n, "content", False, copy.deepcopy, [], False)
print ("x[5] = {}".format (x[5]))
print ("y[5] = {}".format (y[5]))
print ("a[5] = {}".format (a[5]))
print ("b[5] = {}".format (b[5]))
print ("c[5] = {}".format (c[5]))
print ("d[5] = {}".format (d[5]))
print ("e[5] = {}".format (e[5]))
print ("f[5] = {}".format (f[5]))
print ("g[5] = {}".format (g[5]))
if __name__ == '__main__':
main()
评价:
prealloc_array_by_appending took 118.00003051757812 ms
prealloc_array_by_extending took 102.99992561340332 ms
prealloc_array took 3.000020980834961 ms
prealloc_array took 49.00002479553223 ms
prealloc_array took 316.9999122619629 ms
prealloc_array took 473.00004959106445 ms
prealloc_array took 1677.9999732971191 ms
prealloc_array took 2729.999780654907 ms
prealloc_array took 3001.999855041504 ms
x[5] = None
y[5] = None
a[5] = None
b[5] = content
c[5] = some object blah
d[5] = some object 5
e[5] = a
f[5] = []
g[5] = ()
正如您所看到的,创建一个对同一个None对象的引用的大列表所花费的时间非常少。
预扩展或扩展需要更长的时间(我没有平均任何东西,但在运行几次之后,我可以告诉您,扩展和追加大约需要相同的时间)。
Allocating new object for each element - that is what takes the most time. And S.Lott's answer does that - formats a new string every time. Which is not strictly required - if you want to preallocate some space, just make a list of None, then assign data to list elements at will. Either way it takes more time to generate data than to append/extend a list, whether you generate it while creating the list, or after that. But if you want a sparsely-populated list, then starting with a list of None is definitely faster.
如果使用NumPy,就会出现Python中的预分配问题,因为NumPy有更多类似c的数组。在这种情况下,预分配关注的是数据的形状和默认值。
如果要在大量列表上进行数值计算并希望获得性能,可以考虑NumPy。
正如其他人所提到的,预播种列表的最简单方法是使用NoneType对象。
话虽如此,在决定这是必要的之前,您应该了解Python列表的实际工作方式。
在列表的CPython实现中,底层数组总是创建有开销空间,大小逐渐增大(4、8、16、25、35、46、58、72、88、106、126、148、173、201、233、269、309、354、405、462、526、598、679、771、874、990、1120等),因此调整列表的大小几乎不会经常发生。
由于这种行为,大多数list.append()函数的追加复杂度都是O(1),只有在跨越其中一个边界时复杂度才会增加,此时复杂度将为O(n)。在S.Lott的答案中,这种行为导致了执行时间的最小增加。
来源:Python列表实现
Python列表没有内置的预分配。如果你真的需要做一个列表,并且需要避免附加的开销(并且你应该验证你做了),你可以这样做:
l = [None] * 1000 # Make a list of 1000 None's
for i in xrange(1000):
# baz
l[i] = bar
# qux
也许你可以通过使用生成器来避免列表:
def my_things():
while foo:
#baz
yield bar
#qux
for thing in my_things():
# do something with thing
这样,列表就不会全部存储在内存中,而只是根据需要生成。