Python中vector::reserve()的等价方法是什么？

Question

我在找Python中类似于C++的vector::reserve()的功能。我不知道列表会有多大，但我知道它会比较大，我想尽量避免在一个深层循环中频繁调整列表的大小。

到目前为止，我想到的解决办法比较麻烦，跟vector::reserve()的用法比起来差远了。我的办法是先用[None]*K来创建一个列表，同时用一个单独的计数器来记录列表的大小，根据需要往列表里添加或设置项目，然后在列表完全构建好后再复制一部分。有没有其他的选择呢？

Answer 1

简单来说，你可以通过下面的方式创建一个预先设定大小的列表：

lst = [None] * N # where N = size of list

当然，你需要手动设置每个位置的值（而不是用追加的方法），并且要记住你最后使用的那个位置。

不过，是否真的需要这样做又是另一个问题（我们的朋友们对此已经给出了很好的答案）。

Answer 2

和 std::vector 类似，CPython 的 list 在开始的时候就会预先分配比实际需要的更多的空间，然后在需要的时候再扩展这个空间，这样可以让添加元素的操作平均下来是非常快的，时间复杂度是 O(1)。所以我建议在没有证据证明这是个瓶颈之前，就先保持现状。

补充：你在评论中提到你已经做过性能分析。如果是这样的话，预先分配 [None]*n 可能是个不错的尝试，看看是不是重复分配空间真的造成了瓶颈。

如果你的数组是数字类型的，我建议你看看 NumPy。

Answer 3

为了好玩，我做了一些性能测试：

def foo(n):
  x = []
  for y in xrange(n): x.append(y)

def bar(n):
  x = [None] * n
  for y in xrange(n): x[y] = y

def baz(n):
  # This is obviously silly; we could just do range(n)
  # but this way makes for a fairer test
  x = [y for y in xrange(n)]

>>> timeit.timeit(lambda:foo(1000000), number=10)
1.761765391970215
>>> timeit.timeit(lambda:bar(1000000), number=10)
0.79829286962450396
>>> timeit.timeit(lambda:baz(1000000), number=10)
0.9904259479906159
>>> timeit.timeit(lambda:foo(10000), number=1000)
1.3354106457664443
>>> timeit.timeit(lambda:bar(10000), number=1000)
0.70596751821813086
>>> timeit.timeit(lambda:baz(10000), number=1000)
0.58049759117432131