Jak efektywnie porównać dwie nieuporządkowane listy (nie zestawy) w Pythonie?

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

a i b należy uważać za równe, ponieważ mają dokładnie te same elementy, tylko w różnej kolejności.

Rzecz w tym, że moje rzeczywiste listy będą składać się z obiektów (instancji moich klas), a nie liczb całkowitych.

O (n) : Metoda Counter () jest najlepsza (jeśli twoje obiekty są haszowane):

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

O (n log n) : Metoda sortowana () jest następna w kolejności (jeśli obiekty można uporządkować):

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

O (n * n) : Jeśli obiekty nie są ani hashowalne, ani uporządkowane, możesz użyć równości:

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

Możesz sortować zarówno:

sorted(a) == sorted(b)

Sortowanie przez zliczanie może być również bardziej wydajny (ale wymaga obiektu przeznaczonego do 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

Jeśli wiesz, że elementy są zawsze haszowane, możesz użyć a, Counter()które jest O (n)
Jeśli wiesz, że elementy są zawsze możliwe do sortowania, możesz użyć, sorted()które jest O (n log n)

W ogólnym przypadku nie możesz polegać na możliwości sortowania lub na posiadaniu elementów, więc potrzebujesz takiego rozwiązania awaryjnego, które niestety jest O (n ^ 2)

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

Najlepszym sposobem na to jest sortowanie list i porównywanie ich. (Użycie Counternie zadziała z obiektami, które nie są hashowane). Jest to proste w przypadku liczb całkowitych:

sorted(a) == sorted(b)

Trochę trudniej jest z przypadkowymi obiektami. Jeśli zależy Ci na tożsamości obiektu, tj. Czy te same obiekty znajdują się na obu listach, możesz użyć id()funkcji jako klucza sortowania.

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

(W Pythonie 2.x nie potrzebujesz tego key=parametru, ponieważ możesz porównać dowolny obiekt z dowolnym obiektem. Kolejność jest dowolna, ale stabilna, więc działa dobrze w tym celu; nie ma znaczenia, w jakiej kolejności są obiekty in, tylko że kolejność jest taka sama dla obu list. Jednak w Pythonie 3 porównywanie obiektów różnych typów jest w wielu przypadkach niedozwolone - na przykład nie możesz porównywać łańcuchów z liczbami całkowitymi - więc jeśli będziesz mieć obiekty różnych typów, najlepiej jawnie użyć identyfikatora obiektu).

Z drugiej strony, jeśli chcesz porównać obiekty na liście według wartości , najpierw musisz zdefiniować, co oznacza „wartość” dla obiektów. Wtedy będziesz potrzebował jakiegoś sposobu, aby podać go jako klucz (a dla Pythona 3 jako spójny typ). Jednym z potencjalnych sposobów działania w przypadku wielu dowolnych obiektów jest sortowanie według ich repr(). Oczywiście może to zmarnować dużo dodatkowego czasu i repr()ciągów budujących pamięć dla dużych list i tak dalej.

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

Jeśli wszystkie obiekty są twoimi własnymi typami, możesz __lt__()na nich zdefiniować, aby obiekt wiedział, jak porównywać się z innymi. Następnie możesz je po prostu posortować i nie martwić się o key=parametr. Oczywiście możesz także zdefiniować __hash__()i użyć Counter, co będzie szybsze.

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

assertCountEqual (pierwszy, drugi, msg = brak)

Przetestuj, że sekwencja najpierw zawiera te same elementy, co druga, niezależnie od ich kolejności. Jeśli tak nie jest, zostanie wygenerowany komunikat o błędzie zawierający różnice między sekwencjami.

Powielone elementy nie są ignorowane podczas porównywania pierwszego i drugiego. Sprawdza, czy każdy element ma taką samą liczbę w obu sekwencjach. Równoważne z: assertEqual (Counter (lista (pierwsza)), Counter (lista (druga))), ale działa również z sekwencjami obiektów, których nie można zhashować.

Nowość w wersji 3.2.

lub w wersji 2.7: https://docs.python.org/2.7/library/unittest.html#unittest.TestCase.assertItemsEqual

Jeśli lista zawiera elementy, których nie można haszować (na przykład listę obiektów), możesz użyć klasy Counter i funkcji id (), takiej jak:

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

Mam nadzieję, że poniższy fragment kodu może działać w twoim przypadku: -

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

Zapewni to, że wszystkie elementy na obu listach aib są takie same, niezależnie od tego, czy są one w tej samej kolejności, czy nie.

Dla lepszego zrozumienia zapoznaj się z moją odpowiedzią na to pytanie

Jeśli porównanie ma być przeprowadzone w kontekście testowym, użyj assertCountEqual(a, b)( py>=3.2) i assertItemsEqual(a, b)(2.7<=py<3.2 ).

Działa również na sekwencjach obiektów, których nie można zhashować.

Niech a, b wymienia

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

Nie ma potrzeby ich haszowania ani sortowania.

Korzystanie z unittestmodułu zapewnia przejrzyste i standardowe podejście.

import unittest

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