2009-08-12 27 views
10

Estoy en la recta final de un proyecto en el que he estado trabajando. Todo funciona sin problemas, pero tengo un cuello de botella con el que tengo problemas para trabajar.Python: eliminar muchos elementos de una lista

Tengo una lista de tuplas. La lista varía en longitud, por ejemplo, de 40,000 a 1,000,000 de registros. Ahora tengo un diccionario donde todos y cada uno (valor, clave) es una tupla en la lista.

Por lo tanto, podría tener

myList = [(20000, 11), (16000, 4), (14000, 9)...] 
myDict = {11:20000, 9:14000, ...} 

Quiero eliminar cada uno (v, k) tupla de la lista.

Actualmente estoy haciendo:

for k, v in myDict.iteritems(): 
    myList.remove((v, k)) 

Extracción de 838 tuplas de la lista que contiene 20.000 tuplas tarda de 3 - 4 segundos. Lo más probable es que esté eliminando más de 10.000 tuplas de una lista de 1,000,000, así que necesito que sea más rápido.

¿Hay una mejor manera de hacerlo?

Puedo proporcionar el código utilizado para la prueba, además de datos en escabeche de la aplicación real si es necesario.

Respuesta

19

Vas a tener que medir, pero se puede imaginar que esto sea con más prestaciones:

myList = filter(lambda x: myDict.get(x[1], None) != x[0], myList) 

debido a las operaciones de búsqueda que sucede en el dict, que es más adecuado para este tipo de cosas. Sin embargo, tenga en cuenta que esto creará una nueva lista antes de eliminar la anterior; entonces hay una compensación de memoria. Si eso es un problema, sugiéralo repensar el tipo de contenedor como jkp.

Editar: Tenga cuidado, sin embargo, si None está realmente en su lista, tendría que usar un "marcador de posición" diferente.

+1

Wow. Esto trajo mi tiempo de prueba de 3.2 segundos a 0.025 ... Creo que podemos tener un ganador - al menos hasta que Alex Martelli lo haga sonar :) – sberry

+2

Podría vivir siendo el segundo para él :-) – balpha

+0

@ sberry2A: Si eres midiendo 25 ms, el tiempo de pared real podría ser incluso más pequeño que eso; podría ser la resolución del temporizador de su sistema operativo "redondeando" hasta 25 ms. Intente tomar el promedio de 1000 carreras, por ejemplo. –

2

El problema me parece que es el hecho de que está utilizando un list como el contenedor que está tratando de eliminar, y es un tipo totalmente desordenado. Entonces, para encontrar cada elemento en la lista es una operación lineal (O(n)), tiene que iterar sobre toda la lista hasta que encuentre una coincidencia.

Si pudiera cambiar el list por otro contenedor (set?) Que utiliza un hash() de cada artículo para pedirlos, entonces cada coincidencia podría realizarse mucho más rápido.

El código siguiente muestra cómo se puede hacer esto mediante una combinación de ideas ofrecidas por mí y Nick en este tema:

list_set = set(original_list) 
dict_set = set(zip(original_dict.values(), original_dict.keys())) 
difference_set = list(list_set - dict_set) 
final_list = [] 
for item in original_list: 
    if item in difference_set: 
     final_list.append(item) 
+0

Derecho, sin embargo, necesito que se ordenen. Al principio estaba usando un diccionario para almacenar los elementos en myList como v: k para cada uno (k, v) en myList anterior.Pero debido a que necesito que se ordenen, tuve que ordenar los pares k, v del diccionario cada vez que agregué, cambié datos. – sberry

+0

OK, si toma la respuesta provista por Nick Lewis, una vez que tenga el conjunto de elementos para conservar, puede hacer lo siguiente: repetir la lista original y consultar el conjunto para la pertenencia de cada elemento: si el elemento es en el conjunto, agrégalo a tu lista final. Obtendrá una lista ordenada de los artículos que desea. – jkp

5

Cada vez que llame myList.remove, Python tiene que escanear a través de toda la lista para buscar para ese artículo y eliminarlo. En el peor de los casos, cada elemento que busque estará al final de la lista cada vez.

¿Ha intentado hacer la operación "inversa" de:

newMyList = [(v,k) for (v,k) in myList if not k in myDict] 

Pero realmente no estoy seguro de lo bien que se escala, ya sea, ya que iba a hacer una copia de la lista original - podría ser mucho uso de memoria allí.

Probablemente la mejor alternativa aquí es esperar a que Alex Martelli publique un enfoque alucinantemente intuitivo, simple y eficiente.

+0

Esto es mucho más rápido que mi código original. Sin embargo, es aproximadamente 3 - 4 veces más lento que las respuestas de Balpha y Nick Lewis. – sberry

2
[(i, j) for i, j in myList if myDict.get(j) != i] 
+0

Esto es lo mismo que balpha pero usando una lista de comprensión en lugar de filter(). – hughdbrown

+0

Esto debería ser igual que el de Mark Rushakoff, también. – hughdbrown

+0

no lo es, querido. – SilentGhost

2

intentar algo como esto:

myListSet = set(myList) 
myDictSet = set(zip(myDict.values(), myDict.keys())) 
myList = list(myListSet - myDictSet) 

Esto convertirá myList a un conjunto, se intercambiarán las llaves/valores en myDict y ponerlas en un conjunto, y luego encontrar la diferencia, a su vez, volver a una lista y asignarla nuevamente a myList. :)

+0

Los tiempos aquí son muy, muy similares a los obtenidos con la sugerencia de balpha. Son +/- 4 milisegundos. ¿Es uno potencialmente mejor para listas más grandes? – sberry

+0

balpha probablemente consuma menos memoria. – recursive

0
[i for i in myList if i not in list(zip(myDict.values(), myDict.keys()))] 
+2

¿Has probado esto? Mi lectura de su código es que está haciendo una búsqueda lineal de una tupla en una lista, por lo que esta es O (n^2) para toda la operación. Cada solución votada hasta ahora tendrá un mejor rendimiento que esta. – hughdbrown

+0

Esto también evalúa la expresión a la derecha para cada elemento, yendo a través del 'dict' cada vez. – agf

0

Una lista que contiene un millón de 2-tuplas no es grande en la mayoría de las máquinas que ejecutan Python. Sin embargo, si es absolutamente necesario hacer la eliminación in situ, aquí hay una manera limpia de hacerlo correctamente:

def filter_by_dict(my_list, my_dict): 
    sentinel = object() 
    for i in xrange(len(my_list) - 1, -1, -1): 
     key = my_list[i][1] 
     if my_dict.get(key, sentinel) is not sentinel: 
      del my_list[i] 

actualización En realidad cada uno del los costos de O (n) barajar los punteros de la lista hacia abajo usando memmove de C(), entonces si hay d dels, es O(n*d) no O(n**2). Tenga en cuenta que (1) el OP sugiere que d == 0.01 * n y (2) el esfuerzo de O(n*d) es copiar un puntero a otro lugar en la memoria ... por lo que este método podría de hecho ser más rápido de lo que indicaría un vistazo rápido. Puntos de referencia, ¿alguien?

¿Qué vas a hacer con la lista después de has eliminado los elementos que están en el dict? ¿Es posible llevar el filtro dict al siguiente paso?

+0

Si va a hacer eso, también puede generar la lista de claves para eliminar y hacerlas en orden inverso. Me parece un poco más idiomático. delete_me = [i para i, v en enumerate (my_list) si v no está en my_dict]; para i en reversa (delete_me): del my_list [i]; Además, Beazley afirma que el operador interno es más rápido que el método dict.get-method, FWIW. – hughdbrown

+0

Argh. delete_me = [i para i, v en enumerate (mi_lista) si v [1] no en my_dict]; – hughdbrown

+0

(1) Si hacerlo en tres pasos (incluyendo la construcción de una lista temporal y revertirlo) es "idiomático", entonces "idiomático" es malo. (2) el uso de dict.get tiene la misma semántica que el uso de OP de list.remove: tanto k como v deben coincidir entre list y dict. El OP no ha indicado lo contrario. (3) En cualquier caso, usted quiso decir "v [1] en mi dict" no "v [1] no en dict" - el dict contiene los que se eliminarán. Optibeazation muy prematura ;-) –

9

para eliminar alrededor de 10.000 tuplas de una lista de alrededor de 1.000.000, si los valores son hashable, el enfoque más rápido debería ser:

totoss = set((v,k) for (k,v) in myDict.iteritems()) 
myList[:] = [x for x in myList if x not in totoss] 

La preparación del conjunto es un pequeño costo por única vez, cosa que ahorra haciendo tuple desempacando y reempaquetando, o indexando tuplas, muchas veces. Asignar a myList[:] en lugar de asignar a myList también es importante desde el punto de vista semántico (en caso de que haya otras referencias a myList, no basta con volver a enlazar el nombre; realmente desea volver a enlazar el contenido ! -).

No tengo sus datos de prueba para hacer la medición de tiempo yo mismo, ¡ay !, pero, ¡hágamelo saber cómo funciona en nuestros datos de prueba!

Si los valores no se hashable (por ejemplo, que son sub-listas, por ejemplo), más rápido es probable que:

sentinel = object() 
myList[:] = [x for x in myList if myDict.get(x[0], sentinel) != x[1]] 

o tal vez (no hay que hacer una gran diferencia de cualquier manera, pero sospecho el anterior es mejor - la indexación es más barato que el desembalaje y reempaque):

sentinel = object() 
myList[:] = [(a,b) for (a,b) in myList if myDict.get(a, sentinel) != b] 

En estas dos variantes del idioma centinela se utiliza para alejar contra los valores de None (que no es un problema para el conjunto preferido a base de enfoque - ¡si los valores son manejables!) como va a ser ser mucho más barato que if a not in myDict or myDict[a] != b (que requiere dos índices en myDict).

+1

Creo que todos estábamos esperando ver su respuesta. (Nota: un error menor en la primera línea de código ('i')) – Anon

+1

tx para la detección de errores tipográficos, corrigiéndolo ahora –

Cuestiones relacionadas