Forma rápida de eliminar algunos elementos de una lista / cola

Este es un seguimiento de una pregunta similar que plantea la mejor manera de escribir

for item in somelist: if determine(item): code_to_remove_item 

Y parece que el consenso fue en algo como

 somelist[:] = [x for x in somelist if not determine(x)] 

Sin embargo, creo que si solo está eliminando algunos elementos, la mayoría de los elementos se están copiando en el mismo objeto, y tal vez sea lento. En una respuesta a otra pregunta relacionada, alguien sugiere:

 for item in reversed(somelist): if determine(item): somelist.remove(item) 

Sin embargo, aquí, list.remove buscará el elemento, que es O (N) en la longitud de la lista. Puede ser que estemos limitados en el sentido de que la lista se representa como una matriz, en lugar de una lista vinculada, por lo que la eliminación de elementos tendrá que mover todo después de ella. Sin embargo, se sugiere aquí que collections.dequeue se representa como una lista doblemente enlazada. Entonces debería ser posible eliminar en O (1) mientras se está iterando. ¿Cómo podríamos lograr esto?

Actualización : También hice algunas pruebas con el siguiente código:

 import timeit setup = """ import random random.seed(1) b = [(random.random(),random.random()) for i in xrange(1000)] c = [] def tokeep(x): return (x[1]>.45) and (x[1]<.5) """ listcomp = """ c[:] = [x for x in b if tokeep(x)] """ filt = """ c = filter(tokeep, b) """ print "list comp = ", timeit.timeit(listcomp,setup, number = 10000) print "filtering = ", timeit.timeit(filt,setup, number = 10000) 

y consiguió:

 list comp = 4.01255393028 filtering = 3.59962391853 

La lista de comprensión es la solución asintóticamente óptima:

 somelist = [x for x in somelist if not determine(x)] 

Solo hace una pasada sobre la lista, por lo que se ejecuta en tiempo O (n). Ya que necesita llamar a determinar () en cada objeto, cualquier algoritmo requerirá al menos operaciones O (n). La lista de comprensión tiene que hacer algunas copias, pero solo está copiando referencias a los objetos que no copian los objetos en sí.

Eliminar elementos de una lista en Python es O (n), por lo que cualquier cosa que se elimine, haga clic o borre dentro del bucle será O (n ** 2).

Además, en CPython la comprensión de las listas es más rápida que para los bucles.

Si necesita eliminar un elemento en O (1) puede usar HashMaps

Ya que list.remove es equivalente a del list[list.index(x)] , puedes hacer:

 for idx, item in enumerate(somelist): if determine(item): del somelist[idx] 

Pero: no debes modificar la lista mientras estés iterando sobre ella. Te morderá, tarde o temprano. Use el filter o la lista de comprensión primero, y optimice más tarde.

Un deque está optimizado para la eliminación de la cabeza y la cola, no para la eliminación arbitraria en el medio. La eliminación en sí es rápida, pero aún tiene que atravesar la lista hasta el punto de eliminación. Si está iterando a lo largo de toda la longitud, entonces la única diferencia entre filtrar un deque y filtrar una lista (usando un filter o una comprensión) es la sobrecarga de la copia, que en el peor de los casos es un múltiplo constante; sigue siendo una operación O (n). Además, tenga en cuenta que los objetos de la lista no se están copiando, solo las referencias a ellos. Así que no es mucho más caro.

Es posible que pueda evitar copiar así, pero no tengo ninguna razón en particular para creer que esto sea más rápido que una simple comprensión de lista, probablemente no:

 write_i = 0 for read_i in range(len(L)): L[write_i] = L[read_i] if L[read_i] not in ['a', 'c']: write_i += 1 del L[write_i:] 

Tomé una puñalada en esto. Mi solución es más lenta, pero requiere menos sobrecarga de memoria (es decir, no crea una nueva matriz). ¡Incluso podría ser más rápido en algunas circunstancias!

Este código ha sido editado desde su primera publicación.

Tuve problemas con el tiempo, podría estar haciendo esto mal.

 import timeit setup = """ import random random.seed(1) global b setup_b = [(random.random(), random.random()) for i in xrange(1000)] c = [] def tokeep(x): return (x[1]>.45) and (x[1]<.5) # define and call to turn into psyco bytecode (if using psyco) b = setup_b[:] def listcomp(): c[:] = [x for x in b if tokeep(x)] listcomp() b = setup_b[:] def filt(): c = filter(tokeep, b) filt() b = setup_b[:] def forfilt(): marked = (i for i, x in enumerate(b) if tokeep(x)) shift = 0 for n in marked: del b[n - shift] shift += 1 forfilt() b = setup_b[:] def forfiltCheating(): marked = (i for i, x in enumerate(b) if (x[1] > .45) and (x[1] < .5)) shift = 0 for n in marked: del b[n - shift] shift += 1 forfiltCheating() """ listcomp = """ b = setup_b[:] listcomp() """ filt = """ b = setup_b[:] filt() """ forfilt = """ b = setup_b[:] forfilt() """ forfiltCheating = ''' b = setup_b[:] forfiltCheating() ''' psycosetup = ''' import psyco psyco.full() ''' print "list comp = ", timeit.timeit(listcomp, setup, number = 10000) print "filtering = ", timeit.timeit(filt, setup, number = 10000) print 'forfilter = ', timeit.timeit(forfilt, setup, number = 10000) print 'forfiltCheating = ', timeit.timeit(forfiltCheating, setup, number = 10000) print '\nnow with psyco \n' print "list comp = ", timeit.timeit(listcomp, psycosetup + setup, number = 10000) print "filtering = ", timeit.timeit(filt, psycosetup + setup, number = 10000) print 'forfilter = ', timeit.timeit(forfilt, psycosetup + setup, number = 10000) print 'forfiltCheating = ', timeit.timeit(forfiltCheating, psycosetup + setup, number = 10000) 

Y aquí están los resultados

 list comp = 6.56407690048 filtering = 5.64738512039 forfilter = 7.31555104256 forfiltCheating = 4.8994679451 now with psyco list comp = 8.0485959053 filtering = 7.79016900063 forfilter = 9.00477004051 forfiltCheating = 4.90830993652 

Debo estar haciendo algo mal con psyco, porque en realidad se está ejecutando más lento.