Eliminar elementos de una lista mientras se itera sin usar memoria extra en Python

Question

Mi problema es simple: tengo una larga lista de elementos que quiero iterar y verificar cada elemento con una condición. Dependiendo del resultado de la condición, me gustaría eliminar el elemento actual de la lista y continuar iterando sobre él como de costumbre.

He leído algunos otros temas sobre este asunto. Se plantean dos soluciones para ser propuestas. Haga un diccionario fuera de la lista (lo que implica hacer una copia de todos los datos que ya están llenando toda la RAM en mi caso). O recorra la lista en reversa (lo que rompe el concepto de alogrithm que quiero implementar).

¿Hay alguna manera mejor o más elegante que esta para hacerlo?

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

Aquí es una respuesta alternativa por si es absolutamente necesario para eliminar los elementos de la lista original, y usted no tienen suficiente memoria para hacer una copia - mover los elementos abajo en la lista sí mismo:

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

Esto moverá cada elemento (en realidad un puntero para cada elemento) exactamente una vez, por lo que será O (N). La sentencia del al final de la función eliminará los elementos no deseados al final de la lista, y creo que Python es lo suficientemente inteligente como para cambiar el tamaño de la lista sin asignar memoria para una nueva copia de la lista.

Answer 2

¿Qué le parece esto?

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

su regreso la nueva lista con excepción de subtle_condition

Answer 3

Por simplicidad, utilice una lista por comprensión:

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

Por supuesto, esto no altera la lista original, por lo que la llamada el código debería ser diferente.

Si realmente quiere mutar la lista (rara vez la mejor opción), caminar hacia atrás es más simple:

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 4

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

y también

li = filter(condition,li) 

Thanks to Dave Kirby

Answer 5

incorporado -in filtro de función está hecho para hacer esto:

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

Answer 6

eliminar elementos de una lista es caro, ya que python tiene que copiar todos los elementos encima de g_index en un lugar. Si el número de elementos que desea eliminar es proporcional a la longitud de la lista N, entonces su algoritmo será O (N ** 2). Si la lista es lo suficientemente larga como para llenar tu RAM, esperarás mucho tiempo para que se complete.

Es más eficiente para crear una copia filtrada de la lista, ya sea usando una lista por comprensión como mostró Marcelo, o utilizar el filtro o funciones itertools.ifilter:

g_list = filter(not_subtle_condition, g_list) 

Si no necesita utilizar la nueva lista y sólo quiere iterar sobre él una vez, entonces es mejor usar ifilter ya que no va a crear una segunda lista:

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

Answer 7

suena como un muy buen caso de uso para la función de filtro.

def should_be_removed(element): 
    return element > 5 

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

Esto, sin embargo, no eliminará la lista mientras se itera (ni la recomiendo).Si por espacio en la memoria (o por otras razones de rendimiento) que realmente lo necesita, puede hacer lo siguiente:

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

Answer 8

Si realiza una iteración inversa, puede eliminar elementos sobre la marcha sin afectar a los siguientes índices que visitará:

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 

El enumerate(reversed(numbers)) es sólo una elección estilística. Se puede usar un rango si eso es más legible para usted:

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

Si tiene que viajar la lista en orden, puede invertir en su lugar con .reverse() antes y después de la iteración invertido. Esto tampoco duplicará tu lista.