126 votos

Cómo de manera eficiente comparar dos listas no ordenadas (no juegos) 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, sólo que en diferente orden.

La cosa es que mis listas reales se componen de objetos (mi instancias de la clase), no enteros.

218voto

Raymond Hettinger Puntos 50330

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

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

O(n log n): La ordenada() el método es el siguiente mejor (si los objetos están disponible):

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

O(n * n): Si los objetos no son ni hashable, ni hacer pedidos, se puede utilizar 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

15voto

Mark Byers Puntos 318575

Usted puede ordenar tanto:

sorted(a) == sorted(b)

Un recuento de especie también podría ser más eficiente (pero se requiere que el objeto 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

11voto

gnibbler Puntos 103484

Si usted sabe que los artículos son siempre hashable, puede utilizar una Counter() que es O(n)
Si usted sabe que los elementos siempre se puede ordenar, puede utilizar sorted() que es O(n log n)

En el caso general, usted no puede confiar en ser capaz de ordenar, o dispone de los elementos, por lo que necesita una reserva como este, que es, por desgracia O(n^2)

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

5voto

kindall Puntos 60645

La mejor manera de hacer esto es a través de la clasificación de las listas y la comparación entre ellas. (El uso de Counter no funciona con objetos que no son hashable.) Esto es sencillo para los números enteros:

sorted(a) == sorted(b)

Se pone un poco más complicado con objetos arbitrarios. Si usted se preocupa por la identidad de los objetos, es decir, si el mismo los objetos están en ambas listas, puede utilizar el id() función como clave de ordenación.

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

(En Python 2.x no necesita realmente el key= parámetro, porque usted puede comparar cualquier objeto a cualquier objeto. El orden es arbitrario, pero estable, por lo que funciona bien para este propósito; no importa el orden en que los objetos son, sólo 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 se puede comparar cadenas a enteros -- así que si usted va a tener objetos de diferentes tipos, la mejor manera de utilizar explícitamente el ID del objeto.)

Si desea comparar los objetos de la lista por valor, por otro lado, primero es necesario definir qué "valor" significa para los objetos. Entonces usted necesita alguna manera de proporcionar una clave (y para Python 3, como una constante de tipo). Una forma potencial de que el trabajo para una gran cantidad de objetos arbitrarios es ordenar por sus repr(). Por supuesto, esto podría perder un montón de tiempo extra y de construcción de memoria repr() cadenas de las listas de gran tamaño y así sucesivamente.

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

Si los objetos son todos los de su propio tipo, puede definir __lt__() de ellos, así que el objeto sabe cómo comparar sí mismo a los demás. A continuación, puedes ordenarlos y no se preocupe acerca de la key= parámetro. Por supuesto, usted puede también definir __hash__() y el uso de Counter, que será más rápido.

1voto

Umur Kontacı Puntos 12524

Deje a,b, listas de

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 o clasificarlas.

Iteramos.com

Iteramos es una comunidad de desarrolladores que busca expandir el conocimiento de la programación mas allá del inglés.
Tenemos una gran cantidad de contenido, y también puedes hacer tus propias preguntas o resolver las de los demás.

Powered by:

X