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?

c# arrays linq sorting data-structures Matthieu Durut
źródło

Odpowiedzi:

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