Python：修改列表时的内存使用与优化

Question

问题

我有个担心：我在一个普通的 Python 列表中存储了一个相对较大的数据集。为了处理这些数据，我必须多次遍历这个列表，对每个元素进行一些操作，并且经常需要从列表中删除某个项目。

看起来，从 Python 列表中删除一个项目的成本是 O(N)，因为 Python 需要把被删除元素后面的所有元素都往前移动一位。此外，由于要删除的项目数量大约和列表中的元素数量成正比，这样就导致了 O(N^2) 的算法复杂度。

我希望能找到一个在时间和内存上都比较划算的解决方案。我在网上查阅了一些资料，并总结了我的不同选择。哪一个是最好的选择呢？

保持本地索引：

while processingdata:
    index = 0
    while index < len(somelist):
        item = somelist[index]
        dosomestuff(item)
        if somecondition(item):
            del somelist[index]
        else:
            index += 1

这是我想出的最初解决方案。这种方法不仅不太优雅，我希望能找到更好的方法，同时保持时间和内存的高效。

反向遍历列表：

while processingdata:
    for i in xrange(len(somelist) - 1, -1, -1):
        dosomestuff(item)
        if somecondition(somelist, i):
            somelist.pop(i)

这种方法避免了增加索引变量，但最终的成本和原始版本是一样的。它还打破了 dosomestuff(item) 的逻辑，这个逻辑希望按照原始列表中的顺序处理元素。

创建一个新列表：

while processingdata:
    for i, item in enumerate(somelist):
        dosomestuff(item)
    newlist = []
    for item in somelist:
        if somecondition(item):
            newlist.append(item)
    somelist = newlist
    gc.collect()

这是一种非常简单的策略来从列表中删除元素，但需要大量内存，因为几乎要复制整个列表。

使用列表推导：

while processingdata:
    for i, item in enumerate(somelist):
        dosomestuff(item)
    somelist[:] = [x for x in somelist if somecondition(x)]

这种方法非常优雅，但实际上会再遍历一遍整个列表，并且需要复制其中的大部分元素。我的直觉是，这个操作在内存上可能比原来的 del 语句更耗费资源。要记住，somelist 可能非常大，任何每次运行只遍历一次的解决方案可能都会更好。

使用 filter 函数：

while processingdata:
    for i, item in enumerate(somelist):
        dosomestuff(item)
    somelist = filter(lambda x: not subtle_condition(x), somelist)

这种方法同样会创建一个新列表，占用大量内存。

使用 itertools 的 filter 函数：

from itertools import ifilterfalse
while processingdata:
     for item in itertools.ifilterfalse(somecondtion, somelist):
         dosomestuff(item)

这种版本的 filter 调用不会创建新列表，但不会对每个项目调用 dosomestuff，从而打破了算法的逻辑。我包括这个例子只是为了列出所有可能的选项。

在遍历时将项目向上移动：

while processingdata:
    index = 0
    for item in somelist:
        dosomestuff(item)
        if not somecondition(item):
            somelist[index] = item
            index += 1
    del somelist[index:]

这是一种微妙的方法，似乎在成本上比较划算。我认为它会将每个项目（或者每个项目的指针？）移动一次，从而实现 O(N) 的算法。最后，我希望 Python 能够聪明地在结束时调整列表的大小，而不需要为新列表分配内存。不过，我不太确定。

放弃 Python 列表：

class Doubly_Linked_List:
    def __init__(self):
        self.first = None
        self.last = None
        self.n = 0
    def __len__(self):
        return self.n
    def __iter__(self):
        return DLLIter(self)
    def iterator(self):
        return self.__iter__()
    def append(self, x):
        x = DLLElement(x)
        x.next = None
        if self.last is None:
            x.prev = None
            self.last = x
            self.first = x
            self.n = 1
        else:
            x.prev = self.last
            x.prev.next = x
            self.last = x
            self.n += 1

class DLLElement:
    def __init__(self, x):
    self.next = None
    self.data = x
    self.prev = None

class DLLIter:
    etc...

这种对象在某种程度上类似于 Python 列表。然而，删除一个元素的成本是 O(1)。我不想走这条路，因为这会需要在几乎所有地方进行大量的代码重构。

列表操作数据结构 itertools 列表推导内存优化算法复杂度反向遍历 filter 函数