Algorithmus zum Testen der Ungleichheit von geordneten großen Sammlungen

Question

Ok, ich muss testen, ob zwei IEnumerable<T> gleich sind. Die Reihenfolge der Elemente ist wichtig, was bedeutet, dass:

{1, 2, 4, 1, 3} and {1, 2, 1, 3, 4} should not be equal. 

Ich habe auf dieser Seite ein paar Antworten gesehen zu erklären, wie dies mit linq zu tun: zum Beispiel here

Das Problem ist, dass ich immer wieder auf Gleichheit von ziemlich großen Sammlungen (Tausende von Elementen) testen muss, die eine hohe Wahrscheinlichkeit haben, nicht gleich zu sein, so dass die Leistung ein Faktor ist, an den man denken muss. So wie ich es sehe, müssen alle linq Methoden, die in der erwähnten Antwort gezeigt werden (Count oder Except), wenn ich nicht irre, die gesamte Sammlung durchlaufen, was im allgemeinen Fall nicht notwendig ist.

Ich kam mit diesem Code, der ziemlich gut funktioniert (denke ich) und schnell genug ist. Ich habe mich gefragt, ob ich in Art und Weise einige offensichtlich gebaut bin fehlt, dies zu tun (ich will nicht das Rad hier, wenn möglich neu zu erfinden.)

public static bool IsEqualTo<T>(this IEnumerable<T> inner, IEnumerable<T> other) where T: IEquatable<T> 
{ 
    if (inner == null) 
     throw new ArgumentNullException(); 

    if (object.ReferenceEquals(inner, other)) 
     return true; 

    if (object.ReferenceEquals(other, null)) 
     return false; 

    using (var innerEnumerator = inner.GetEnumerator()) 
    using (var otherEnumerator = other.GetEnumerator()) 
    { 
     while (innerEnumerator.MoveNext()) 
     { 
      if (!otherEnumerator.MoveNext() || !innerEnumerator.Current.Equals(otherEnumerator.Current)) 
       return false; 
     } 

     return !otherEnumerator.MoveNext(); 
    } 
} 

Answer 1

Grundsätzlich Sie suchen kurzzuschließen die Auswertung, wenn ein Element wurde nicht gefunden.

IEnumerable.SequenceEqual (MSDN) bereits tut dies; erwies sich aus durch die Umsetzung in: http://referencesource.microsoft.com/#System.Core/System/Linq/Enumerable.cs (Linie 806)

Wenn Auftrag wichtig ist, sollten Sie in der Lage sein, eine einfach zu schreiben, während Schleife:

int i = 0; 
int aCount = a.Count(); //Use `IList` so you can use the property for efficiency 
int bCount = b.Count(); //Use `IList` so you can use the property for efficiency 

if (aCount != bCount) 
    return false; 

while (a.ElementAt(i) == b.ElementAt(i)) 
    i++; 

return i == aCount; 

Ihre Funktion ist die gleiche Sache ist im Grunde, und die Arbeit würde fein.

Answer 2

Wenn Sie häufig Sequenzen vergleichen wollen, würde ich vorschlagen, dass Sie einen Typ definieren sollten, die eine unveränderliche Folge kapselt und implementiert ICollection zusammen mit entweder IList<T> oder ICollection<T> (Sie zwei Arten definieren könnte, von denen eine IList<T> wickelt und implementiert ICollection und IList<T> und eine davon wickelt IEnumerable<T> und implementiert ICollection und ICollection<T>). Dieser Typ sollte Equals() und GetHashCode() überschreiben und sollte Felder für eine zwischengespeicherte Zählung zusammen mit ein Paar Int64 Felder und ein Int32 Feld für Hash-Codes und möglicherweise auch ein Int64 Sequenznummer Feld haben.

Wenn der Clientcode GetHashCode aufruft oder wenn die Anzahl der Elemente in der umschlossenen Sammlung festgelegt werden soll, muss der Code durch die Auflistung auflisten, die Hashwerte für jedes Element berechnen und diese 64 verwenden -Bit Hash-Werte für die Sammlung als Ganzes, und schließlich verdauen diese in einen 32-Bit-Wert für die Verwendung von GetHashCode geeignet. Auch wenn GetHashCode() nur einen einzelnen 32-Bit-Wert erfordert, würde ich aus den unten beschriebenen Gründen vorschlagen, mehr zu berechnen und zu speichern.

Wenn Sie einen Gleichheitstest durchführen, prüfen Sie zunächst, ob beide Objekte dieselbe Sammlung umfassen. Wenn ja, sind sie gleich. Andernfalls prüfen Sie, ob die Sammlungen die gleiche Anzahl von Elementen enthalten und ob die gesamten Hash-Codes übereinstimmen. Wenn keine der beiden Bedingungen zutrifft, sind sie nicht gleich. Ansonsten überprüfen Sie einzelne Elemente gegeneinander.Beachten Sie, dass, wenn Hash-Codes noch nicht berechnet wurden, es sich lohnt oder nicht, diese zu berechnen (und zu prüfen), bevor Sie einen Gleichheitstest durchführen; Ein Benchmarking kann zeigen, ob es hilfreich oder schädlich ist. Wenn eine Sammlung schließlich gehackt wird, ist es besser früher als später. Auf der anderen Seite, wenn Gleichheitsprüfungen bei einer Millionen-Objekt-Sammlung konsistent "nicht gleich" nach dem bloßen Betrachten des ersten Elements berichten würde und nichts anderes jemals den Hash-Wert benötigt, wäre es eine Verschwendung, sie zu berechnen.

Wenn zwei Objekte gleich sind, kann es sinnvoll sein, die umschlossene Sammlung des neueren Objekts durch die im älteren Objekt eingewickelte Sammlung zu ersetzen und die Sequenznummer des neueren Objekts mit der des älteren Objekts abzugleichen. Dadurch erhöht sich die Wahrscheinlichkeit, dass die Wrapper, wenn sie erneut verglichen werden, als gleich erkannt werden, ohne dass irgendwelche Elemente überprüft werden müssen. Beachten Sie, dass es verschiedene andere Techniken gibt, die verwendet werden können, um zukünftige Gleichheitsprüfungen zu erleichtern, die verschiedene Speicher-Trade-Offs beinhalten; Leider hat der Ansatz, der das beste typische Verhalten hat, ein sehr schlechtes Worst-Case-Verhalten. Beachten Sie außerdem, dass ein Wrapper, der Hashwerte zwischenspeichert, fehlschlägt, wenn die umgebrochenen Auflistungen extern geändert werden. Das Aufspüren der Ursachen solcher Fehler kann jedoch schwierig sein, wenn die oben genannten Referenzsubstitutionen vorgenommen werden.

Wenn viele ungleiche Sammlungen verglichen werden, kann das frühzeitige Beenden mithilfe von Hashcodes ein wichtiger Leistungsgewinn sein. Bei der Berechnung von Hash-Codes würde ich vorschlagen, dass Sie ein paar "unabhängige" Methoden zum Berechnen von 64-Bit-Hash-Codes verwenden. Der Grund dafür ist, dass abhängig davon, wie die Hash-Codes einzelner Elemente berechnet werden, die Wahrscheinlichkeit einer systemischen Hash-Kollision bei Verwendung einer einzelnen Hash-Methode unakzeptabel groß sein kann. Die Kosten für die Berechnung Ihrer eigenen Hash-Werte sind im Vergleich zu den Kosten für die Ermittlung der Hash-Werte Ihrer Bestandteile gering. Daher ist die Berechnung von zwei oder drei unabhängigen Hash-Funktionen eine kostengünstige Möglichkeit, systemischen Hash-Kollisionen vorzubeugen.