如何通过过滤在原地修改Python集合？

Question

我在想，Python有没有办法直接修改集合，而不是创建新的集合。例如：

lst = [1, 2, 3, 4, 5, 6]
new_lst = [i for i in lst if i > 3]

这样做是没问题的，但会创建一个新的集合。为什么Python的集合没有一个像filter()这样的方法，可以直接在原来的集合上进行修改呢？

Answer 1

也许我来得有点晚，但因为没有其他“时间复杂度是O(n)、空间复杂度是O(1)”的解决方案被发布，而且还有人声称这是不可能的，所以我觉得我应该发这个。

# Retains the elements of xs for which p returned true 
def retain(xs, p):
    w = 0
    for x in xs:
        if p(x):
            xs[w] = x
            w += 1
    del xs[w:]

Answer 2

如果你想在原地进行这个操作，可以直接使用

lst[:] = [i for i in lst if i > 3]

这个方法不会更快，也不会节省内存，但是它会直接修改原来的对象，如果你需要这样的效果的话。

Answer 3

其他的回答都是对的；如果你想让所有指向旧列表的名字都指向新列表，可以使用切片赋值。

不过，这并不是真正的原地创建；新列表是先在别的地方创建的。Sven的回答中的链接很不错。

之所以没有一种方法可以真正做到原地操作，是因为像这样创建新列表的时间复杂度是O(n)，而每次真正的原地删除操作的时间复杂度是O(k)，这里的k是从删除点开始到列表末尾的长度。要避免这种情况，Python列表只能使用一些临时存储，这就是你通过切片赋值所做的事情。

如果你不需要把数据存储在list中，这里有一个在collections.deque上进行原地O(n)过滤的例子：

from collections import deque

def dequefilter(deck, condition):
    for _ in xrange(len(deck)):
        item = deck.popleft()
        if condition(item):
            deck.append(item)

deck = deque((1, 2, 3, 4, 5))
dequefilter(deck, lambda x: x > 2) # or operator.gt(2)
print deck
# deque([3, 4, 5])