如何通过就地过滤来修改python集合？

Question

我想知道,如果Python中有方法修改集合而不创建新集合.例如:

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

工作得很好,但创建了一个新的集合.是否有一个原因,Python集合缺少一个filter()可以修改集合对象的方法(或类似的)？

Answer 1

如果你想这样做,只需使用

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

这不会更快或保存任何内存,但它会更改对象,如果这是您需要的语义.

Answer 2

其他答案都是正确的; 如果您希望指向旧列表的所有名称都指向新列表,则可以使用切片分配.

然而,这不是真正的就地创造; 新列表首先在别处创建.Sven答案中的链接很好.

没有一个真正在原地运行的原因是,当创建这样的新列表是O(n)时,每个真正的就地项目移除本身就是 O(k),其中k长度是列表从删除点开始.使用Python列表避免这种情况的唯一方法是使用一些临时存储,这是您使用切片分配所做的.

collections.deque如果您不需要将数据存储在以下内容中,就可以在a上使用就地O(n)过滤器的示例list:

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])

Answer 3

也许我有点晚了，但由于没有发布其他“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:]