Wie effizient vergleichen zwei ungeordnete Listen (nicht Sätze) in Python?

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

a & b als gleich gelten, weil Sie genau die gleichen Elemente, nur in verschiedener Reihenfolge.

Die Sache ist die, meine aktuellen Listen bestehen aus Objekten (meine Klasse Instanzen), nicht zahlen.

Wie werden die Objekte verglichen werden?
was ist die erwartete Größe der real-Listen? Werden die Listen verglichen werden, die von vergleichbarer grösse oder sehr Verschieden? Erwarten Sie, dass die meisten Listen übereinstimmen oder nicht?
Man könnte prüfen len()s erste.

InformationsquelleAutor johndir | 2011-10-19

192

O(n): Die Counter() Methode am besten ist (wenn Ihre Objekte sind hashable):
```
def compare(s, t):
    return Counter(s) == Counter(t)
```
O(n log n): Die sortiert() Methode ist die nächste beste (wenn Ihre Objekte sind bestellbar):
```
def compare(s, t):
    return sorted(s) == sorted(t)
```
O(n * n): Wenn die Objekte sind weder hashable, noch bestellbar, die Sie verwenden können, Geschlechter:
```
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
```
Danke. Ich konvertiert jedes Objekt zu einem string dann auf den Zähler () - Methode.
was ist mit string
Hey @Raymond, ich habe vor kurzem festgestellt, diese Frage auf ein interview und ich sorted() zugegeben, nicht zu wissen, über Counter. Der interviewer insistierte, gab es eine weitere effiziente Methode und klar, zog ich eine leere. Nach umfangreichen Tests in python 3 mit der timeit Modul, sortiert konsequent aus kommt schneller auf Listen von ganzen zahlen. Auf Listen, 1k Elemente, etwa 1,5% langsamer und auf kurze Listen, 10 Stück mit 7,5% langsamer. Gedanken?
Für kurze Listen, big-O-Analyse ist in der Regel irrelevant, da die timings sind geprägt durch Konstante Faktoren. Für die längeren Listen, ich vermute, etwas ist falsch mit Ihrem benchmarking. Für 100 int-Werte mit 5 Wiederholungen jede, die ich bekomme: 127 usec für sortierte und 42 für Zähler (über 3x schneller). Bei 1000 int-Werten mit 5 Wiederholungen, Counter-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)'
Nein danke. Ich habe nicht viel Interesse an debugging-unechte timing-Skripte. Es gibt eine Menge Los hier (reines python vs C-code, timsort angewendet wird, um randomisierte Daten vs semi-geordnete Daten, verschiedene Implementierungs-details über Ausführungen, wie viele Duplikate in den Daten, etc.)

InformationsquelleAutor Raymond Hettinger
14

Können Sie eine Sortierreihenfolge für beide:
```
sorted(a) == sorted(b)
```
Einen zählen, Sortieren könnte auch effizienter sein, aber es erfordert, dass das Objekt von 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
```
Dies funktioniert nicht mit Objekten in der beabsichtigten Weise.
Die Zähler verwenden, hashing, aber die Objekte sind nicht unhashable per se. Sie müssen nur implementiert eine sinnvolle __hash__, aber dass kann unmöglich sein, für die Sammlungen.
Ja, funktioniert nicht mit alle Objekte könnten besser sein 😉
sortiert wird nicht funktionieren, für alles, zB komplexe zahlen sorted([0, 1j])
sortiert() auch nicht funktioniert, mit sets, wo die Vergleichs-Operatoren wurden außer Kraft gesetzt für die Teilmenge/Obermenge tests.

InformationsquelleAutor Mark Byers
11

Wenn Sie wissen, die Artikel sind immer hashable können Sie eine Counter() ist O(n)

Wenn Sie wissen, die Elemente immer sortiert, Sie können sorted() ist O(n log n)

Im Allgemeinen Fall können Sie nicht Vertrauen können, um zu Sortieren, oder hat die Elemente, so brauchen Sie einen fallback, wie diese, die leider O(n^2)
```
len(a)==len(b) and all(a.count(i)==b.count(i) for i in a)
```
InformationsquelleAutor John La Rooy
5

Der beste Weg, dies zu tun ist durch die Sortierung der Listen und vergleicht Sie. (Mit Counter funktioniert nicht mit Objekten, die nicht hashable.) Das ist einfach für Ganzzahlen:
```
sorted(a) == sorted(b)
```
Wird es ein wenig schwieriger mit beliebigen Objekten. Wenn Sie um den Objekt-Identität, d.h., ob die gleichen Objekte sind in beiden Listen verwenden, können Sie die id() Funktion als Sortierschlüssel.
```
sorted(a, key=id) == sorted(b, key==id)
```
(In Python 2.x, die Sie nicht wirklich benötigen die key= parameter, da Sie können vergleichen, ein beliebiges Objekt beliebiges Objekt. Die Reihenfolge ist beliebig, aber stabil, so dass es funktioniert gut für diesen Zweck, ist es egal, in welcher Reihenfolge die Objekte werden in, nur, dass die Reihenfolge ist die gleiche für beide Listen. In Python 3, obwohl, Vergleich von Objekten unterschiedlicher Typen ist nicht zulässig in vielen Fällen-zum Beispiel, Sie können nicht vergleichen Sie strings mit ganzen zahlen-also wenn Sie Objekte von verschiedenen Typen, am besten explizit die Objekt-ID.)

Wenn Sie wollen, vergleichen Sie die Objekte in der Liste durch Wert, auf der anderen Seite, müssen Sie zuerst zu definieren, was "Wert" bedeutet für die Objekte. Dann müssen Sie einige Weg zu geben, dass als Schlüssel (und für Python 3, als eine einheitliche Art). Eine Möglichkeit, die funktionieren würde, für eine Menge von beliebigen Objekten zu Sortieren durch Ihre repr(). Natürlich könnte verschwenden viel mehr Zeit und Speicher Gebäude repr() strings für große Listen und so weiter.
```
sorted(a, key=repr) == sorted(b, key==repr)
```
Wenn die Objekte alle Ihre eigenen Typen können Sie definieren __lt__() auf Sie, so dass das Objekt weiß, wie zu vergleichen, sich für andere. Dann können Sie einfach Sortieren und sich keine sorgen über die key= parameter. Natürlich könnte man auch definieren __hash__() und verwenden Counter, was schneller geht.

InformationsquelleAutor kindall
3

Wenn die Liste Positionen enthält, die nicht hashable (wie eine Liste von Objekten) Sie können möglicherweise verwenden Sie die Counter-Klasse und die id () - Funktion, wie z.B.:
```
from collections import Counter
...
if Counter(map(id,a)) == Counter(map(id,b)):
    print("Lists a and b contain the same objects")
```
InformationsquelleAutor Mars
2

Wenn der Vergleich durchgeführt werden, im Test-Kontext, Nutzung assertCountEqual(a, b) (py>=3.2) und assertItemsEqual(a, b) (2.7<=py<3.2).

Arbeitet auf Sequenzen von unhashable Objekte zu.

InformationsquelleAutor jarekwg
2

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

assertCountEqual(erste, zweite, msg=None)

Test, dass die Sequenz enthält die gleichen Elemente wie die zweite, unabhängig von der Reihenfolge. Wenn Sie nicht, eine Fehlermeldung die Auflistung der Unterschiede zwischen den Sequenzen generiert werden.

Doppelte Elemente werden nicht ignoriert beim Vergleich der ersten und zweiten. Es wird überprüft, ob jedes element hat die gleiche Anzahl in beiden Sequenzen. Äquivalent zu: assertEqual(Counter(list(first)), Zähler(list(second))), aber Sie funktioniert mit den Sequenzen der unhashable Objekte.

Neu in der version 3.2.

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

(Was hat das hinzufügen jarekwg Antwort?)

InformationsquelleAutor cleder
1

Seien a,b Listen
```
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
```
Nicht brauchen, um Ihnen hashable oder Sie zu Sortieren.

Ja, aber das ist O(n**2) wie mehrere andere Poster, die angegeben, so sollte nur verwendet werden, wenn die anderen Methoden nicht funktionieren. Es wird auch davon ausgegangen a unterstützt pop (ist änderbar) und index (eine Sequenz). Raymond übernimmt weder während gnibbler ist davon nur eine Folge.

InformationsquelleAutor Umur Kontacı
1

Ich hoffe, dass die unten Stück code, das funktioniert vielleicht in deinem Fall :-
```
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 beiden Listen a & b sind die gleichen, unabhängig davon, ob Sie in der gleichen Reihenfolge oder nicht.

Zum besseren Verständnis, siehe meine Antwort im diese Frage

InformationsquelleAutor Pabitra Pati

Schreibe einen Kommentar

Du musst angemeldet sein, um einen Kommentar abzugeben.