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

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)时间运行.由于您需要在每个对象上调用determine(),因此任何算法都至少需要O(n)次操作.列表理解确实需要进行一些复制,但它只是复制对象的引用,而不是复制对象本身.

从Python中的列表中删除项目是O(n),因此循环中具有remove,pop或del的任何内容都将为O(n**2).

此外,在CPython列表中,理解比循环更快.