快速从列表/队列中移除少量项目的方法

Question

这是对一个类似问题的后续讨论，那个问题询问了在Python中写代码的最佳方式。

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

因为 list.remove 的作用和 del list[list.index(x)] 是一样的，所以你可以这样做：

for idx, item in enumerate(somelist):
    if determine(item):
        del somelist[idx]

但是：在遍历（查看）列表的时候，不要去修改这个列表。这会在某个时候给你带来麻烦。你可以先使用 filter 或者列表推导式，然后再进行优化。

Answer 2

如果你想要在常数时间内（O(1)）删除一个项目，可以使用哈希表（HashMap）。

Answer 3

列表推导式是一种非常高效的解决方案：

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

它只需要遍历一次列表，所以运行时间是O(n)。因为你需要对每个对象调用一次determine()，所以任何算法至少需要O(n)的操作。虽然列表推导式需要进行一些复制，但它只是复制了对象的引用，而不是复制整个对象。

在Python中，从列表中删除项目的时间复杂度是O(n)，所以如果在循环中使用remove、pop或del等操作，时间复杂度就会变成O(n²)。

另外，在CPython中，列表推导式的速度比for循环要快。