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

84

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:

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.

c#  list  duplicates 
— Nitesh
źródło
5
@ColonelPanic - oficjalna dokumentacja tutaj msdn.microsoft.com/en-us/library/bb348436(v=vs.110).aspx stwierdza wyraźnie „Metoda Distinct () zwraca nieuporządkowaną sekwencję, która nie zawiera zduplikowanych wartości”.
— Evk
@Evk „Nieuporządkowana sekwencja” to nie to samo, co „oryginalna kolejność sekwencji”.
— Nitesh
3
Uważam, że „unoreered” oznacza „w żadnym konkretnym porządku”, co oznacza również „niekonieczne w pierwotnej kolejności”.
— Evk
Właśnie miałem problem z określeniem odrębności w Oracle12 Entity Framework 6. W moim przypadku miałem orderby before disinct w mojej klauzuli linq i zamówienie zniknęło. select (). OrderBy (). Distinct (). ToList () nie działało podczas zaznaczania (). OrderBy (). Distinct (). ToList () działało.
— Karl,
2
@Karl, te wyrażenia są takie same. :)
— pvgoran

Odpowiedzi:

77

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 .

— Jon Skeet
źródło
Akceptuję to, ponieważ 1) Wyraźnie odpowiada na moje obawy, czy jest to gwarantowane, czy nie 2) Powiązany post zagłębia się w nieudokumentowane aspekty Odrębności 3) Powiązany post ma również przykładową implementację, której można użyć jako odniesienia do implementacji Odrębnego na Listy z tą gwarancją.
— Nitesh
25

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.

— Sergey Berezovskiy
źródło
8
Czy jest to dobrze udokumentowane zachowanie?
— abatishchev
4
Połączona odpowiedź zawiera odniesienie do dokumentacji, które mówi: „Sekwencja wyników jest nieuporządkowana”.
— mgronber
5
@lazyberezovsky: Pytanie dotyczy gwarancji , a nie powszechnej implementacji . (Jak już powiedziałem, byłbym zaskoczony, gdyby implementacja kiedykolwiek zmieniła się na różnych platformach / wersjach, ale to nie daje gwarancji.)
— LukeH
5
@lazyberezovsky: Pochodzę z C \ C ++, gdzie wiele rzeczy jest nieokreślonych i bardzo często pyta się, czy coś jest gwarantowane. Używam także Distinct () w aplikacji Silverlight, która jest zarówno na Macu, jak i Windowsie, dlatego nie możemy zdecydować się na „powszechną implementację”, to musi być zagwarantowane.
— Nitesh
43
@lazyberezovsky: Kiedy ludzie mówią o gwarancjach, zwykle mają na myśli udokumentowane zachowanie, na którym można polegać. Na przykład, docs dla GroupBy należy określić zachowanie, ale docs dla Wyraźny nie robić .
— Jon Skeet,
14

Zgodnie z dokumentacją sekwencja jest nieuporządkowana.

— mgronber
źródło
3
Dodatkowe informacje, aby go znaleźć: w linku należy zapoznać się z sekcją „Uwagi”. „Sekwencja wyników jest nieuporządkowana”.
— Curtis Yallop
6

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.

— Colonel Panic
źródło
7
Źródłem nie jest specyfikacja. To, co znalazłeś, jest zbiegiem okoliczności i może być nieważne po następnej aktualizacji.
— Henk Holterman
@HenkHolterman Generalnie zgadzam się, implementacje mogą się zmienić. Na przykład .NET 4.5 zmienił algorytm sortowania za Array.Sort. Jednak w tym konkretnym przypadku jakakolwiek rozsądna implementacja Enumerable.Distinct z pewnością będzie leniwa („daje różne wartości, gdy tylko zostaną zauważone”) i wynika z tego właściwość zachowania porządku. Leniwa ocena to podstawowa zasada LINQ to Objects; unieważnienie tego byłoby nie do pomyślenia.
— Colonel Panic
1
Widziałem implementacje korzystające z .net 4.6, w których wywołanie dbQuery.OrderBy(...).Distinct().ToList()nie zwraca listy w kolejności określonej przez kolejność przez predykat - usunięcie Distinct (który okazał się zbędny) naprawiło błąd w moim przypadku
— Rowland Shaw
1

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).

— Lorenzo Delana
źródło
1

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.

— HimBromBeere
źródło
Korzystając z naszej strony potwierdzasz, że przeczytałeś(-aś) i rozumiesz nasze zasady używania plików cookie i zasady ochrony prywatności.
Licensed under cc by-sa 3.0 with attribution required.