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)。我不想在这里讨论，因为这几乎在任何地方都需要大量的代码重构。
回答 4
Stack Overflow用户
发布于 2010-04-14 00:15:57
如果不知道这个列表的具体操作细节，就很难确切地知道在这种情况下什么才是最好的。如果您的处理阶段依赖于列表元素的当前索引，这将不起作用，但如果不是，您似乎已经放弃了最Python化(在许多方面，也是最简单的)方法:生成器。
如果您所做的只是迭代每个元素，以某种方式对其进行处理，然后将该元素包含在列表中或不包含该元素，则使用生成器。这样你就再也不需要把整个可迭代存储在内存中了。
def process_and_generate_data(source_iterable):
for item in source_iterable:
dosomestuff(item)
if not somecondition(item):
yield item您需要有一个处理循环来持久化处理过的可迭代对象(将其写回文件，或者其他任何东西)，或者，如果您有多个处理阶段，您希望将其分离到不同的生成器中，您可以让处理循环将一个生成器传递给下一个生成器。
Stack Overflow用户
发布于 2010-04-14 01:02:05
从你的描述中，它听起来像是一个deque ("deck")可能就是你要找的：
http://docs.python.org/library/collections.html#deque-objects
通过重复调用pop()来“迭代”它，然后，如果您想要将弹出的项保留在双队列中，则使用appendleft( item )将该项返回到前面。当您完成迭代并且已经看到了deque中的所有内容时，为了跟上进度，可以放入一个类似于None的标记对象，或者在开始特定循环时请求deque的len()，并使用range()弹出相同数量的项。
我相信你会发现你需要的所有操作都是O(1)。
Stack Overflow用户
发布于 2010-04-14 06:15:39
双向链表比仅仅重新分配链表更糟糕。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)https://stackoverflow.com/questions/2631053
复制相似问题