问题所在
我关心的是:我在一个经典的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
复制相似问题