Wie kann man ungeordnete Objektlisten effizient vergleichen?

Effizienter Vergleich ungeordneter Listen

Der Vergleich ungeordneter Listen, auch als Taschen bezeichnet, kann eine anspruchsvolle Aufgabe sein, insbesondere wenn mit Objekten statt mit einfachen Datentypen wie Ganzzahlen gearbeitet wird . Hier sind drei effiziente Ansätze, um dieses Problem anzugehen:

1. Counter-Methode (O(n))

Für Objekte, die hashbar sind (d. h. in einen eindeutigen Hash-Wert konvertiert werden können), kann die Counter()-Methode aus dem Collections-Modul von Python verwendet werden. Es erstellt ein wörterbuchähnliches Objekt, bei dem Schlüssel die Elemente der Liste und Werte ihre jeweilige Anzahl sind. Der Vergleich zweier Listen mit diesem Ansatz hat eine lineare Zeitkomplexität von O(n), wobei n die Länge der Listen ist.

import collections

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

2. Sortierte Methode (O(n log n))

Wenn die Objekte in der Liste vergleichbar sind (d. h. sie haben eine definierte Reihenfolge), kann das Sortieren der Listen einen effizienten Vergleichsmechanismus bieten. Die Methode sorted() in Python sortiert die Elemente in der Liste, sodass Sie leicht feststellen können, ob die beiden Listen dieselben Elemente in beliebiger Reihenfolge enthalten. Dieser Ansatz hat eine zeitliche Komplexität von O(n log n), wobei n die Länge der Listen ist.

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

3. Gleichheitsvergleich (O(n * n))

Wenn die Objekte weder hashbar noch sortierbar sind, besteht ein einfacher Ansatz darin, Gleichheitsvergleiche zwischen den Elementen der beiden Listen durchzuführen. Für jedes Element in der ersten Liste entfernen wir es aus der zweiten Liste. Wenn ein Element der ersten Liste in der zweiten Liste nicht gefunden wird, schlägt der Vergleich fehl. Dieser Ansatz weist im ungünstigsten Fall eine Zeitkomplexität von O(n * n) auf, wobei n die Länge der Listen ist.

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

Durch die Verwendung dieser effizienten Vergleichstechniken können Sie ungeordnete Listen von Objekten effektiv vergleichen , ob sie hashbar, bestellbar oder keines von beidem sind.

Das obige ist der detaillierte Inhalt vonWie kann man ungeordnete Objektlisten effizient vergleichen?. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!