python - 有没有办法绕过 Python list.append() 随着列表的增长而在循环中逐渐变慢？

Question

我有一个正在读取的大文件，每隔几行就将其转换为一个 Object 的实例。

由于我正在循环文件，我使用 list.append(instance) 将实例存储到列表中，然后继续循环。

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

这不是循环固有的 ~ 当我在循环文件时打印每个新实例时，程序以恒定速度运行 ~ 只有当我将它们 append 到列表时它才会变慢。

我的 friend 建议在 while 循环之前禁用垃圾收集并在之后启用它并进行垃圾收集调用。

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

---

我将尝试以下建议的以下两件事。

(1)“预分配”内存~最好的方法是什么？ (2) 尝试使用双端队列

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

要复制该现象，请运行答案中提供的下面的测试代码，并假设列表有有用的数据。

---

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

Answer 1

您观察到的性能差是您正在使用的版本中的python垃圾收集器中的错误引起的。升级到Python 2.7，或3.1或更高版本或更高版本或更高版本以恢复不适合的0(1)行为期望在 Python 中追加列表。

如果您无法升级，请在构建列表时禁用垃圾收集，并在完成后将其打开。

(您也可以调整垃圾收集器的触发器或随着进度的有选择性调用收集，但是我在此答案中不探索这些选项，因为它们更复杂，我怀疑您的用例适合上述解决方案。)<)<)<)<)<)

背景:

见:https://bugs.python.org/issue4074还有https://docs.python.org/release/2.5.2/lib/module-gc.html

记者观察到，随着列表的长度增长，将复杂对象(不是数字或字符串的对象) append 到线性的速度。

这种行为的原因是垃圾收集器正在检查和重新检查列表中的每个对象，以查看它们是否有资格获得垃圾收集。此行为会导致将对象添加到列表的时间线性增加。预计会在 py3k 中进行修复，因此它不应该适用于您正在使用的解释器。

测试:

我进行了一个测试来证明这一点。对于 1k 次迭代，我将 10k 个对象 append 到一个列表中，并记录每次迭代的运行时间。整体运行时差异立即显而易见。在测试的内部循环期间禁用垃圾收集，我的系统上的运行时间为 18.6 秒。为整个测试启用垃圾回收后，运行时间为 899.4s。

这是测试:

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 轴是对数刻度的秒数。

_{(来源:hypervolu.me)}

由于这两个图在 y 分量上相差几个数量级，因此在这里它们是独立的，y 轴是线性缩放的。

_{(来源:hypervolu.me)}

_{(来源:hypervolu.me)}

有趣的是，随着垃圾收集的关闭，我们只看到每10k附录的运行时尖峰，这表明Python的 list 重新分配成本相对较低。无论如何，它们比垃圾收集成本低许多数量级。

以上图的密度很难看出，在垃圾收集器开启的情况下，大多数区间实际上都有很好的性能；只有当垃圾收集器循环时，我们才会遇到病态行为。您可以在这个 10k append 时间的直方图中观察到这一点。大多数数据点每 10k 追加下降约 0.02 秒。

_{(来源:hypervolu.me)}

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