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语句花费更多,至少在记忆方面.请记住,某些列表可能很大,并且每次运行只迭代一次的任何解决方案都可能总是获胜.

使用过滤功能:

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(并且在许多方面,最简单)的方法:生成器.

如果您所做的只是遍历每个元素,以某种方式处理它,然后在列表中包含该元素,则使用生成器.然后你永远不需要将整个iterable存储在内存中.

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

你需要有一个处理循环来处理持久化已处理的迭代(将其写回文件,或其他),或者如果你有多个处理阶段,你宁愿分成不同的生成器,你可以让你的处理循环通过一个发电机到下一个.