Python:修改列表时的内存使用和优化
问题所在
我关心的是:我在一个经典的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(项)的逻辑，它希望以与原始列表中出现的顺序相同的顺序处理它们。
创建一个新的列表：
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)这也会创建一个占用大量RAM的新列表。
使用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)。我不想在这里讨论，因为这几乎在任何地方都需要大量的代码重构。
https://stackoverflow.com/questions/2631053
复制相似问题