有没有办法绕开Python list.append（）随着列表的增长而逐渐变慢？
我正在阅读一个大文件，并将每隔几行转换为Object的一个实例。
由于我正在循环该文件，我使用list.append（instance）将实例存储到列表，然后继续循环。
这是一个大约100MB左右的文件，因此不会太大，但是随着列表越来越大，循环逐渐减慢。 （我打印循环中每圈的时间）。
这不是固有的循环〜当我打印每一个新的实例，当我循环的文件，程序以恒定的速度进展〜只有当我把它们追加到列表慢慢。
我的朋友build议在while循环之前禁用垃圾收集，然后启用它并进行垃圾收集调用。
有没有其他人观察到类似的问题list.append变慢？ 有没有其他办法可以绕过这个呢？
我会尝试下面的两个build议。
（1）“预先分配”记忆〜最好的办法是什么？ （2）尝试使用deque
多篇文章（请参阅Alex Martelli的评论）提出了内存碎片（他拥有大量的可用内存，就像我一样），但对性能没有明显的修正。
要复制这种现象，请运行答案中提供的testing代码，并假定列表中有有用的数据。
gc.disable（）和gc.enable（）有助于计时。 我也会仔细分析所有的时间花在哪里。
您观察到的糟糕的性能是由您正在使用的版本中的Python垃圾收集器中的错误引起的。 升级到Python 2.7或3.1或更高版本以重新获得Python中列表追加的预期0（1）行为。
如果无法升级，请在构build列表时禁用垃圾回收，并在完成后将其打开。
（你也可以调整垃圾收集器的触发器，或者随着进度的select调用collect，但是我不会在这个答案中探索这些选项，因为它们更复杂，我怀疑你的用例适用于上述解决scheme。）
背景：
请参阅： https ： //bugs.python.org/issue4074和https://docs.python.org/release/2.5.2/lib/module-gc.html
记者注意到，随着列表长度的增加，将复杂对象（不是数字或string的对象）追加到列表中会线性减慢。
这种行为的原因是垃圾收集器正在检查并重新检查列表中的每个对象，以查看它们是否有资格进行垃圾回收。 此行为导致时间线性增加将对象添加到列表。 预计修复程序将在py3k中着陆，因此它不适用于您正在使用的翻译程序。
testing：
我跑了一个testing来certificate这一点。 对于1k次迭代，我将10k对象附加到列表中，并logging每次迭代的运行时间。 总的运行时间差异是显而易见的。 在testing的内部循环期间禁用垃圾收集，我的系统上的运行时间是18.6s。 在整个testing中启用垃圾收集，运行时间是899.4s。
这是testing：
import time import gc class A: def __init__(self): self.x = 1 self.y = 2 self.why = 'no reason' def time_to_append(size, append_list, item_gen): t0 = time.time() for i in xrange(0, size): append_list.append(item_gen()) return time.time() - t0 def test(): x = [] count = 10000 for i in xrange(0,1000): print len(x), time_to_append(count, x, lambda: A()) def test_nogc(): x = [] count = 10000 for i in xrange(0,1000): gc.disable() print len(x), time_to_append(count, x, lambda: A()) gc.enable() 完整源代码： https ： //hypervolu.me/~erik/programming/python_lists/listtest.py.txt
graphics结果：红色与gc打开，蓝色与gcclosures。 y轴是秒对数缩放。
http://hypervolu.me/~erik/programming/python_lists/gc.png
由于这两个图在y分量上相差几个数量级，因此这里它们与y轴线性地成比例地独立。
http://hypervolu.me/~erik/programming/python_lists/gc_on.png
http://hypervolu.me/~erik/programming/python_lists/gc_off.png
有趣的是，在垃圾收集closures的情况下，我们看到每10k个附加信息在运行时只有很小的峰值，这表明Python的列表重新分配成本相对较低。 无论如何，它们比垃圾收集成本低很多个数量级。
上述情节的密度使得难以看出，随着垃圾收集器，大多数间隔实际上有良好的performance; 只有当垃圾收集器循环时，才会遇到病态行为。 你可以在这个10k追加时间的直方图中观察这个。 大多数数据点每10k附加大约0.02秒。
http://hypervolu.me/~erik/programming/python_lists/gc_on.hist.png
用于生成这些地块的原始数据可以在http://hypervolu.me/~erik/programming/python_lists/find。;
没有什么可以规避的： 附加到列表是O（1）摊销。
列表（在CPython中）是一个至less与列表一样长的数组，长达两倍。 如果数组未满，则追加到列表与分配一个数组成员（O（1））一样简单。 每当数组满了，它的大小就会自动加倍。 这意味着有时需要O（n）操作，但是每n次操作只需要一个操作 ，并且越来越less，因为列表变大。 O（n）/ n ==> O（1）。 （在其他实现中，名称和细节可能会发生变化，但同一时间属性必须保持不变。）
附加到列表已经缩放。
是否有可能，当文件变得很大，你不能把所有的东西都放在内存中，而且你正面临操作系统分页到磁盘的问题？ 这可能是你的algorithm的一个不同的部分，不能很好地扩展吗？
许多这些答案只是野生猜测。 我喜欢麦克·格雷厄姆（Mike Graham）最好的，因为他对于如何实现列表是正确的。 但是我写了一些代码来重现你的主张并进一步研究它。 这里有一些发现。
这是我开始的。
import time x = [] for i in range(100): start = time.clock() for j in range(100000): x.append([]) end = time.clock() print end - start
我只是将空列表追加到列表x 。 每打印100000次，打印一次。 它确实像你所说的那样慢下来。 （第一次迭代为0.03秒，最后一次为0.84秒…）。
很明显，如果你实例化一个列表，但不把它附加到x ，它运行得更快，并且不会随着时间的推移而放大。
但是，如果将x.append([])更改为x.append('hello world') ，则根本没有速度增加。 同样的对象被添加到列表100 * 100,000次。
我所做的是：
- 速度下降与列表大小无关。 它与活动Python对象的数量有关。
- 如果你不把这些项目追加到列表中，他们只是马上收集垃圾，不再被Pythonpipe理。
- 如果反复附加同一个项目，那么活动Python对象的数量不会增加。 但是名单不得不每隔一段时间重新调整一次。 但这不是性能问题的根源。
- 由于您正在创build并将大量新创build的对象添加到列表中，因此它们保持有效并且不会被垃圾收集。 减速可能与此有关。
至于Python的内部，可以解释这一点，我不知道。 但我很确定列表数据结构不是罪魁祸首。
你可以尝试http://docs.python.org/release/2.5.2/lib/deque-objects.html在列表中分配需要的元素的期望数量？ ？ 我敢打赌，列表是一个连续的存储，必须重新分配和复制每隔几个迭代。 （类似于c ++中一些stream行的std :: vector实现）
编辑：备份http://www.python.org/doc/faq/general/#how-are-lists-implemented
我在使用Numpy数组时遇到了这个问题，创build如下：
import numpy theArray = array([],dtype='int32')
在一个循环内追加这个数组的时间越来越长，随着数组的增长，这是一个交易破坏者，因为我有14M追加。
上面概述的垃圾收集器解决scheme听起来很有前途，但没有奏效。
什么工作是创build具有预定义大小的arrays如下：
theArray = array(arange(limit),dtype='int32')
只要确保限制比你需要的数组大。
然后可以直接设置数组中的每个元素：
theArray[i] = val_i
最后，如有必要，您可以删除未使用的数组部分
theArray = theArray[:i]
这在我的情况下造成了巨大的差异。
使用一个集合，然后将其转换为最后的列表
my_set=set() with open(in_file) as f: # do your thing my_set.add(instance) my_list=list(my_set) my_list.sort() # if you want it sorted
我有同样的问题，这解决了几个命令的时间问题。
;){kind=link}
;){kind=link}
;){kind=link}
;){kind=link}