Comment comparer efficacement deux listes non ordonnées (pas des ensembles) en Python ?

Question

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

a et b doivent être considérés comme égaux, car ils contiennent exactement les mêmes éléments, mais dans un ordre différent.

Le problème est que mes listes réelles seront constituées d'objets (mes instances de classe), et non d'entiers.

Answer 1

O(n) : Le Compteur() est la meilleure méthode (si vos objets sont hachables) :

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

O(n log n) : Le trié() est la meilleure solution (si vos objets peuvent être commandés) :

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

O(n * n) : Si les objets ne sont ni hachables, ni ordonnables, vous pouvez utiliser l'égalité :

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

Answer 2

Vous pouvez trier les deux :

sorted(a) == sorted(b)

A tri par comptage pourrait également être plus efficace (mais elle nécessite que l'objet soit hachable).

>>> 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 3

Si vous savez que les éléments sont toujours hachables, vous pouvez utiliser une fonction Counter() qui est O(n)
Si vous savez que les éléments peuvent toujours être triés, vous pouvez utiliser sorted() ce qui est O(n log n)

Dans le cas général, vous ne pouvez pas compter sur la possibilité de trier ou de disposer des éléments, vous avez donc besoin d'une solution de rechange comme celle-ci, qui est malheureusement O(n^2)

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

Answer 4

La meilleure façon de procéder consiste à trier les listes et à les comparer. (En utilisant Counter ne fonctionnera pas avec des objets qui ne sont pas hachables). C'est simple pour les entiers :

sorted(a) == sorted(b)

La situation est un peu plus délicate avec les objets arbitraires. Si vous vous souciez de l'identité de l'objet, c'est-à-dire de savoir si l'objet même se trouvent dans les deux listes, vous pouvez utiliser la fonction id() comme clé de tri.

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

(Dans Python 2.x, vous n'avez pas besoin de l'option key= car on peut comparer n'importe quel objet à n'importe quel objet. L'ordre est arbitraire mais stable, et fonctionne donc très bien pour cet objectif ; l'ordre des objets n'a pas d'importance, il suffit que l'ordre soit le même pour les deux listes. Dans Python 3, cependant, la comparaison d'objets de types différents est interdite dans de nombreuses circonstances - par exemple, vous ne pouvez pas comparer des chaînes de caractères à des entiers - donc si vous avez des objets de types différents, il vaut mieux utiliser explicitement l'ID de l'objet).

Si vous souhaitez comparer les objets de la liste par valeur, d'autre part, il faut d'abord définir ce que signifie la "valeur" pour les objets. Il faut ensuite trouver un moyen de fournir cette valeur comme clé (et pour Python 3, comme type cohérent). Un moyen potentiel qui fonctionnerait pour un grand nombre d'objets arbitraires est de trier par leur repr() . Bien sûr, cela pourrait faire perdre beaucoup de temps et de mémoire à la construction de l'ordinateur repr() pour les grandes listes, etc.

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

Si les objets sont tous de votre propre type, vous pouvez définir __lt__() afin que l'objet sache se comparer aux autres. Ensuite, vous pouvez simplement les trier sans vous préoccuper de l'ordre des objets. key= paramètre. Bien entendu, vous pouvez également définir __hash__() et utiliser Counter qui sera plus rapide.

Answer 5

Listes a, b

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

Il n'est pas nécessaire de les rendre hachables ou de les trier.