有没有办法避免Python中list.append()在循环中随着列表增长变得越来越慢？

63 投票

7 回答

61681 浏览

数据工程师

提问于 2025-04-15 20:35

我有一个很大的文件要读取，每读几行就把它们转换成一个对象的实例。

因为我在循环读取这个文件，所以我会用 list.append(instance) 把这个实例存到一个列表里，然后继续循环。

这个文件大约有100MB，所以不算太大，但随着列表越来越长，循环的速度逐渐变慢。（我在循环中打印每次的时间）。

这个问题并不是循环本身造成的——当我在循环中打印每个新实例时，程序的速度是稳定的——只有在把它们添加到列表时，速度才会变慢。

我的朋友建议在循环开始前关闭垃圾回收，然后在循环结束后再开启，并进行一次垃圾回收的调用。

有没有其他人也遇到过 list.append 变慢的问题？有没有其他方法可以解决这个问题？

我会尝试下面建议的两件事。

(1) “预分配”内存——这最好的做法是什么？ (2) 尝试使用 deque。

很多帖子（比如 Alex Martelli 的评论）提到内存碎片化的问题（他和我一样有大量可用内存）——但没有明显的解决性能问题的方法。

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

gc.disable() 和 gc.enable() 对时间管理有帮助。我还会仔细分析一下时间都花在哪里了。

性能优化列表操作内存管理垃圾回收循环效率内存碎片化 deque 预分配内存

7 个回答

很多回答其实都是在猜测。我觉得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内部的机制能否解释这一切，我不太确定。不过我很肯定，列表的数据结构不是问题的根源。

回答于 2025-04-15 由 Python大师

分享举报

其实没有什么需要绕过的：往列表里添加东西的平均时间是O(1)。

在CPython中，列表其实是一个数组，这个数组的长度至少和列表一样长，最多可以是列表的两倍。如果这个数组没有满，往列表里添加东西就像给数组里的某个位置赋值一样简单（O(1)）。每当数组满了，它的大小会自动翻倍。这意味着偶尔会需要一个O(n)的操作，但这个操作只在每n次操作中需要一次，而且随着列表变大，这种情况会越来越少。O(n) / n ==> O(1)。在其他实现中，名称和细节可能会有所不同，但时间特性基本上是一样的。

往列表里添加东西的效率是可以扩展的。

如果文件变得很大，你可能无法把所有东西都放在内存里，这样就可能会遇到操作系统把数据换到硬盘上的问题。也有可能是你算法的其他部分扩展性不好？

回答于 2025-04-15 由 Python大师

分享举报

106

你观察到的性能问题是因为你使用的Python版本中的垃圾回收器有个bug。建议你升级到Python 2.7，或者3.1及以上版本，这样在向列表添加元素时就能恢复到预期的快速性能。

如果你无法升级，可以在构建列表时先关闭垃圾回收，等完成后再开启。

（你也可以调整垃圾回收器的触发条件，或者在进程中选择性地调用垃圾回收，但我在这里不详细讨论这些选项，因为它们比较复杂，而我觉得你的情况更适合上述解决方案。）

背景：

可以查看： https://bugs.python.org/issue4074 以及 https://docs.python.org/release/2.5.2/lib/module-gc.html

报告者发现，当向列表中添加复杂对象（不是数字或字符串的对象）时，随着列表长度的增加，添加的速度会线性变慢。

造成这种情况的原因是垃圾回收器在检查列表中的每个对象，以确定它们是否可以被回收。这种检查导致添加对象的时间逐渐增加。预计在py3k中会修复这个问题，因此你使用的解释器应该不会受到影响。

测试：

我做了一个测试来演示这个问题。在1000次迭代中，我向一个列表中添加了10000个对象，并记录每次迭代的运行时间。整体运行时间的差异非常明显。在测试的内部循环中关闭垃圾回收时，我的系统运行时间是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

图形结果：红色表示开启垃圾回收，蓝色表示关闭垃圾回收。y轴是以对数方式缩放的秒数。

_{(来源： hypervolu.me)}