Czy metoda Distinct () zachowuje pierwotną kolejność sekwencji nienaruszoną?

Chcę usunąć duplikaty z listy, bez zmiany kolejności unikalnych elementów na liście.

Jon Skeet i inni zasugerowali użycie następujących elementów:

list = list.Distinct().ToList();

Odniesienie:

• Jak usunąć duplikaty z List <T>?
• Usuń duplikaty z List <T> w C #

Czy jest zagwarantowane, że kolejność unikalnych elementów będzie taka sama jak wcześniej? Jeśli tak, podaj referencję, która to potwierdza, ponieważ nie mogłem znaleźć niczego na ten temat w dokumentacji.

Nie jest to gwarantowane, ale jest to najbardziej oczywista implementacja. Byłoby trudno zaimplementować w sposób strumieniowy (tj. Zwracał wyniki tak szybko, jak to możliwe, po przeczytaniu jak najmniej) bez zwracania ich w kolejności.

Możesz przeczytać mój wpis na blogu dotyczący implementacji Distinct () w Edulinq .

Zwróć uwagę, że nawet gdyby było to gwarantowane dla LINQ to Objects (co osobiście uważam, że powinno być), nie miało to żadnego znaczenia dla innych dostawców LINQ, takich jak LINQ to SQL.

Poziom gwarancji zapewnianych w LINQ to Objects jest czasami trochę niespójny, IMO. Niektóre optymalizacje są udokumentowane, inne nie. Heck, część dokumentacji jest całkowicie błędna .

W .NET Framework 3.5 deasemblacja CIL implementacji Linq-to-Objects Distinct()pokazuje, że kolejność elementów jest zachowana - jednak nie jest to udokumentowane zachowanie.

Zrobiłem małe dochodzenie z Reflector. Po deasemblacji System.Core.dll, Version = 3.5.0.0 widać, że Distinct () jest metodą rozszerzającą, która wygląda następująco:

public static class Emunmerable
{
    public static IEnumerable<TSource> Distinct<TSource>(this IEnumerable<TSource> source)
    {
        if (source == null)
            throw new ArgumentNullException("source");

        return DistinctIterator<TSource>(source, null);
    }
}

Tak więc interesujący jest tutaj DistinctIterator, który implementuje IEnumerable i IEnumerator. Oto uproszczona (usunięta goto i lables) implementacja tego IEnumeratora:

private sealed class DistinctIterator<TSource> : IEnumerable<TSource>, IEnumerable, IEnumerator<TSource>, IEnumerator, IDisposable
{
    private bool _enumeratingStarted;
    private IEnumerator<TSource> _sourceListEnumerator;
    public IEnumerable<TSource> _source;
    private HashSet<TSource> _hashSet;    
    private TSource _current;

    private bool MoveNext()
    {
        if (!_enumeratingStarted)
        {
            _sourceListEnumerator = _source.GetEnumerator();
            _hashSet = new HashSet<TSource>();
            _enumeratingStarted = true;
        }

        while(_sourceListEnumerator.MoveNext())
        {
            TSource element = _sourceListEnumerator.Current;

             if (!_hashSet.Add(element))
                 continue;

             _current = element;
             return true;
        }

        return false;
    }

    void IEnumerator.Reset()
    {
        throw new NotSupportedException();
    }

    TSource IEnumerator<TSource>.Current
    {
        get { return _current; }
    }

    object IEnumerator.Current
    {        
        get { return _current; }
    }
}

Jak widać - wyliczanie przebiega w kolejności podanej przez źródło wyliczalne (lista, na którą dzwonimy Distinct). Hashsetsłuży tylko do określenia, czy już zwróciliśmy taki element, czy nie. Jeśli nie, zwracamy go, w przeciwnym razie - kontynuuj wyliczanie na źródle.

Jest więc zagwarantowane, że Distinct()zwróci elementy dokładnie w tej samej kolejności , jaką zapewnia kolekcja, do której zastosowano Distinct.

Zgodnie z dokumentacją sekwencja jest nieuporządkowana.

Tak , Enumerable.Distinct zachowuje porządek. Zakładając, że metoda jest leniwa „daje różne wartości, gdy tylko zostaną zauważone”, następuje to automatycznie. Pomyśl o tym.

The source .NET Reference potwierdza. Zwraca podciąg, pierwszy element w każdej klasie równoważności.

foreach (TSource element in source)
    if (set.Add(element)) yield return element;

Implementacja .NET Rdzeń jest podobny.

Frustrujące jest to, że dokumentacja Enumerable.Distinct jest niejasna w tym punkcie:

Sekwencja wyników jest nieuporządkowana.

Mogę sobie tylko wyobrazić, że oznaczają one „sekwencja wyników nie jest posortowana”. Państwo mogli wdrożyć W odróżnieniu od wstępnego sortowania następnie porównując każdy element do poprzedniego, ale nie byłoby to leniwy jak zdefiniowano powyżej.

Domyślnie, gdy używasz operatora Distinct linq, używa metody Equals, ale możesz użyć własnego IEqualityComparer<T>obiektu do określenia, kiedy dwa obiekty są równe za pomocą niestandardowej implementacji logiki GetHashCodei Equalsmetody. Zapamietaj to:

GetHashCodenie powinien używać ciężkich porównań procesorów (np. używać tylko niektórych oczywistych podstawowych testów) i jest używany jako pierwszy do stwierdzenia, czy dwa obiekty są na pewno różne (jeśli zwracany jest inny kod skrótu) lub potencjalnie ten sam (ten sam kod skrótu). W tym ostatnim przypadku, gdy dwa obiekty mają ten sam kod skrótu, framework wykona krok, aby sprawdzić za pomocą metody Equals jako ostateczną decyzję o równości danych obiektów.

Po tym, jak masz MyTypei MyTypeEqualityComparerklasy podążają za kodem, nie gwarantuje to, że sekwencja zachowa swoją kolejność:

var cmp = new MyTypeEqualityComparer();
var lst = new List<MyType>();
// add some to lst
var q = lst.Distinct(cmp);

W bibliotece follow sci zaimplementowałem metodę rozszerzającą, aby zapewnić, że zestaw Vector3D zachowuje kolejność podczas korzystania z określonej metody rozszerzenia DistinctKeepOrder:

odpowiedni kod jest następujący:

/// <summary>
/// support class for DistinctKeepOrder extension
/// </summary>
public class Vector3DWithOrder
{
    public int Order { get; private set; }
    public Vector3D Vector { get; private set; }
    public Vector3DWithOrder(Vector3D v, int order)
    {
        Vector = v;
        Order = order;
    }
}

public class Vector3DWithOrderEqualityComparer : IEqualityComparer<Vector3DWithOrder>
{
    Vector3DEqualityComparer cmp;

    public Vector3DWithOrderEqualityComparer(Vector3DEqualityComparer _cmp)
    {
        cmp = _cmp;
    }

    public bool Equals(Vector3DWithOrder x, Vector3DWithOrder y)
    {
        return cmp.Equals(x.Vector, y.Vector);
    }

    public int GetHashCode(Vector3DWithOrder obj)
    {
        return cmp.GetHashCode(obj.Vector);
    }
}

W skrócie Vector3DWithOrderhermetyzuje typ i liczbę całkowitą zamówienia, podczas gdy Vector3DWithOrderEqualityComparerhermetyzuje funkcję porównującą oryginalny typ.

i to jest pomocnik metody, aby zapewnić utrzymanie porządku

/// <summary>
/// retrieve distinct of given vector set ensuring to maintain given order
/// </summary>        
public static IEnumerable<Vector3D> DistinctKeepOrder(this IEnumerable<Vector3D> vectors, Vector3DEqualityComparer cmp)
{
    var ocmp = new Vector3DWithOrderEqualityComparer(cmp);

    return vectors
        .Select((w, i) => new Vector3DWithOrder(w, i))
        .Distinct(ocmp)
        .OrderBy(w => w.Order)
        .Select(w => w.Vector);
}

Uwaga : dalsze badania mogą pozwolić na znalezienie bardziej ogólnego (zastosowania interfejsów) i zoptymalizowanego sposobu (bez hermetyzacji obiektu).

To w dużej mierze zależy od twojego dostawcy linq. Na Linq2Objects możesz pozostać przy wewnętrznym kodzie źródłowym dla Distinct, co pozwala założyć, że oryginalna kolejność jest zachowana.

Jednak dla innych dostawców, którzy na przykład rozwiązują problem z jakimś rodzajem SQL, niekoniecznie tak jest, ponieważ ORDER BY-statement zwykle pojawia się po każdej agregacji (takiej jak Distinct). Więc jeśli twój kod jest taki:

myArray.OrderBy(x => anothercol).GroupBy(x => y.mycol);

jest to tłumaczone na coś podobnego do następującego w SQL:

SELECT * FROM mytable GROUP BY mycol ORDER BY anothercol;

To oczywiście najpierw grupuje dane, a następnie sortuje je. Teraz utkniesz na własnej logice DBMS, jak to wykonać. W niektórych DBMS jest to nawet niedozwolone. Wyobraź sobie następujące dane:

mycol anothercol
1     2
1     1
1     3
2     1
2     3

wykonując myArr.OrderBy(x => x.anothercol).GroupBy(x => x.mycol)zakładamy następujący wynik:

mycol anothercol
1     1
2     1

Ale DBMS może agregować kolumnę anothercol tak, że zawsze używana jest wartość z pierwszego wiersza, co daje w wyniku następujące dane:

mycol anothercol
1    2
2    1

co po złożeniu zamówienia spowoduje:

mycol anothercol
2    1
1    2

Jest to podobne do następującego:

SELECT mycol, First(anothercol) from mytable group by mycol order by anothercol;

co jest całkowicie odwrotną kolejnością niż oczekiwano.

Zobaczysz, że plan wykonania może się różnić w zależności od tego, jaki jest podstawowy dostawca. Dlatego nie ma takiej gwarancji w dokumentacji.