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

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 ont exactement les mêmes éléments, mais dans un ordre différent.

Le fait est que mes listes réelles seront constituées d'objets (mes instances de classe), pas d'entiers.

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

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

O (n log n) : La méthode sorted () est la meilleure suivante (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 triables, 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

Vous pouvez trier les deux:

sorted(a) == sorted(b)

Un tri par comptage pourrait également être plus efficace (mais il 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

Si vous savez que les éléments sont toujours hachables, vous pouvez utiliser a Counter()qui est O (n)
Si vous savez que les éléments sont toujours triables, 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 d'avoir les éléments, vous avez donc besoin d'une solution de secours 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)

La meilleure façon d'y parvenir est de trier les listes et de les comparer. (L'utilisation Counterne fonctionnera pas avec des objets qui ne sont pas hachables.) C'est simple pour les entiers:

sorted(a) == sorted(b)

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

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

(En Python 2.x, vous n'avez pas réellement besoin du key=paramètre, car vous pouvez comparer n'importe quel objet à n'importe quel objet. L'ordre est arbitraire mais stable, donc cela fonctionne bien à cette fin; peu importe l'ordre dans lequel les objets sont dans, seulement que l'ordre est le même pour les deux listes. En 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 à des entiers - donc si vous avez des objets de différents types, il est préférable d'utiliser explicitement l'ID de l'objet.)

Si vous souhaitez comparer les objets de la liste par valeur, par contre, vous devez d'abord définir ce que signifie «valeur» pour les objets. Ensuite, vous aurez besoin d'un moyen de fournir cela en tant que clé (et pour Python 3, en tant que type cohérent). Un moyen potentiel qui fonctionnerait pour de nombreux objets arbitraires est de trier par leur repr(). Bien sûr, cela pourrait perdre beaucoup de temps supplémentaire et de créer des repr()chaînes de mémoire pour les grandes listes, etc.

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

Si les objets sont tous de vos propres types, vous pouvez les définir __lt__()pour que l'objet sache se comparer aux autres. Ensuite, vous pouvez simplement les trier et ne pas vous soucier du key=paramètre. Bien sûr, vous pouvez également définir __hash__()et utiliser Counter, ce qui sera plus rapide.

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

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

Testez que la séquence contient d'abord les mêmes éléments que la seconde, quel que soit leur ordre. Si ce n'est pas le cas, un message d'erreur répertoriant les différences entre les séquences sera généré.

Les éléments en double ne sont pas ignorés lors de la comparaison des premier et second. Il vérifie si chaque élément a le même nombre dans les deux séquences. Équivaut à: assertEqual (Counter (list (first)), Counter (list (second))) mais fonctionne également avec des séquences d'objets non détachables.

Nouveau dans la version 3.2.

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

Si la liste contient des éléments qui ne sont pas hachables (comme une liste d'objets), vous pourrez peut-être utiliser la classe de compteur et la fonction id () comme:

from collections import Counter
...
if Counter(map(id,a)) == Counter(map(id,b)):
    print("Lists a and b contain the same objects")

J'espère que le morceau de 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'

Cela garantira que tous les éléments des deux listes a& bsont identiques, qu'ils soient dans le même ordre ou non.

Pour une meilleure compréhension, reportez-vous à ma réponse à cette question

Si la comparaison doit être effectuée dans un contexte de test, utilisez assertCountEqual(a, b)( py>=3.2) et assertItemsEqual(a, b)( 2.7<=py<3.2).

Fonctionne également sur des séquences d'objets non détachables.

Soit a, b 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.

L'utilisation du unittestmodule vous donne une approche claire et standard.

import unittest

test_object = unittest.TestCase()
test_object.assertCountEqual(a, b)