¿Cómo comparar eficientemente dos listas desordenadas (no conjuntos) en Python?

a = [1, 2, 3, 1, 2, 3] b = [3, 2, 1, 3, 2, 1] 

a y b deben considerarse iguales, porque tienen exactamente los mismos elementos, solo que en un orden diferente.

La cuestión es que mis listas reales constarán de objetos (mis instancias de clase), no de enteros.

O (n) : el método Counter () es el mejor (si sus objetos son hashable):

 def compare(s, t): return Counter(s) == Counter(t) 

O (n log n) : el método ordenado () es el siguiente mejor (si sus objetos se pueden ordenar):

 def compare(s, t): return sorted(s) == sorted(t) 

O (n * n) : si los objetos no son hashable, ni se pueden ordenar, puede usar la igualdad:

 def compare(s, t): t = list(t) # make a mutable copy try: for elem in s: t.remove(elem) except ValueError: return False return not t 

Puedes ordenar ambos:

 sorted(a) == sorted(b) 

Un orden de conteo también podría ser más eficiente (pero requiere que el objeto sea hashable).

 >>> from collections import Counter >>> a = [1, 2, 3, 1, 2, 3] >>> b = [3, 2, 1, 3, 2, 1] >>> print (Counter(a) == Counter(b)) True 

Si sabe que los elementos son siempre hashable, puede usar un Counter() que es O (n)
Si sabe que los elementos siempre se pueden sorted() , puede usar sorted() que es O (n log n)

En el caso general, no puede confiar en poder ordenar, o tiene los elementos, por lo que necesita un repliegue como este, que desafortunadamente es O (n ^ 2)

 len(a)==len(b) and all(a.count(i)==b.count(i) for i in a) 

La mejor manera de hacerlo es ordenando las listas y comparándolas. (El uso de Counter no funcionará con objetos que no sean hashable). Esto es sencillo para los enteros:

 sorted(a) == sorted(b) 

Se pone un poco más complicado con los objetos arbitrarios. Si le importa la identidad del objeto, es decir, si los mismos objetos están en ambas listas, puede usar la función id() como la clave de clasificación.

 sorted(a, key=id) == sorted(b, key==id) 

(En Python 2.x, en realidad no necesita el parámetro key= , porque puede comparar cualquier objeto con cualquier objeto. El ordenamiento es arbitrario pero estable, por lo que funciona bien para este propósito; no importa qué orden los objetos están en, solo que el ordenamiento es el mismo para ambas listas. Sin embargo, en Python 3, la comparación de objetos de diferentes tipos no está permitida en muchas circunstancias, por ejemplo, no puede comparar cadenas con enteros, por lo que si tener objetos de varios tipos, lo mejor es usar explícitamente la ID del objeto.)

Por otro lado, si desea comparar los objetos en la lista por valor , primero debe definir qué significa “valor” para los objetos. Luego, necesitará alguna forma de proporcionar eso como una clave (y para Python 3, como un tipo consistente). Una forma potencial que funcionaría para muchos objetos arbitrarios es ordenarlos por su repr() . Por supuesto, esto podría desperdiciar una gran cantidad de tiempo extra y memoria al crear cadenas repr() para listas grandes y así sucesivamente.

 sorted(a, key=repr) == sorted(b, key==repr) 

Si los objetos son todos sus propios tipos, puede definir __lt__() en ellos para que el objeto sepa cómo compararse con otros. Entonces puede ordenarlos y no preocuparse por el parámetro key= . Por supuesto, también puede definir __hash__() y usar Counter , que será más rápido.

Si la lista contiene elementos que no son hashable (como una lista de objetos), es posible que pueda usar la Clase de contador y la función id () como:

 from collections import Counter ... if Counter(map(id,a)) == Counter(map(id,b)): print("Lists a and b contain the same objects") 

Si la comparación se realiza en un contexto de prueba, use assertCountEqual(a, b) ( py>=3.2 ) y assertItemsEqual(a, b) ( 2.7<=py<3.2 ).

Funciona en secuencias de objetos inestables también.

https://docs.python.org/3.5/library/unittest.html#unittest.TestCase.assertCountEqual

assertCountEqual (primero, segundo, msg = ninguno)

Pruebe que la secuencia primero contiene los mismos elementos que la segunda, independientemente de su orden. Cuando no lo hagan, se generará un mensaje de error que enumera las diferencias entre las secuencias.

Los elementos duplicados no se ignoran cuando se comparan primero y segundo. Verifica si cada elemento tiene el mismo conteo en ambas secuencias. Equivalente a: assertEqual (Contador (lista (primero)), Contador (lista (segundo))) pero también funciona con secuencias de objetos imposibles de lavar.

Nuevo en la versión 3.2.

o en 2.7: https://docs.python.org/2.7/library/unittest.html#unittest.TestCase.assertItemsEqual

Deja a, b listas

 def ass_equal(a,b): try: map(lambda x: a.pop(a.index(x)), b) # try to remove all the elements of b from a, on fail, throw exception if len(a) == 0: # if a is empty, means that b has removed them all return True except: return False # b failed to remove some items from a 

No hay necesidad de hacerlos hashable u ordenarlos.

Espero que la siguiente pieza de código funcione en su caso:

 if ((len(a) == len(b)) and (all(i in a for i in b))): print 'True' else: print 'False' 

Esto asegurará que todos los elementos en ambas listas a y b sean iguales, sin importar si están en el mismo orden o no.

Para una mejor comprensión, refiérase a mi respuesta en esta pregunta