迭代时从列表中删除项目而不使用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

从列表中删除项目是昂贵的,因为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 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足够智能,可以调整列表大小,而无需为列表的新副本分配内存.