Comment comparer efficacement deux listes non ordonnées (et non des sets) en Python?

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

a & b doivent être considérés comme égaux, parce qu'ils ont exactement les mêmes éléments, seulement dans un ordre différent.

la chose est, mes listes actuelles seront composées d'objets (mes instances de classe), pas d'entiers.

91
demandé sur Raymond Hettinger 2011-10-20 02:13:02

9 réponses

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

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

O (N log n) : le trié () la méthode est la suivante (si vos objets sont commandables): 

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

O(n * n) : si les objets ne sont ni peut utiliser é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
153
répondu Raymond Hettinger 2016-08-24 08:17:09

vous pouvez trier les deux: 

sorted(a) == sorted(b)

A counting sort pourrait aussi être plus efficace (mais il exige 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
12
répondu Mark Byers 2011-10-19 22:27:10

si vous savez que les articles sont toujours hachables, vous pouvez utiliser un Counter() qui est O(n)

Si vous savez que les articles sont toujours sortable, vous pouvez utiliser sorted() qui est O(N log n)

dans le cas général vous ne pouvez pas compter sur la capacité de trier, ou a les éléments, donc vous avez besoin d'un repli comme celui-ci, qui est malheureusement O (N^2) 

len(a)==len(b) and all(a.count(i)==b.count(i) for i in a)
10
répondu John La Rooy 2011-10-19 23:00:33

La meilleure façon de le faire est de trier les listes et de les comparer. (Utiliser Counter ne fonctionnera pas avec les objets qui ne sont pas hachables.) Ceci est simple pour les entiers: 

sorted(a) == sorted(b)

ça devient un peu plus délicat avec les objets arbitraires. Si vous vous souciez de l'identité de l'objet, c'est-à-dire si les objets même sont dans les deux listes, vous pouvez utiliser la fonction id() comme clé de tri. 

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

(En Python 2.x vous n'avez pas besoin du paramètre key= , car vous pouvez comparer n'importe quel objet à n'importe quel autre. L'ordre est arbitraire mais stable, donc il fonctionne très bien dans ce but; peu importe l'ordre dans lequel les objets sont, seulement que l'ordre est le même pour les deux listes. En Python 3, cependant, comparer des objets de différents types est interdit 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 différents types, mieux vaut utilisez explicitement L'ID de l'objet.)

Si vous voulez comparer les objets de la liste par valeur", 1519160920", d'autre part, vous devez d'abord définir ce que "valeur" désigne, pour les objets. Alors vous aurez besoin d'un moyen pour fournir cela comme une clé (et pour Python 3, comme un type cohérent). Un moyen potentiel qui pourrait fonctionner pour beaucoup d'objets arbitraires est de trier par leur repr() . Bien sûr, cela pourrait faire perdre beaucoup de temps supplémentaire et de construire la mémoire repr() chaînes pour grandes listes et ainsi de suite. 

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

si les objets sont tous vos propres types, vous pouvez définir __lt__() sur eux de sorte que l'objet sait se comparer à d'autres. Ensuite, vous pouvez simplement les trier et ne pas vous soucier du paramètre key= . Bien sûr, vous pouvez également définir __hash__() et l'utilisation Counter , qui sera plus rapide.

5
répondu kindall 2011-10-19 22:31:17

si la liste contient des éléments qui ne sont pas hachables (comme une liste d'objets), vous pourriez être en mesure d'utiliser la Counter Class et la fonction id() telle que: 

from collections import Counter
...
if Counter(map(id,a)) == Counter(map(id,b)):
    print("Lists a and b contain the same objects")
3
répondu Mars 2017-01-02 21:45:17

si la comparaison doit être effectuée dans un contexte d'essai, utiliser assertCountEqual(a, b) ( py>=3.2 ) et assertItemsEqual(a, b) ( 2.7<=py<3.2 ).

fonctionne aussi sur des séquences d'objets inhashables.

2
répondu jarekwg 2016-01-09 14:13:54

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

assertCountEqual(premier, deuxième, msg=None)

Test de cette séquence, la première contient les mêmes éléments que la seconde, indépendamment de leur ordre. Quand ils ne le font pas, un message d'erreur énumérant les différences entre les séquences sera généré.

les éléments dupliqués ne sont pas ignorés lors de la comparaison deuxième. Il vérifie que chaque élément a le même nombre dans les deux séquences. Équivalent à: assertEqual(Compteur(liste(premier)), Compteur(liste(seconde))) mais fonctionne avec des séquences de unhashable objets.

nouveau dans la version 3.2.

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

2
répondu cleder 2016-10-13 09:00:33

soit a,b des listes 

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

pas besoin de les rendre hachables ou de les trier.

1
répondu Umur Kontacı 2011-10-19 23:43:05

j'espère que le code ci-dessous pourrait fonctionner dans votre cas: - 

if ((len(a) == len(b)) and
   (all(i in a for i in b))):
    print 'True'
else:
    print 'False'

ainsi, tous les éléments des deux listes a et b seront identiques, qu'ils soient dans le même ordre ou non.

pour une meilleure compréhension, référez-vous à ma réponse dans cette question

1
répondu Pabitra Pati 2017-05-23 12:09:37