Ich habe zwei Listen A und B (Liste). Wie kann man feststellen, ob sie auf die billigste Weise gleich sind? Ich kann etwas wie '(A minus B) union (B minus A) = leerer Satz' schreiben oder sie zusammenfügen und die Anzahl der Elemente zählen, aber es ist ziemlich teuer. Gibt es eine Problemumgehung?
Nun, das hängt davon ab, wie Sie Ihre Listen interpretieren.
Wenn Sie sie als Tupel betrachten (also die Reihenfolge der Elemente in Listen zählt), dann können Sie mit diesem Code gehen:
%Vor%Wenn Sie Ihre Listen als Mengen betrachten (also ist die Reihenfolge der Elemente nicht wichtig), dann ... verwenden Sie die falschen Datenstrukturen, die ich vermute:
%Vor%Wenn die Reihenfolge der Listenelemente relevant ist:
%Vor%Wenn die Listen als ungeordnete Mengen behandelt werden sollen:
%Vor% (Die SequenceEqual -Methode und die < Ein href="http://msdn.microsoft.com/en-us/library/bb359438.aspx"> HashSet<T> -Konstruktor haben beide Überladungen, die ein IEqualityComparer<T> Parameter, wenn Sie diese Funktionalität benötigen.)
Es hängt davon ab, was Sie unter "die Liste sind gleich" verstehen. Wenn Sie meinen, dass sie dieselben Objekte enthalten, ist die von Daniel vorgeschlagene Lösung in Ordnung, nur Union () listet die beiden auf und zählt die Elemente.
Wenn Sie mit "gleich" meinen, dass sie die gleichen Elemente in derselben Reihenfolge haben, wäre es besser, die Anzahl der beiden Listen zu vergleichen, wenn sie die gleiche Anzahl haben Iterieren Sie mit einer einfachen for loop , um jedes Element aus beiden Listen mit demselben Index zu vergleichen. Weniger schön, aber Sie können kaum schneller sein.
Es gibt hier keine Abkürzung, es sei denn, die Listen sind sortiert. In diesem Fall können Sie die Elemente einzeln vergleichen. Und ich nehme natürlich an, dass diese Reihenfolge keine Rolle spielt, sonst ist es offensichtlich, dass man sie auch einzeln vergleichen kann.
Andernfalls würde ich vorschlagen, dass der effizienteste Algorithmus, den Sie für große Listen von Elementen erhalten könnten, wahrscheinlich in etwa so aussehen würde. Verwenden Sie eine Hashtabelle, um zu verfolgen, was Sie gesehen haben (Warnung: nicht getestet, aber es sollte klar sein, worauf ich hinaus will.)
%Vor%Eine erste Aufnahme - wenn sie die gleichen Elemente enthalten, sollte die Vereinigung beider Listen die gleiche Anzahl von Elementen haben wie jede der beiden Listen.
%Vor%Hinweis: Scheitert, wenn eine Liste leer ist.
Aber es ist wahrscheinlich immer noch eine Operation O(n²) .
Eine andere Lösung - die Listen müssen die gleiche Länge haben und die Liste A minus Liste B darf keine Elemente enthalten.
%Vor%