有没有办法绕过Python list.append()随着列表的增长逐渐变慢？

Question

我有一个大文件,我正在读取,并将每几行转换为一个对象的实例.

由于我循环遍历文件,因此我使用list.append(instance)将实例存储到列表中,然后继续循环.

这是一个约100MB左右的文件,因此它不会太大,但随着列表变大,循环逐渐减慢.(我打印循环中每圈的时间).

这不是循环所固有的〜当我循环浏览文件时打印每个新实例时,程序以恒定速度进行〜只有当我将它们附加到列表时才会变慢.

我的朋友建议在while循环之前禁用垃圾收集,然后启用它并进行垃圾收集调用.

有没有其他人观察到list.append变慢的类似问题？有没有其他方法来规避这个？

---

我将尝试以下两个建议.

(1)"预先分配"记忆〜这样做的最佳方法是什么？(2)尝试使用deque

多个帖子(请参阅Alex Martelli的评论)建议内存碎片化(他有像我这样的大量可用内存)〜但没有明显的性能修复.

要复制这种现象,请运行下面答案中提供的测试代码,并假设这些列表包含有用的数据.

---

gc.disable()和gc.enable()有助于计时.我还会仔细分析所有时间花在哪里.

Answer 1

您观察到的性能不佳是由您正在使用的版本中的Python垃圾收集器中的错误引起的.升级到Python 2.7或3.1或更高版本以重新获得在Python中附加列表所期望的amoritized 0(1)行为.

如果无法升级,请在构建列表时禁用垃圾回收,并在完成后将其打开.

(你也可以调整垃圾收集器的触发器,或者在你进步时有选择地调用collect,但我不会在这个答案中探索这些选项,因为它们更复杂,我怀疑你的用例适合上述解决方案.)

背景:

请参阅:https://bugs.python.org/issue4074以及https://docs.python.org/release/2.5.2/lib/module-gc.html

记者观察到,随着列表长度的增加,将复杂对象(非数字或字符串的对象)附加到列表会线性减慢.

此行为的原因是垃圾收集器正在检查并重新检查列表中的每个对象,以查看它们是否符合垃圾回收的条件.此行为导致将对象添加到列表的时间线性增加.预计修复将在py3k中出现,因此它不应该适用于您正在使用的解释器.

测试:

我跑了一个测试来证明这一点.对于1k次迭代,我将10k对象附加到列表中,并记录每次迭代的运行时.整体运行时差异很明显.在测试的内部循环期间禁用垃圾收集,我的系统上的运行时间为18.6秒.通过为整个测试启用垃圾收集,运行时为899.4秒.

这是测试:

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

图形结果:红色表示gc打开,蓝色表示gc关闭.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

有趣的是,关闭垃圾回收,我们发现每10k附加的运行时只有小的峰值,这表明Python的列表重新分配成本相对较低.无论如何,它们比垃圾收集成本低许多个数量级.

上面的图的密度使得很难看到垃圾收集器打开,大多数间隔实际上具有良好的性能; 只有当垃圾收集器循环时才会遇到病理行为.您可以在10k附加时间的直方图中观察到这一点.大多数数据点每10k附加约0.02s.

http://hypervolu.me/~erik/programming/python_lists/gc_on.hist.png

用于生成这些图的原始数据可以在http://hypervolu.me/~erik/programming/python_lists/找到.

Answer 2

没有什么可以规避的:追加到列表是O(1)摊销.

列表(在CPython中)是一个数组,至少与列表一样长,最多两倍.如果数组未满,则附加到列表就像分配其中一个数组成员(O(1))一样简单.每次数组都满了,它的大小会自动加倍.这意味着有时需要O(n)操作,但是每n次操作只需要操作,并且随着列表变大,它越来越少需要.O(n)/ n ==> O(1).(在其他实现中,名称和详细信息可能会发生变化,但必须保持相同的时间属性.)

附加到列表已经扩展.

是否有可能当文件变大时,您无法将所有内容保存在内存中并且您遇到操作系统分页到磁盘的问题？它是否可能是你的算法的另一部分不能很好地扩展？

Answer 3

很多这些答案都是疯狂的猜测.我喜欢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.我打印出每100,000次附加的持续时间,100次.它确实像你声称的那样减速.(第一次迭代为0.03秒,最后一次为0.84秒......相当不同.)

显然,如果您实例化一个列表但不追加它x,它会更快地运行并且不会随着时间的推移而扩展.

但是如果换x.append([])到x.append('hello world'),那就没有速度提升了.同一个对象被添加到列表100*100,000次.

我对此做了什么:

• 速度降低与列表的大小无关.它与实时Python对象的数量有关.
• 如果您根本没有将项目附加到列表中,它们就会立即收集垃圾并且不再由Python管理.
• 如果反复追加相同的项目,则实时Python对象的数量不会增加.但该列表必须每隔一段时间重新调整一次.但这不是性能问题的根源.
• 由于您要创建大量新创建的对象并将其添加到列表中,因此它们保持活动状态并且不会被垃圾回收.减速可能与此有关.

至于可以解释这一点的Python内部,我不确定.但我很确定列表数据结构不是罪魁祸首.