这样的代码经常发生：
l = []
while foo:
# baz
l.append(bar)
# qux
如果您要将数千个元素附加到列表中，这真的很慢，因为必须不断调整列表的大小以适应新元素。
在 Java 中，您可以创建一个具有初始容量的 ArrayList。如果您知道您的列表有多大，这将更有效率。
我知道这样的代码通常可以重构为列表理解。但是，如果for / while循环非常复杂，这是不可行的。我们的 Python 程序员有没有等价物？
Claudiu
问问题
213328 次
9 回答
125
警告：这个答案是有争议的。看评论。
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
结论。这几乎不重要。
过早的优化是万恶之源。
于 2008-11-22T22:02:34.847 回答
91
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
这样，列表根本不会全部存储在内存中，只是根据需要生成。
于 2008-11-22T21:07:18.873 回答
58
短版：使用
pre_allocated_list = [None] * 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列表开始肯定会更快。
于 2011-04-04T00:48:00.617 回答
33
Pythonic 的方法是：
x = [None] * numElements
或者您希望预填充的任何默认值，例如
bottles = [Beer()] * 99
sea = [Fish()] * many
vegetarianPizzas = [None] * peopleOrderingPizzaNotQuiche
（警告 Emptor：[Beer()] * 99语法创建一个 Beer，然后用 99 个对同一单个实例的引用填充一个数组）
Python 的默认方法可能非常有效，尽管随着元素数量的增加效率会下降。
比较
import time
class Timer(object):
def __enter__(self):
self.start = time.time()
return self
def __exit__(self, *args):
end = time.time()
secs = end - self.start
msecs = secs * 1000 # Millisecs
print('%fms' % msecs)
Elements = 100000
Iterations = 144
print('Elements: %d, Iterations: %d' % (Elements, Iterations))
def doAppend():
result = []
i = 0
while i < Elements:
result.append(i)
i += 1
def doAllocate():
result = [None] * Elements
i = 0
while i < Elements:
result[i] = i
i += 1
def doGenerator():
return list(i for i in range(Elements))
def test(name, fn):
print("%s: " % name, end="")
with Timer() as t:
x = 0
while x < Iterations:
fn()
x += 1
test('doAppend', doAppend)
test('doAllocate', doAllocate)
test('doGenerator', doGenerator)
和
#include <vector>
typedef std::vector<unsigned int> Vec;
static const unsigned int Elements = 100000;
static const unsigned int Iterations = 144;
void doAppend()
{
Vec v;
for (unsigned int i = 0; i < Elements; ++i) {
v.push_back(i);
}
}
void doReserve()
{
Vec v;
v.reserve(Elements);
for (unsigned int i = 0; i < Elements; ++i) {
v.push_back(i);
}
}
void doAllocate()
{
Vec v;
v.resize(Elements);
for (unsigned int i = 0; i < Elements; ++i) {
v[i] = i;
}
}
#include <iostream>
#include <chrono>
using namespace std;
void test(const char* name, void(*fn)(void))
{
cout << name << ": ";
auto start = chrono::high_resolution_clock::now();
for (unsigned int i = 0; i < Iterations; ++i) {
fn();
}
auto end = chrono::high_resolution_clock::now();
auto elapsed = end - start;
cout << chrono::duration<double, milli>(elapsed).count() << "ms\n";
}
int main()
{
cout << "Elements: " << Elements << ", Iterations: " << Iterations << '\n';
test("doAppend", doAppend);
test("doReserve", doReserve);
test("doAllocate", doAllocate);
}
在我的 Windows 7 Core i7上，64 位 Python 提供
Elements: 100000, Iterations: 144
doAppend: 3587.204933ms
doAllocate: 2701.154947ms
doGenerator: 1721.098185ms
虽然 C++ 提供（使用Microsoft Visual C++构建，64 位，已启用优化）
Elements: 100000, Iterations: 144
doAppend: 74.0042ms
doReserve: 27.0015ms
doAllocate: 5.0003ms
C++ 调试版本产生：
Elements: 100000, Iterations: 144
doAppend: 2166.12ms
doReserve: 2082.12ms
doAllocate: 273.016ms
这里的重点是，使用 Python，您可以实现 7-8% 的性能提升，如果您认为自己正在编写高性能应用程序（或者如果您正在编写用于 Web 服务或其他东西的东西），那么这不是被嗤之以鼻的，但你可能需要重新考虑你的语言选择。
此外，这里的 Python 代码并不是真正的 Python 代码。在这里切换到真正的 Pythonesque 代码可以提供更好的性能：
import time
class Timer(object):
def __enter__(self):
self.start = time.time()
return self
def __exit__(self, *args):
end = time.time()
secs = end - self.start
msecs = secs * 1000 # millisecs
print('%fms' % msecs)
Elements = 100000
Iterations = 144
print('Elements: %d, Iterations: %d' % (Elements, Iterations))
def doAppend():
for x in range(Iterations):
result = []
for i in range(Elements):
result.append(i)
def doAllocate():
for x in range(Iterations):
result = [None] * Elements
for i in range(Elements):
result[i] = i
def doGenerator():
for x in range(Iterations):
result = list(i for i in range(Elements))
def test(name, fn):
print("%s: " % name, end="")
with Timer() as t:
fn()
test('doAppend', doAppend)
test('doAllocate', doAllocate)
test('doGenerator', doGenerator)
这使
Elements: 100000, Iterations: 144
doAppend: 2153.122902ms
doAllocate: 1346.076965ms
doGenerator: 1614.092112ms
（在 32 位中，doGenerator 比 doAllocate 做得更好）。
这里 doAppend 和 doAllocate 之间的差距要大得多。
显然，这里的差异真的只适用于你这样做的次数超过几次，或者如果你在一个负载很重的系统上这样做，这些数字将被扩大几个数量级，或者你正在处理相当大的列表。
这里的重点：使用 Pythonic 方式来获得最佳性能。
但是，如果您担心一般的高级性能，那么 Python 是错误的语言。最根本的问题是，由于 Python 的装饰器等特性（PythonSpeed/PerformanceTips、Data Aggregation），传统上 Python 函数调用比其他语言慢 300 倍。
于 2014-06-11T22:21:01.730 回答
10
正如其他人所提到的，预置列表的最简单方法是使用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, etc)，因此调整列表大小几乎不会经常发生。
Because of this behavior, most list.append() functions are O(1) complexity for appends, only having increased complexity when crossing one of these boundaries, at which point the complexity will be O(n). This behavior is what leads to the minimal increase in execution time in S.Lott's answer.
Source: Python list implementation
于 2017-01-12T18:20:35.773 回答
4
我运行了S.Lott 的代码并通过预分配产生了同样 10% 的性能提升。我使用生成器尝试了 Ned Batchelder 的想法，并且能够看到生成器的性能优于 doAllocate。对于我的项目来说，10% 的改进很重要，所以感谢大家，因为这对很多人都有帮助。
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
def doGen(size=10000):
return list("some unique object %d" % ( i, ) for i in xrange(size))
size = 1000
@print_timing
def testAppend():
for i in xrange(size):
doAppend()
@print_timing
def testAlloc():
for i in xrange(size):
doAllocate()
@print_timing
def testGen():
for i in xrange(size):
doGen()
testAppend()
testAlloc()
testGen()
输出
testAppend took 14440.000ms
testAlloc took 13580.000ms
testGen took 13430.000ms
于 2009-10-21T19:09:38.817 回答
4
如果您使用NumPy会出现有关 Python 中预分配的担忧，因为 NumPy 具有更多类似 C 的数组。在这种情况下，预分配问题与数据的形状和默认值有关。
如果您正在对海量列表进行数值计算并希望获得性能，请考虑使用 NumPy。
于 2014-07-30T02:22:33.290 回答
0
对于某些应用程序，您可能需要字典。例如，在 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 如果我不小心使用错误可能会引发异常，并且因为我需要考虑地图让我避免的边缘情况。
确实，字典不会那么高效，但正如其他人所评论的那样，速度上的微小差异并不总是值得重大的维护风险。
于 2016-10-27T16:33:12.733 回答
-3
据我了解，Python 列表已经与 ArrayLists 非常相似。但是如果你想调整那些参数，我在互联网上发现了这篇可能很有趣的帖子（基本上，只需创建你自己的ScalableList扩展）：
http://mail.python.org/pipermail/python-list/2000-May/035082.html
于 2008-11-22T21:07:56.767 回答