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

Mi problema es simple: tengo una larga lista de elementos que quiero recorrer y comprobar cada elemento contra una condición. Dependiendo del resultado de la condición, me gustaría eliminar el elemento actual de la lista y continuar la iteración como de costumbre.

He leído algunos otros hilos sobre este asunto. Dos soluciones de costura a proponer. O bien haga un diccionario 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 camine por la lista a la inversa (lo que rompe el concepto del algoritmo que quiero implementar).

¿Hay alguna forma 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 

Aquí hay una respuesta alternativa si, absolutamente, tiene que eliminar los elementos de la lista original y no tiene suficiente memoria para hacer una copia; mueva los elementos hacia abajo de la lista usted 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 a cada elemento) exactamente una vez, por lo que será O (N). La statement del al final de la función eliminará cualquier elemento no deseado 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.

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

y también

 li = filter(condition,li) 

Gracias a Dave Kirby

eliminar elementos de una lista es costoso, ya que Python tiene que copiar todos los elementos arriba de g_index en un solo 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 su RAM, estará esperando mucho tiempo para que se complete.

Es más eficiente crear una copia filtrada de la lista, ya sea utilizando una comprensión de la lista como mostró Marcelo, o usar las funciones de filtro o itertools.ifilter:

 g_list = filter(not_subtle_condition, g_list) 

Si no necesita usar la nueva lista y solo quiere iterar sobre ella una vez, entonces es mejor usar ifilter ya que eso no creará una segunda lista:

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

La función de filtro incorporada está hecha solo para hacer esto:

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

¿Qué tal esto?

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

devuelve la nueva lista con excepción de subtle_condition

Para simplificar, use una lista de 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 el código de llamada tendría que ser diferente.

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

 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] 

Suena como un 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 durante la iteración (ni la recomiendo). Si por espacio de memoria (u otras razones de rendimiento) 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 

Si realiza una iteración inversa, puede eliminar elementos sobre la marcha sin afectar los próximos í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 

La enumerate(reversed(numbers)) es solo una opción estilística. Puedes usar un rango si eso es más legible para ti:

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

Si necesita recorrer la lista en orden, puede revertirla en su lugar con .reverse() antes y después de la iteración inversa. Esto tampoco duplicará tu lista.