Saltar al contenido

¿Cómo comparar de manera eficiente dos listas desordenadas (no conjuntos) en Python?

Solución:

Sobre): Los Encimera() El método es el mejor (si sus objetos son hash):

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

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

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

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

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

Puede ordenar ambos:

sorted(a) == sorted(b)

Una clasificación de conteo también podría ser más eficiente (pero requiere que el objeto sea hash).

>>> 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 siempre se pueden hash, puede utilizar un Counter() que es O (n)
Si sabe que los elementos siempre se pueden ordenar, 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 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)
¡Haz clic para puntuar esta entrada!
(Votos: 0 Promedio: 0)


Tags :

Utiliza Nuestro Buscador

Deja una respuesta

Tu dirección de correo electrónico no será publicada. Los campos obligatorios están marcados con *