¿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 & b deben considerarse iguales, porque tienen exactamente los mismos elementos, solo que en un orden diferente.

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

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

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

O (n log n) : el método sorted () es el siguiente mejor (si sus objetos son ordenables):

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

O (n * n) : si los objetos no son hashables ni pueden pedirse, 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)

Una ordenación 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 utilizables, puede usar uno Counter()que sea O (n)
Si sabe que los elementos siempre se pueden ordenar, puede usar sorted()cuál es O (n log n)

En el caso general, no puede confiar en poder ordenar o tener los elementos, por lo que necesita un respaldo 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 ordenar las listas y compararlas. (El uso Counterno funcionará con objetos que no sean hashaable). Esto es sencillo para los enteros:

sorted(a) == sorted(b)

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

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

(En Python 2.x en realidad no necesita el key=parámetro, porque puede comparar cualquier objeto con cualquier objeto. El orden es arbitrario pero estable, por lo que funciona bien para este propósito; no importa el orden de los objetos) en, solo que el orden es el mismo para ambas listas. En Python 3, sin embargo, 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 tendrá objetos de varios tipos, lo mejor es usar explícitamente la ID del objeto).

Si desea comparar los objetos en la lista por valor, por otro lado, primero debe definir qué significa "valor" para los objetos. Entonces 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 ellos repr(). Por supuesto, esto podría desperdiciar mucho tiempo extra y crear repr()cadenas de memoria para listas grandes, etc.

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

Si los objetos son todos de su propio tipo, puede definirlos __lt__()para que el objeto sepa cómo compararse con los demás. Luego puede ordenarlos y no preocuparse por el key=parámetro. Por supuesto, también podría definir __hash__()y usar Counter, lo que será más rápido.

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

ClaimCountEqual (primero, segundo, msg = Ninguno)

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

Los elementos duplicados no se ignoran al comparar primero y segundo. Verifica si cada elemento tiene el mismo recuento en ambas secuencias. Equivalente a: afirmarEqual (Counter (list (first)), Counter (list (second))) pero también funciona con secuencias de objetos no compartibles.

Nuevo en la versión 3.2.

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

Si la lista contiene elementos que no se pueden compartir (como una lista de objetos), es posible que pueda usar la clase Counter 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")

Espero que el siguiente 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 las listas ay bsean iguales, independientemente de si están en el mismo orden o no.

Para una mejor comprensión, consulte mi respuesta en esta pregunta

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

Funciona también en secuencias de objetos no compartibles.

Deje 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 es necesario hacerlos hashaable o ordenarlos.

El uso del unittestmódulo le brinda un enfoque limpio y estándar.

import unittest

test_object = unittest.TestCase()
test_object.assertCountEqual(a, b)