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 可能很大，并且每次运行仅迭代一次的任何解决方案可能总是会获胜。

使用过滤功能：

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

这也会创建一个占用大量 RAM 的新列表。

使用 itertools 的过滤器函数：

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

此版本的过滤器调用不会创建新列表，但不会对破坏算法逻辑的每个项目调用 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)。我不想去这里，因为这几乎在任何地方都需要大量的代码重构。

Answer 1

如果不知道您正在使用此列表执行的具体操作，则很难确切地知道在这种情况下什么是最好的。如果您的处理阶段取决于列表元素的当前索引，则这将不起作用，但如果不是，则似乎您已经放弃了最Pythonic（并且在许多方面，最简单）的方法：生成器。

如果您所做的只是迭代每个元素，以某种方式处理它，然后是否将该元素包含在列表中，请使用生成器。那么你就不需要将整个可迭代存储在内存中。

def process_and_generate_data(source_iterable):
    for item in source_iterable:
        dosomestuff(item)
        if not somecondition(item):
            yield item

您需要有一个处理循环来处理持久化处理后的可迭代对象（将其写回文件或其他内容），或者如果您有多个处理阶段，您希望将其分成不同的生成器，则可以让处理循环通过一台发电机到另一台发电机。

Answer 2

从您的描述来看，双端队列（“甲板”）正是您正在寻找的：

http://docs.python.org/library/collections.html#deque-objects

通过重复调用 pop() 来“迭代”它，然后，如果您想将弹出的项目保留在双端队列，使用appendleft(item)将该项目返回到前面。为了跟上您完成迭代并查看双端队列中的所有内容的时间，可以放入您监视的标记对象（例如 None ），或者在启动特定循环并使用 range( 时询问双端队列的 len() ) ) 到 pop() 正好那么多项。

我相信你会发现你需要的所有操作都是 O(1) 的。

Answer 3

Python 仅存储对列表中对象的引用，而不存储元素本身。如果逐项增长列表，列表（即对象的引用列表）将逐项增长，最终到达 Python 在末尾预先分配的多余内存的末尾。列表（参考文献！）。然后，它将列表（引用！）复制到一个新的更大的位置，而列表元素保留在原来的位置。由于您的代码无论如何都会访问旧列表中的所有元素，因此通过 new_list[i]=old_list[i] 将引用复制到新列表几乎没有任何负担。唯一的性能提示是立即分配所有新元素，而不是追加它们（OTOH，Python 文档说摊销追加仍然是 O(1)，因为多余元素的数量随着列表大小的增加而增长）。如果您缺少新列表（引用）的位置，那么我担心您运气不佳 - 任何可以逃避 O(n) 就地插入/删除的数据结构都可能比简单的 4 数组更大- 或 8 字节条目。

Answer 4

双向链表比仅仅重新分配列表更糟糕。 Python 列表使用 5 个单词+每个元素一个单词。双向链表的每个元素将使用 5 个单词。即使您使用单链表，每个元素仍然需要 4 个单词 - 这比重建列表时每个元素少于 2 个单词要糟糕得多。

从内存使用的角度来看，将项目向上移动并删除最后的空闲部分是最好的方法。如果列表未满一半，Python 将释放内存。要问自己的问题是，这真的很重要吗？列表条目可能指向某些数据，除非列表中有很多重复的对象，否则列表使用的内存与数据相比是微不足道的。鉴于此，您不妨建立一个新列表。

对于构建新列表，您建议的方法不太好。没有明显的理由让你不能只浏览一遍这个列表。此外，调用 gc.collect() 是不必要的，而且实际上是有害的 - CPython 引用计数无论如何都会立即释放旧列表，甚至其他垃圾收集器在遇到内存压力时也最好进行收集。所以这样的事情会起作用：

while processingdata:
    retained = []
    for item in somelist:
        dosomething(item)
        if not somecondition(item):
            retained.append(item)
    somelist = retained

如果您不介意在列表推导中使用副作用，那么以下也是一个选择：

def process_and_decide(item):
    dosomething(item)
    return not somecondition(item)

while processingdata:
    somelist = [item for item in somelist if process_and_decide(item)]

还可以重构 inplace 方法，以便将机制和业务逻辑分开：

def inplace_filter(func, list_):
    pos = 0
    for item in list_:
        if func(item):
            list_[pos] = item
            pos += 1
    del list_[pos:]

while processingdata:
    inplace_filter(process_and_decide, somelist)

Answer 5

您没有提供足够的信息，我无法很好地回答这个问题。我不太了解您的用例，无法告诉您如果您必须优化时间，哪些数据结构将为您带来所需的时间复杂度。典型的解决方案是构建一个新列表而不是重复删除，但显然这会使内存使用量增加一倍。

如果您遇到内存使用问题，您可能希望放弃使用内存中的 Python 结构，而使用磁盘数据库。许多数据库都可用，sqlite 随 Python 一起提供。根据您的使用情况以及内存需求的紧张程度，array.array 或 numpy 可能会对您有所帮助，但这在很大程度上取决于您需要执行的操作。 array.array 的时间复杂度与 list 相同，numpy 数组的工作方式有所不同。使用惰性迭代器（例如生成器和 itertools 模块中的内容）通常可以将内存使用量减少 n 倍。

使用数据库将缩短从任意位置删除项目的时间（尽管如果这很重要，顺序将会丢失）。使用 dict 会起到相同的作用，但可能会占用大量内存。

您还可以考虑使用 blist 作为一个可能会得到你想要的一些妥协的列表。我不相信它会大幅增加内存使用量，但它会将项目删除更改为 O(log n)。当然，这是以其他操作变得更加昂贵为代价的。

我必须进行测试才能相信，双向链表实现的内存使用常数因子将小于通过简单创建新列表获得的 2。我真的很怀疑。

我认为，您将必须分享有关您的问题类的更多信息，以获得更具体的答案，但一般建议是

• 迭代列表，构建新列表（或在需要时使用生成器生成项目） 。如果您确实需要一个列表，那么它的内存系数将为 2，该值可以很好地缩放，但如果您内存不足，则无济于事。
• 如果内存不足，您可能需要一个磁盘数据库或将数据存储在文件中，而不是微优化。

Answer 6

Brandon Craig Rhodes 建议使用collections.deque，它可以解决这个问题：操作不需要额外的内存，并且保持 O(n) 的复杂度。我不知道总内存使用量以及它与列表的比较如何；值得注意的是，双端队列必须存储更多的引用，如果它不像使用两个列表那样占用内存，我不会感到惊讶。您必须测试或研究它才能了解自己。

如果您要使用双端队列，我的部署方式与罗兹建议的略有不同：

from collections import deque
d = deque(range(30))
n = deque()

print d

while True:
    try:
        item = d.popleft()
    except IndexError:
        break

    if item % 3 != 0:
        n.append(item)

print n

这样做不会产生显着的内存差异，但与随心所欲地改变同一个双端队列相比，出错的机会要少得多。