在 Python 中迭代时从列表中删除项目而不使用额外的内存

Question

我的问题很简单：我有一个很长的元素列表，我想遍历这些元素并根据条件检查每个元素。根据条件的结果，我想删除列表的当前元素，并像往常一样继续迭代它。

我已经阅读了有关此问题的其他一些主题。提出了两种解决方案。要么从列表中创建一个字典（这意味着在我的例子中复制已经填满所有 RAM 的所有数据）。要么反向遍历列表（这打破了我想要实现的算法的概念）。

还有比这更好或更优雅的方法吗？

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

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

还有

li = filter(condition,li) 

感谢 Dave Kirby

Answer 2

如果您绝对必须从原始列表中删除项目，并且您没有足够的内存来制作副本，那么这里有一个替代答案 - 自己将项目向下移动到列表中：

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

这将移动每个项目（实际上是一个指向每个项目的指针） item) 恰好出现一次，因此时间复杂度为 O(N)。函数末尾的 del 语句将删除列表末尾的任何不需要的项目，并且我认为 Python 足够智能，可以调整列表的大小，而无需为列表的新副本分配内存。

Answer 3

从列表中删除项目的成本很高，因为 python 必须将 g_index 之上的所有项目复制到一个位置。如果要删除的项目数量与列表 N 的长度成正比，那么您的算法将是 O(N**2)。如果列表足够长，足以填满您的 RAM，那么您将等待很长时间才能完成。

创建列表的过滤副本会更有效，可以使用 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 4

内置过滤器功能就是为了做到这一点：

list_of_g = filter(lambda x: not subtle_condition(x), list_of_g)

Answer 5

这个怎么样？

[x for x in list_of_g if not subtle_condition(x)]

它返回新列表，但微妙_条件除外

Answer 6

为了简单起见，使用列表理解：

def walk_list(list_of_g):
    return [g for g in list_of_g if not subtle_condition(g)]

当然，这不会改变原始列表，因此调用代码必须不同。

如果你真的想改变列表（很少是最好的选择），向后走更简单：

def walk_list(list_of_g):
    for i in xrange(len(list_of_g), -1, -1):
        if subtle_condition(list_of_g[i]):
            del list_of_g[i]

Answer 7

听起来像是过滤器功能的一个非常好的用例。

def should_be_removed(element):
  return element > 5

a = range(10)
a = filter(should_be_removed, a)

然而，这不会在迭代时删除列表（我也不推荐这样做）。如果出于内存空间（或其他性能原因）您确实需要它，您可以执行以下操作：

i = 0
while i < len(a):
    if should_be_removed(a[i]):
        a.remove(a[i])
    else:
        i+=1
    print a

Answer 8

如果执行反向迭代，则可以动态删除元素，而不会影响您将访问的下一个索引：

numbers = range(20)

# remove all numbers that are multiples of 3
l = len(numbers)
for i, n in enumerate(reversed(numbers)):
    if n % 3 == 0:
        del numbers[l - i - 1]

print numbers

enumerate(reversed(numbers)) 只是一种风格选择。如果您更容易理解，您可以使用范围：

l = len(numbers)
for i in range(l-1, -1, -1):
    n = numbers[i]
    if n % 3 == 0:
        del numbers[i]

如果您需要按顺序遍历列表，则可以在反向迭代之前和之后使用 .reverse() 就地反转它。这也不会重复您的列表。