Algorytm testowania nierówności zamówionych dużych kolekcji

Question

Ok, muszę sprawdzić, czy dwa IEnumerable<T> są równe. Kolejność elementów jest ważne, co oznacza, że:

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

Widziałem kilka odpowiedzi na tej stronie wyjaśniające w jaki sposób to zrobić z linq na przykład: here

Problemem jest to, że muszę wielokrotnie testować pod kątem równości całkiem dużych kolekcji (tysięcy elementów), które mają duże prawdopodobieństwo, że nie będą równe, więc wydajność jest czynnikiem, o którym trzeba pamiętać. Sposób, w jaki go widzę, wszystkie metody przedstawione w odpowiedzi (Count lub Except) muszą, jeśli się nie mylę, iterować przez cały zbiór, który w ogólnym przypadku nie jest konieczny.

Wpadłem na ten kod, który działa dość dobrze (jak sądzę) i jest wystarczająco szybki. Zastanawiałem się, czy jestem brakuje niektórych oczywiste, zbudowany w zasadzie robi to (nie chcę wyważać otwartych drzwi tutaj, jeśli to możliwe.)

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

Zasadniczo szukasz zwarcia ocenę kiedy element nie został znaleziony.

IEnumerable.SequenceEqual (MSDN) już to robi; okazało się, poprzez wdrożenie w:

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; 

Twoja funkcja ma w zasadzie to samo, i będzie działać:

Gdy kolejność jest istotna, należy być w stanie napisać prosty pętli while http://referencesource.microsoft.com/#System.Core/System/Linq/Enumerable.cs (linia 806) w porządku.

Answer 2

Jeśli będziesz chciał często porównują sekwencje, chciałbym zaproponować, że należy określić rodzaj, który hermetyzuje niezmienną sekwencję i implementuje ICollection wraz z albo IList<T> lub ICollection<T> (można zdefiniować dwa rodzaje, z których jedna owija się IList<T> i implementuje ICollection i IList<T> i jedną z nich owija IEnumerable<T> i implementuje ICollection i ICollection<T>). Ten typ powinien zastąpić Equals() i GetHashCode() i powinien zawierać pola dla pamięci podręcznej wraz z kilkoma polami Int64 i polem Int32 dla ogólnych kodów skrótu, a także być może z polem numeru sekwencji Int64.

Jeśli kod klienta wywoła GetHashCode lub jeśli określenie liczby elementów w opakowanej kolekcji wymagałoby wyliczenia pozycji, kod powinien wyliczyć w kolekcji, obliczyć wartości skrótu dla każdego elementu i użyć tych obliczeń na poziomie 64 -bitowe wartości mieszania dla kolekcji jako całości i ostatecznie przetraw ich wartości 32-bitowe odpowiednie do użycia przez GetHashCode. Mimo że GetHashCode() wymaga tylko jednej 32-bitowej wartości, sugerowałbym obliczanie i przechowywanie więcej niż z powodów opisanych poniżej.

Podczas wykonywania testu równości należy rozpocząć od sprawdzenia, czy oba obiekty zawijają tę samą kolekcję. Jeśli tak, są równi. W przeciwnym razie sprawdź, czy zbiory zawierają taką samą liczbę elementów i czy ogólne kody skrótu są zgodne. Jeśli żaden z warunków nie ma zastosowania, nie są równe. W przeciwnym razie sprawdź poszczególne elementy względem siebie.Zauważ, że jeśli kody skrótu nie zostały jeszcze obliczone, może warto lub nie warto je obliczyć (i sprawdzić) przed wykonaniem testu równości; niektóre testy porównawcze mogą ujawnić, czy są one pomocne lub szkodliwe. Jeśli kolekcja zostanie ostatecznie zahartowana, lepiej zrobić ją wcześniej niż później. Z drugiej strony, jeśli kontrole równości w kolekcji zawierającej miliony pozycji będą konsekwentnie zgłaszać "nie równe" po prostu patrząc na pierwszy element i nic więcej nie będzie wymagało wartości mieszania, obliczanie go byłoby marnotrawstwem.

Jeśli dwa obiekty zostaną uznane za równe, może warto zastąpić kolekcję owiniętą nowszego obiektu kolekcją owiniętą w starszy obiekt i sprawić, aby numer kolejny nowszego obiektu był zgodny z numerem starszego obiektu. Takie postępowanie zwiększy prawdopodobieństwo, że jeśli opakowania zostaną ponownie porównane, można je uznać za równe bez konieczności sprawdzania jakichkolwiek przedmiotów. Zauważ, że istnieją różne inne techniki, które mogą pomóc w ułatwieniu przyszłych testów równości, które obejmują różne kompromisy w pamięci; niestety, podejście, które miałoby najlepsze zachowanie w typowym przypadku, ma bardzo złe zachowanie w najgorszym przypadku. Należy zauważyć, że chociaż dowolne opakowanie, które buforuje wartości hash, nie powiedzie się, jeśli opakowane kolekcje zostaną zmodyfikowane zewnętrznie, znalezienie przyczyn takich błędów może być trudne, jeśli dokonane zostaną wymienione podstawienia referencyjne.

Jeśli porówna się wiele nierównomiernych zbiorów, możliwość wczesnego wyjścia z wykorzystaniem kodów hash może być dużym osiągnięciem. W informatycznym haszowaniu sugerowałbym użycie kilku "niezależnych" metod obliczania 64-bitowych kodów skrótu. Powodem tego jest to, że w zależności od tego, w jaki sposób są obliczane kody skrótu poszczególnych elementów, prawdopodobieństwo systemowej kolizji mieszania przy użyciu pojedynczej metody hash może być niedopuszczalnie duże. Koszt obliczania własnych wartości mieszania jest niewielki w porównaniu z kosztem uzyskania wartości mieszania twoich składników, więc obliczenie dwóch lub trzech niezależnych funkcji skrótu będzie tanim sposobem ochrony przed systemowymi konfliktami hash.