Python - 创建具有初始容量的列表

Question

像这样的代码经常发生：l = []while foo:    #baz    l.append(bar)    #qux如果您要将数千个元素追加到列表中，这非常慢，因为必须不断调整列表大小以适应新元素。在Java中，您可以创建具有初始容量的ArrayList。如果您对列表的大小有所了解，那么效率会更高。我知道像这样的代码通常可以重新考虑到列表理解中。但是，如果for / while循环非常复杂，那么这是不可行的。我们的Python程序员有没有相同的东西？

Answer 1

def doAppend( size=10000 ):

    result = []

    for i in range(size):

        message= "some unique object %d" % ( i, )

        result.append(message)

    return result

def doAllocate( size=10000 ):

    result=size*[None]

    for i in range(size):

        message= "some unique object %d" % ( i, )

        result[i]= message

    return result

结果。（评估每个功能144次并平均持续时间）

simple append 0.0102

pre-allocate  0.0098

结论。这几乎不重要。

过早优化是万恶之源。

Answer 2

简短版：使用

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对象的引用的大列表，只需要很少的时间。

前置或延长需要更长的时间（我没有做任何平均值，但是在运行几次后我可以告诉你，延伸和追加大致需要相同的时间）。

为每个元素分配新对象 - 这是花费最多时间的。而S.Lott的答案就是这样 - 每次都会格式化一个新的字符串。这不是严格要求的 - 如果您想预先分配一些空间，只需创建一个None列表，然后随意将数据分配给列表元素。无论哪种方式，生成数据都需要花费更多时间而不是追加/扩展列表，无论是在创建列表时生成还是在生成列表之后生成数据。但是如果你想要一个人口稀少的列表，那么从None列表开始肯定会更快。