在Python中迭代时无额外内存移除列表项

Question

我的问题很简单：我有一个很长的元素列表，我想逐个检查每个元素是否符合某个条件。根据条件的结果，我想删除当前的元素，然后继续正常遍历这个列表。

我看过一些其他的讨论，似乎有两种解决方案。第一种是把列表变成一个字典（这意味着要复制所有的数据，而这些数据已经占用了我所有的内存）。第二种是反向遍历列表（这又违背了我想要实现的算法的概念）。

有没有比这更好或者更优雅的方法呢？

def walk_list(list_of_g):
    g_index = 0
    while g_index < len(list_of_g):
        g_current = list_of_g[g_index]
        if subtle_condition(g_current):
            list_of_g.pop(g_index)
        else:
            g_index = g_index + 1

Answer 1

从列表中删除项目是比较耗费时间的，因为Python需要把被删除项目后面的所有项目都往前挪一个位置。如果你要删除的项目数量和列表的长度N成正比，那么你的算法效率会是O(N**2)。如果列表足够长，甚至占满你的内存，那你可能要等很久才能完成这个操作。

更有效的方法是创建一个过滤后的列表副本，可以使用列表推导式，就像Marcelo展示的那样，或者使用filter或itertools.ifilter函数：

g_list = filter(not_subtle_condition, g_list)

如果你只想遍历这个新列表一次，而不需要保存它，那么使用ifilter会更好，因为它不会创建第二个列表：

for g_current in itertools.ifilter(not_subtle_condtion, g_list):
    # do stuff with g_current

Answer 2

li = [ x for x in li if condition(x)]

还有

li = filter(condition,li) 

感谢 Dave Kirby

Answer 3

这里有一个替代方案，如果你真的必须从原始列表中删除项目，并且没有足够的内存来制作副本——你可以自己把项目往下移动：

def walk_list(list_of_g):
    to_idx = 0
    for g_current in list_of_g:
        if not subtle_condition(g_current):
            list_of_g[to_idx] = g_current
            to_idx += 1
    del list_of_g[to_idx:]

这样做会把每个项目（实际上是每个项目的指针）移动一次，所以时间复杂度是O(N)。函数最后的del语句会删除列表末尾的多余项目，我认为Python足够聪明，可以在不为新副本分配内存的情况下调整列表的大小。