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

relaciones entre conjuntos programacion

Question

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 orden diferente.

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

Answer 1

Espero que el siguiente código funcione en tu 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, independientemente de si están en el mismo orden o no.

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

Answer 2

La mejor forma de hacerlo es ordenando las listas y comparándolas. (El uso de Counter no funcionará con objetos que no son aptos para el hash). Esto es sencillo para los enteros:

sorted(a) == sorted(b)

Se pone 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 función id() como la clave de clasificación.

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

(En Python 2.x no necesita el parámetro key= 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 en qué orden los objetos están dentro, solo que el orden 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 números enteros, así que si lo hace tener objetos de varios tipos, lo mejor es usar explícitamente el ID del objeto).

Si desea comparar los objetos de la lista por valor , primero debe definir qué significa "valor" para los objetos. Entonces necesitarás alguna forma de proporcionar eso como clave (y para Python 3, como un tipo consistente). Una posible forma que funcionaría para muchos objetos arbitrarios es ordenar por su repr() . Por supuesto, esto podría desperdiciar mucho tiempo extra y la creación de memoria cadenas de caracteres repr() para listas grandes y demás.

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 los demás. Luego puede ordenarlos y no preocuparse por el parámetro key= . Por supuesto, también __hash__() definir __hash__() y usar Counter , que será más rápido.

Answer 3

Let 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 lavables ni clasificarlos.

Answer 4

Puedes ordenar ambos:

sorted(a) == sorted(b)

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

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

Answer 5

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 en secuencias de objetos irresolubles también.

Answer 6

Si la lista contiene elementos que no son hashables (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")

Answer 7

Si sabe que los elementos son siempre aptos para el uso, puede usar un Counter() que es O (n)
Si sabe que los artículos son siempre ordenables, puede usar sorted() que es O (n log n)

En el caso general, no puede confiar en que pueda ordenar, o tiene 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)

Answer 8

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

assertCountEqual (primero, segundo, msg = Ninguno)

Prueba esa secuencia primero contiene los mismos elementos que el segundo, 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 conteo en ambas secuencias. Equivalente a: assertEqual (Counter (list (first)), Counter (list (second))) pero también funciona con secuencias de objetos no reemplazables.

Nuevo en la versión 3.2.

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

Answer 9

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

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

O (n log n) : El método sorted() 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 lavables ni ordenables, 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