从列表/队列中删除一些项目的快速方法

Question

这是对一个类似 问题 的跟进，该问题询问了最好的写作方式

for item in somelist:
    if determine(item):
         code_to_remove_item

似乎共识是在类似的事情上

somelist[:] = [x for x in somelist if not determine(x)]

但是，我认为如果您只删除一些项目，那么大部分项目都会被复制到同一个对象中，这可能会很慢。在另一个相关 问题 的 回答 中，有人建议：

 for item in reversed(somelist):
    if determine(item):
        somelist.remove(item)

但是，这里的 list.remove 将搜索列表长度为 O(N) 的项目。可能我们的限制在于列表表示为数组，而不是链表，因此删除项目将需要移动它后面的所有内容。不过 这里 建议用双向链表来表示collections.dequeue。然后应该可以在迭代时在 O(1) 中删除。我们将如何真正做到这一点？

更新：我也做了一些时间测试，代码如下：

 import timeit
setup = """
import random
random.seed(1)
b = [(random.random(),random.random()) for i in xrange(1000)]
c = []
def tokeep(x):
        return (x[1]>.45) and (x[1]<.5)
"""
listcomp = """
c[:] = [x for x in b if tokeep(x)]
"""
filt = """
c = filter(tokeep, b)
"""
print "list comp = ", timeit.timeit(listcomp,setup, number = 10000)
print "filtering = ", timeit.timeit(filt,setup, number = 10000)

并得到：

 list comp =  4.01255393028
filtering =  3.59962391853

原文由 highBandWidth 发布，翻译遵循 CC BY-SA 4.0 许可协议

Answer 1

列表理解是渐近最优解：

 somelist = [x for x in somelist if not determine(x)]

它只对列表进行一次传递，因此运行时间为 O(n)。由于您需要在每个对象上调用 determine()，因此任何算法都至少需要 O(n) 次操作。列表推导式确实需要进行一些复制，但它只是复制对对象的引用，而不是复制对象本身。

在 Python 中从列表中删除项目的时间复杂度为 O(n)，因此在循环内使用 remove、pop 或 del 的任何内容的时间复杂度为 O(n**2)。

此外，在 CPython 中，列表理解比 for 循环更快。

原文由 Daniel Stutzbach 发布，翻译遵循 CC BY-SA 3.0 许可协议

Answer 2

双端队列针对头部和尾部的移除进行了优化，而不是针对中间的任意移除进行了优化。移除本身是很快的，但是你仍然需要遍历列表到移除点。如果您遍历整个长度，那么过滤双端队列和过滤列表（使用 filter 或理解）之间的唯一区别是复制的开销，最坏的情况下是一个常数倍数；它仍然是一个 O(n) 操作。另外请注意，列表中的对象并没有被复制——只是对它们的引用。所以它没有那么多开销。

有可能你可以避免像这样复制，但我没有特别的理由相信这比直接的列表理解更快——它可能不是：

 write_i = 0
for read_i in range(len(L)):
    L[write_i] = L[read_i]
    if L[read_i] not in ['a', 'c']:
         write_i += 1
del L[write_i:]

原文由 senderle 发布，翻译遵循 CC BY-SA 3.0 许可协议