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

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

Answer 1

列表理解是渐近最优解：

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

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

从Python中的列表中删除项目为O（n），因此循环内带有remove，pop或del的所有内容均为O（n ** 2）。

另外，在CPython列表中，理解要比for循环快。