Wie kann man zwei ungeordnete Listen (keine Mengen) in Python effizient vergleichen?

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

a & b sollten als gleich angesehen werden, da sie genau die gleichen Elemente haben, nur in unterschiedlicher Reihenfolge.

Die Sache ist, meine tatsächlichen Listen bestehen aus Objekten (meinen Klasseninstanzen), nicht aus ganzen Zahlen.

Johndir
quelle
7
Wie werden die Objekte verglichen?
Marcelo Cantos
2
Was ist die erwartete Größe der realen Listen? Werden die verglichenen Listen von vergleichbarer Größe oder sehr unterschiedlich sein? Erwarten Sie, dass die meisten Listen übereinstimmen oder nicht?
Dmitry B.
Man könnte len()zuerst s überprüfen .
Graubart

Antworten:

245

O (n) : Die Counter () -Methode ist am besten (wenn Ihre Objekte hashbar sind):

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

O (n log n) : Die sortierte () Methode ist die nächstbeste (wenn Ihre Objekte bestellbar sind):

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

O (n * n) : Wenn die Objekte weder hashbar noch bestellbar sind, können Sie Gleichheit verwenden:

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
Raymond Hettinger
quelle
1
Danke dir. Ich habe jedes Objekt in eine Zeichenfolge konvertiert und dann die Counter () -Methode verwendet.
Johndir
Hey @Raymond, ich bin kürzlich auf diese Frage in einem Interview gestoßen und habe sie verwendet sorted(), obwohl ich zugegebenermaßen nichts davon wusste Counter. Der Interviewer bestand darauf, dass es eine effizientere Methode gab, und ich zog eindeutig eine Lücke. Nach umfangreichen Tests in Python 3 mit dem timeitModul wird die Sortierung in Listen mit Ganzzahlen konsistent schneller ausgeführt. Auf Listen mit 1k Artikeln, ca. 1,5% langsamer und auf Kurzlisten mit 10 Artikeln, 7,5% langsamer. Gedanken?
Arctelix
4
Bei kurzen Listen ist die Big-O-Analyse normalerweise irrelevant, da die Timings von konstanten Faktoren dominiert werden. Bei den längeren Listen vermute ich, dass etwas mit Ihrem Benchmarking nicht stimmt. Für 100 Zoll mit jeweils 5 Wiederholungen bekomme ich: 127 usec für sortiert und 42 für Counter (ca. 3x schneller). Bei 1.000 Zoll mit 5 Wiederholungen ist der Zähler 4x schneller. python3.6 -m timeit -s 'from collections import Counter' -s 'from random import shuffle' -s 't=list(range(100)) * 5' -s 'shuffle(t)' -s 'u=t[:]' -s 'shuffle(u)' 'Counter(t)==Counter(u)'
Raymond Hettinger
@ Raymond In der Tat bekommen wir unterschiedliche Ergebnisse. Ich habe mein Setup in einem Chatroom gepostet sorted vs counter. Ich bin sehr gespannt, was hier los ist.
Arctelix
4
Nein Danke. Ich habe nicht viel Interesse daran, falsche Timing-Skripte zu debuggen. Hier ist viel los (reiner Python gegen C-Code, Timsort wird auf randomisierte Daten gegen halbgeordnete Daten angewendet, unterschiedliche Implementierungsdetails je nach Version, wie viele Duplikate in den Daten enthalten sind usw.)
Raymond Hettinger
16

Sie können beide sortieren:

sorted(a) == sorted(b)

EIN Zählung Art könnte auch effizienter sein (aber es erfordert das Objekt hashable sein).

>>> from collections import Counter
>>> a = [1, 2, 3, 1, 2, 3]
>>> b = [3, 2, 1, 3, 2, 1]
>>> print (Counter(a) == Counter(b))
True
Mark Byers
quelle
Der Zähler verwendet zwar Hashing, aber Objekte sind an sich nicht nicht verwischbar. Sie müssen nur ein vernünftiges implementieren __hash__, aber das könnte für Sammlungen unmöglich sein.
Jochen Ritzel
2
sortiert funktioniert auch nicht für alles, zB komplexe Zahlensorted([0, 1j])
John La Rooy
1
sortiert () funktioniert auch nicht mit Mengen, bei denen die Vergleichsoperatoren für Teilmengen- / Obermengen-Tests überschrieben wurden.
Raymond Hettinger
12

Wenn Sie wissen, dass die Elemente immer hashbar sind, können Sie a verwenden, Counter()das O (n) ist.
Wenn Sie wissen, dass die Elemente immer sortierbar sind, können Sie verwendensorted() O (n log n) verwenden.

Im allgemeinen Fall können Sie sich nicht darauf verlassen, dass Sie sortieren können oder über die Elemente verfügen. Daher benötigen Sie einen solchen Fallback, der leider O (n ^ 2) ist.

len(a)==len(b) and all(a.count(i)==b.count(i) for i in a)
John La Rooy
quelle
5

Der beste Weg, dies zu tun, besteht darin, die Listen zu sortieren und zu vergleichen. (Die Verwendung Counterfunktioniert nicht mit Objekten, die nicht hashbar sind.) Dies ist für Ganzzahlen unkompliziert:

sorted(a) == sorted(b)

Bei beliebigen Objekten wird es etwas kniffliger. Wenn Sie sich für die Objektidentität interessieren, dh ob sich in beiden Listen dieselben Objekte befinden, können Sie die id()Funktion als Sortierschlüssel verwenden.

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

(In Python 2.x benötigen Sie das eigentlich nicht key= Parameter , da Sie jedes Objekt mit jedem Objekt vergleichen können. Die Reihenfolge ist willkürlich, aber stabil, daher funktioniert es für diesen Zweck einwandfrei. Es spielt keine Rolle, in welcher Reihenfolge die Objekte sind nur, dass die Reihenfolge für beide Listen gleich ist. In Python 3 ist das Vergleichen von Objekten unterschiedlichen Typs jedoch unter vielen Umständen nicht zulässig. Beispielsweise können Sie Zeichenfolgen nicht mit Ganzzahlen vergleichen. Wenn Sie also Objekte haben von verschiedenen Typen, am besten explizit die ID des Objekts verwenden.)

Wenn Sie die Objekte in der Liste nach Wert vergleichen möchten, müssen Sie zunächst definieren, was "Wert" für die Objekte bedeutet. Dann benötigen Sie eine Möglichkeit, dies als Schlüssel bereitzustellen (und für Python 3 als konsistenten Typ). Ein möglicher Weg, der für viele beliebige Objekte funktionieren würde, besteht darin, nach ihren zu sortieren repr(). Dies könnte natürlich viel zusätzliche Zeit und Speicheraufbau repr()für große Listen usw. verschwenden .

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

Wenn die Objekte alle Ihre eigenen Typen sind, können Sie sie definieren __lt__(), damit das Objekt weiß, wie es sich mit anderen vergleicht. Dann können Sie sie einfach sortieren und sich nicht um den key=Parameter kümmern . Natürlich können Sie auch definieren __hash__()und verwenden Counter, was schneller sein wird.

irgendwie
quelle
4

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

assertCountEqual (erste, zweite, msg = Keine)

Testen Sie, ob diese Sequenz zuerst dieselben Elemente wie die zweite enthält, unabhängig von ihrer Reihenfolge. Wenn dies nicht der Fall ist, wird eine Fehlermeldung generiert, in der die Unterschiede zwischen den Sequenzen aufgeführt sind.

Doppelte Elemente werden beim Vergleich von erstem und zweitem nicht ignoriert. Es wird überprüft, ob jedes Element in beiden Sequenzen die gleiche Anzahl hat. Entspricht: assertEqual (Zähler (Liste (erste)), Zähler (Liste (zweite))), funktioniert jedoch auch mit Sequenzen nicht zerlegbarer Objekte.

Neu in Version 3.2.

oder in 2.7: https://docs.python.org/2.7/library/unittest.html#unittest.TestCase.assertItemsEqual

Cleder
quelle
2
(Was fügt dies zu Jarekwgs Antwort hinzu ?)
Greybeard
3

Wenn die Liste Elemente enthält , die nicht hashable sind (wie zum Beispiel einer Liste von Objekten) Sie könnten in der Lage sein , die verwenden Zähler Klasse und die Funktion id () wie zum Beispiel:

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

Ich hoffe, dass der folgende Code in Ihrem Fall funktioniert: -

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

Dadurch wird sichergestellt, dass alle Elemente in den Listen a&b sind, unabhängig davon, ob sie in derselben Reihenfolge vorliegen oder nicht.

Zum besseren Verständnis beziehen Sie sich auf meine Antwort in dieser Frage

Pabitra Pati
quelle
2

Wenn der Vergleich in einem Testkontext durchgeführt werden soll, verwenden Sie assertCountEqual(a, b)( py>=3.2) und assertItemsEqual(a, b)( 2.7<=py<3.2).

Funktioniert auch mit Sequenzen von nicht zerlegbaren Objekten.

jarekwg
quelle
1

Lassen Sie a, b auflisten

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

Sie müssen sie nicht hashbar machen oder sortieren.

Umur Kontacı
quelle
1
Ja, aber dies ist O (n ** 2), wie in mehreren anderen Postern angegeben. Es sollte daher nur verwendet werden, wenn die anderen Methoden nicht funktionieren. Es wird auch davon ausgegangen, dass es aunterstützt pop(veränderlich ist) und index(eine Sequenz ist). Raymond's nimmt beides nicht an, während Gnibbler's nur eine Sequenz annimmt.
Agf
0

Die Verwendung des unittestModuls bietet Ihnen einen sauberen und standardmäßigen Ansatz.

import unittest

test_object = unittest.TestCase()
test_object.assertCountEqual(a, b)
Meysam Sadeghi
quelle