Utrzymanie porządku z LINQ

361

Używam LINQ do instrukcji Objects w uporządkowanej tablicy. Których operacji nie należy wykonywać, aby mieć pewność, że kolejność tablicy nie ulegnie zmianie?

— Matthieu Durut
źródło

645

Zbadałem metody System.Linq.Enumerable , odrzucając wszystkie, które zwróciły wyniki niepoliczalne dla IE . Sprawdziłem uwagi każdego z nich, aby ustalić, w jaki sposób kolejność wyniku różni się od kolejności źródła.

Całkowicie zachowuje porządek. Możesz zamapować element źródłowy według indeksu na element wynikowy

AsEnumerable
Odlew
Concat
Wybierz
ToArray
Notować

Zachowuje porządek. Elementy są filtrowane lub dodawane, ale nie są ponownie zamawiane.

Odrębny
Z wyjątkiem
Krzyżować
OfType
Prepend (nowość w .net 4.7.1)
Pominąć
SkipWhile
Brać
TakeWhile
Gdzie
Zip (nowy w .net 4)

Niszczy zamówienie - nie wiemy, w jakiej kolejności można oczekiwać.

ToDictionary
ToLookup

Wyraźnie redefiniuje kolejność - użyj ich, aby zmienić kolejność wyników

Zamów przez
OrderByDescending
Odwrócić
Więc przez
ThenByDescending

Przedefiniowuje porządek zgodnie z niektórymi zasadami.

GroupBy - Obiekty IGrouping są generowane w kolejności opartej na kolejności elementów w źródle, które wytworzyły pierwszy klucz każdego IGrouping. Elementy w grupie są uzyskiwane w kolejności, w jakiej występują w źródle.
GroupJoin - GroupJoin zachowuje porządek elementów zewnętrznych, a dla każdego elementu zewnętrznego kolejność pasujących elementów od wewnętrznych.
Połącz - zachowuje porządek elementów zewnętrznych, a dla każdego z tych elementów kolejność pasujących elementów wewnętrznych.
SelectMany - dla każdego elementu źródła wywoływany jest selektor i zwracana jest sekwencja wartości.
Zjednoczenie - Gdy obiekt zwrócony tą metodą jest wyliczany, Związek wylicza pierwszy i drugi w tej kolejności i zwraca każdy element, który nie został jeszcze uzyskany.

Edycja: W oparciu o tę implementację przeniosłem Distinct na Zachowanie kolejności .

    private static IEnumerable<TSource> DistinctIterator<TSource>
      (IEnumerable<TSource> source, IEqualityComparer<TSource> comparer)
    {
        Set<TSource> set = new Set<TSource>(comparer);
        foreach (TSource element in source)
            if (set.Add(element)) yield return element;
    }

— Amy B.
źródło

2

Właściwie myślę, że Distinct zachowuje pierwotną (pierwszą znalezioną) kolejność - więc {1,2,1,3,1,3,4,1,5} wynosiłby {1,2,3,4,5}

— Marc Gravell

10

msdn.microsoft.com/en-us/library/bb348436.aspx Metoda Distinct <(Of <(TSource>)>) (IEnumerable <(Of <(TSource>)>))) zwraca nieuporządkowaną sekwencję, która nie zawiera zduplikowanych wartości .

— Amy B,

12

Marc: to, co mówisz, może być prawdą, ale oparcie się na takim zachowaniu byłoby złym pomysłem.

— Amy B,

4

@Amy B tak, ale nie dotyczy Linq do Objects. W Linq do Sql odrębne () umieszcza odrębne słowo kluczowe w wygenerowanym sql, a porządkowanie od sql nie jest gwarantowane. Chciałbym zobaczyć implementację odrębnego linq dla obiektów, które nie zachowują porządku i są bardziej wydajne niż te, które zachowują porządek. Na przykład, możesz zużyć całe dane wejściowe i umieścić je w haszsecie, a następnie uzyskać wartości, wyliczając hashset (utratę kolejności), ale to gorzej. Więc tak, nie mam nic przeciwko temu, żeby od czasu do czasu wymykać dokumentację :)

— dn

4

Może dokumentacja (dla Distinctmetody) miała po prostu powiedzieć „nieposortowane”, a nie „w nieprzewidywalnej kolejności”. Powiedziałbym, że Distinctnależy do powyższej kategorii filtrowania, podobnie jak Where.

— Jeppe Stig Nielsen,

34

Czy faktycznie mówisz o SQL, czy o tablicach? Innymi słowy, czy używasz LINQ do SQL czy LINQ do Objects?

Operatorzy LINQ to Objects tak naprawdę nie zmieniają swojego oryginalnego źródła danych - budują sekwencje, które są skutecznie wspierane przez to źródło danych. Jedynymi operacjami, które zmieniają kolejność, są OrderBy / OrderByDescending / ThenBy / ThenByDescending - i nawet wtedy są stabilne dla równo uporządkowanych elementów. Oczywiście wiele operacji odfiltruje niektóre elementy, ale elementy, które zostaną zwrócone, będą w tej samej kolejności.

Jeśli przekonwertujesz na inną strukturę danych, np. Z ToLookup lub ToDictionary, nie sądzę, aby porządek został zachowany w tym momencie - ale i tak jest to nieco inne. (Wydaje mi się, że kolejność mapowania wartości na ten sam klucz jest zachowana dla wyszukiwania).

— Jon Skeet
źródło

dlatego, że OrderBy jest sortowaniem stabilnym, to: seq.OrderBy (_ => _.Key) ustawi elementy w dokładnie takiej samej kolejności, jak seq.GroupBy (_ => _.Key) .SelectMany (_ => _ ). Czy to jest poprawne?

— dmg

1

@dmg: Nie, nie będzie. Zaraz GroupBypo nim SelectManypodane zostaną wyniki pogrupowane według klucza, ale nie w rosnącej kolejności kluczy ... da to w kolejności, w której klucze wystąpiły pierwotnie.

— Jon Skeet

czy mówisz, że LINQ do SQL nie porządkuje preserver?

— symbiont

@symbiont: W wielu operacji SQL nie jest brak dobrze zdefiniowane, aby rozpocząć. Zasadniczo staram się składać tylko obietnice dotyczące rzeczy, które mogę zagwarantować - na przykład LINQ względem Objects.

— Jon Skeet,

@JonSkeet Jeśli użyję OrderBy, to gwarantuje, że obiekty „n” z tym samym kluczem zachowają swoją oryginalną sekwencję, z wyjątkiem tego, że wszystkie są razem. tj .: w list<x> {a b c d e f g}przypadku, gdy wszystkie c, d, e mają ten sam klucz, wynikowa sekwencja będzie zawierać c, d, e obok siebie ORAZ w kolejności c, d, e. Nie mogę znaleźć kategorycznej odpowiedzi opartej na stwardnieniu rozsianym.

— Paulustrious,

7

Jeśli pracujesz nad tablicą, wygląda na to, że używasz LINQ-to-Objects, a nie SQL; czy możesz potwierdzić? Większość operacji LINQ niczego nie porządkuje (dane wyjściowe będą w tej samej kolejności co dane wejściowe) - więc nie stosuj innego sortowania (OrderBy [Malejąco] / ThenBy [Malejąco]).

[edytuj: jak Jon uściślił; LINQ generalnie tworzy nową sekwencję, pozostawiając oryginalne dane w spokoju]

Zauważ, że wpychanie danych do Dictionary<,>(ToDictionary) będzie szyfrować dane, ponieważ słownik nie przestrzega żadnej szczególnej kolejności sortowania.

Ale najczęstsze rzeczy (Wybierz, Gdzie, Pomiń, Weź) powinny być w porządku.

— Marc Gravell
źródło

Jeśli się nie mylę, ToDictionary()po prostu nie składa żadnych obietnic dotyczących kolejności, ale w praktyce utrzymuje kolejność wprowadzania (dopóki czegoś z niej nie usuniesz). Nie mówię, żebym na tym polegał, ale „mieszanie się” wydaje się niedokładne.

— Timo,

4

Znalazłem świetną odpowiedź w podobnym pytaniu, które odwołuje się do oficjalnej dokumentacji. Cytując to:

Dla Enumerablemetod (LINQ do obiektów, których dotyczy List<T>), można polegać na zlecenie elementów zwróconych przez Select, Wherelub GroupBy. Nie dotyczy to rzeczy z natury nieuporządkowanych, takich jak ToDictionarylub Distinct.

Z dokumentacji Enumerable.GroupBy :

Te IGrouping<TKey, TElement>obiekty są uzyskane w kolejności na podstawie kolejności elementów w źródle, które produkowały pierwszy klucz każdego IGrouping<TKey, TElement>. Elementy w grupie są uzyskiwane w kolejności, w jakiej występują source.

Niekoniecznie dotyczy to IQueryablemetod rozszerzenia (inni dostawcy LINQ).

Źródło: Czy wyliczalne metody LINQ utrzymują względną kolejność elementów?

— Curtis Yallop
źródło

2

Każda „grupa według” lub „kolejność według” prawdopodobnie zmieni kolejność.

— leppie
źródło

0

Pytanie tutaj odnosi się konkretnie do LINQ-to-Objects.

Jeśli zamiast tego używasz LINQ-to-SQL, nie ma tam żadnego zamówienia, chyba że narzucisz taki z czymś takim jak:

mysqlresult.OrderBy(e=>e.SomeColumn)

Jeśli nie zrobisz tego z LINQ-to-SQL, kolejność wyników może się różnić między kolejnymi zapytaniami, nawet tych samych danych, co może powodować przejściowy błąd.

— Andrzej Pasztet
źródło