Preserving order with LINQ

312

141

I use LINQ to Objects instructions on an ordered array. Which operations shouldn't I do to be sure the order of the array is not changed?

Matthieu Durut

Posted 2008-10-15T12:20:13.293

Reputation: 2 145

Answers

557

I examined the methods of System.Linq.Enumerable, discarding any that returned non-IEnumerable results. I checked the remarks of each to determine how the order of the result would differ from order of the source.

Preserves Order Absolutely. You can map a source element by index to a result element

  • AsEnumerable
  • Cast
  • Concat
  • Select
  • ToArray
  • ToList

Preserves Order. Elements are filtered, but not re-ordered.

  • Distinct
  • Except
  • Intersect
  • OfType
  • Skip
  • SkipWhile
  • Take
  • TakeWhile
  • Where
  • Zip (new in .net 4)

Destroys Order - we don't know what order to expect results in.

  • ToDictionary
  • ToLookup

Redefines Order Explicitly - use these to change the order of the result

  • OrderBy
  • OrderByDescending
  • Reverse
  • ThenBy
  • ThenByDescending

Redefines Order according to some rules.

  • GroupBy - The IGrouping objects are yielded in an order based on the order of the elements in source that produced the first key of each IGrouping. Elements in a grouping are yielded in the order they appear in source.
  • GroupJoin - GroupJoin preserves the order of the elements of outer, and for each element of outer, the order of the matching elements from inner.
  • Join - preserves the order of the elements of outer, and for each of these elements, the order of the matching elements of inner.
  • SelectMany - for each element of source, selector is invoked and a sequence of values is returned.
  • Union - When the object returned by this method is enumerated, Union enumerates first and second in that order and yields each element that has not already been yielded.

Edit: I've moved Distinct to Preserving order based on this implementation.

    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

Posted 2008-10-15T12:20:13.293

Reputation: 86 683

4Maybe the documentation (for Distinct method) just meant to say "unsorted", not "in unpredictable order". I'd say Distinct belongs to the filtering category above, just like Where. – Jeppe Stig Nielsen – 2012-09-20T16:17:54.420

WWJSD: http://stackoverflow.com/a/4734876/62600

– Todd Menier – 2014-09-12T18:51:43.580

I'm not sure about select many, as there is no other constructions besides two foreaches. What side effect are you talking about? – Johnny_D – 2015-03-10T12:22:27.040

1@Johnny_D I've considered my use of the term "side effect", and decided to edit since it has a meaning in our field. Also, when I'm talking about "preserving order", I'm talking from the perspective of Order Isomorphism. Distinct and SelectMany are not order isomorphic. – Amy B – 2015-03-18T12:22:03.070

Aren't Except, Intersect Union etc set operations? I wouldnt trust them to return in order. Is it documented? – nawfal – 2015-06-29T19:37:46.270

1

@nawfal Intersect ( https://msdn.microsoft.com/en-us/library/vstudio/bb460136(v=vs.100).aspx ): "Finally, the marked elements are yielded in the order in which they were collected." Except doesn't document this, but its implementation is likely to be very similar. Union ( https://msdn.microsoft.com/en-us/library/vstudio/bb341731(v=vs.100).aspx ) : quote is already in the answer. While these operations could be described as set operations, they operate on IEnumerable<T> and it makes sense for their implementations to have a documented order based on the order of the source IEnumerable.

– Amy B – 2015-06-29T23:33:48.807

@nawfal also note: this question and answer are about LinqToObjects (the methods of System.Linq.Enumerable). If you are using Linq to anything else (System.Linq.Queryable) - none of this applies. – Amy B – 2015-06-29T23:38:03.990

@DavidB For ILookup: The IGrouping<TKey, TElement> objects are yielded in an order based on the order of the elements in source that produced the first key of each IGrouping<TKey, TElement>. Elements in a grouping are yielded in the order they appear in source., taken from the GroupBy documentation. Since ILookup has IGroupings, it's guaranteed to preserve order, right? – mbomb007 – 2015-07-08T16:51:57.030

https://github.com/dotnet/corefx/blob/master/src/System.Linq.Parallel/src/System/Linq/Parallel/Utils/Lookup.cs

ToLookup returns a Lookup. As you can see in the code, Lookup wraps a Dictionary. Because of this, Lookup has the same inconsistent ordering as Dictionary.

– Amy B – 2015-11-17T16:28:37.427

Lookup indeed wraps a dictionary but a special one: it maintains links between the elements to preserve the ordering of group keys, because it has to fulfil the documented ordering of GroupBy. Lookup is the underlying data structure of both GroupBy and ToLookup. Therefore ToLookup preserves ordering just as well as Distinct does: neither is documented, both works (for ≥ 6 years now). – robert4 – 2015-11-19T11:24:37.810

But Lookup is backed by a plain Dictionary: _dict = new Dictionary<TKey, IGrouping<TKey, TElement>>(_comparer); Does this mean that Dictionary preserves order? – Amy B – 2015-11-19T15:39:19.970

@David B The plain Dictionary preserves ordering (albeit undocumented) as long as no elements are removed, but it is not used in Lookup. Its internal GetGrouping() method contains a hash table implementation, with the aforementioned .next pointers, to be used in GetEnumerator() (line 3288).

– robert4 – 2015-11-23T08:33:12.437

@robert4 it looks like ToLookup changes the keys order, but the elements preserve the order of the source enumerable. – HuBeZa – 2016-02-02T12:45:40.800

@HuBeZa can you show an example on dotnetfiddle.net? It sounds me impossible. Are you speaking about Linq.Parallel or the normal(serial) one?

– robert4 – 2016-02-02T18:43:59.397

@robert4 take a look at ToLookup which calls Lookup.Create. It runs serially on the source enumerable and calls Grouping.Add that encapsulate a simple array buffer.

– HuBeZa – 2016-02-03T07:42:11.410

@HuBeZa This proves that the order of elements is preserved within the groups, which I didn't question. I contradicted with the first half of your claim: “ToLookup changes the keys order”. Lookup.Create calls lookup.GetGrouping() for every item of the source, which creates groups in a manner that preserves the ordering of keys, as I detailed above.

– robert4 – 2016-02-03T13:00:16.800

You didn't mention Aggregate. Aggregate follows the order because the concept of Aggregate requires that it follows the order. Here's the Reference Source to verify this. I realize that since it's kind of a given, it might not be important enough to mention, but it's not mentioned anywhere on this Q&A.

– Zach Mierzejewski – 2017-03-17T16:05:12.307

1@ZachMierzejewski Aggregate was excluded because it does not return an IEnumerable. With no enumerable result, the order of the result does not exist and cannot be defined as preserved or not. It is important to know that Aggregate processes the input in order, same as all the methods which have an IEnumerable source. – Amy B – 2017-03-17T16:57:33.970

2Actually, I think Distinct preserves original (first found) order - so {1,2,1,3,1,3,4,1,5} would be {1,2,3,4,5} – Marc Gravell – 2008-10-15T14:33:32.897

10

http://msdn.microsoft.com/en-us/library/bb348436.aspx

The Distinct<(Of <(TSource>)>)(IEnumerable<(Of <(TSource>)>)) method returns an unordered sequence that contains no duplicate values.

– Amy B – 2008-10-15T14:47:25.430

12Marc: what you say could be true, but it would be a bad idea to rely on that behavior. – Amy B – 2008-10-15T14:52:16.230

1@David B I think it would be unreasonable to implement Distinct (for linq to objects) in a way that doesn't preserve order, since that would perform worse than if it did preserve order. – dan – 2011-07-14T06:34:04.763

1@dan shrug if you want to defy the documentation, that's up to you. – Amy B – 2011-08-18T01:16:57.887

2@David B yes but it doesn't apply to Linq to Objects. In Linq to Sql, distinct() puts the distinct keyword into the generated sql, and ordering from sql is not guaranteed. I'd be interested to see an implementation of distinct for linq to objects that doesn't preserve order and is more efficient that one that does preserve order. For example, you can consume the entire input and put it in a hashset, then yield values by enumerating the hashset (losing order), but that's worse. So yeah, I don't mind defying documentation every now and then :) – dan – 2011-08-19T03:39:52.757

@Dan "Found First" destroys order. In that list the 1 is before and after the 4. By making it a distinct list, that ordering is gone. – Rangoric – 2011-08-31T15:51:27.340

1@Rangoric - depends on your definition of preserves order. If we go with the FoundFirst for Distinct - one could aruge that elements are filtered and not reordered. The only reason I have for not choosing that option, is the documentation says "unordered". – Amy B – 2011-09-02T17:16:46.180

@David and that's why. Found First isn't the same as Distinct. If there comes a time when someone has a way to do distinct without preserving order that is faster, then by all means, I don't want to hold them back because of an assumption. – Rangoric – 2011-09-02T22:19:39.397

I think it's funny that no one ever asked me to move Union to Preserving Order... it has the same Found First behavior as Distinct. – Amy B – 2018-06-08T18:45:46.473

So why doesn't, eg, Skip (and other things on the order preserved list) return an IOrderedEnumerable?

– ruffin – 2018-09-07T21:27:42.707

@ruffin It might be helpful to think about what IOrderedEnumerable&lt;T&gt; is for. Without this interface, we could not call ThenBy. Does it make sense to call customers.Skip(5).ThenBy(c =&gt; c.Name) ? Skip does not define an ordering - its implementation doesn't change the order. – Amy B – 2018-09-08T07:47:34.783

Thanks for the reply! The flipside of this, however, is that IEnumerable doesn't guarantee order, and I wouldn't've assumed I could count on something returning IEnumerable "doesn't change the order". It seems smelly to say that a function that returns an unordered type guarantees that unordered type's order is preserved. Wait, what? ;^) If customers has an internalized idea of how it's ordered (ie, the formula by which it's ordered, which I admit I don't think is the case), then your Skip usage would, in fact, make sense. orderedByCountyCustomers.Skip(5).ThenBy(c =&gt; c.Name) – ruffin – 2018-09-10T15:14:04.413

Interesting continuation of your point in this answer from Eric Lippert & discussion with Skeet. Still seems weird to pretend an IEnumerable has an order to be preserved when it doesn't guarantee order (ie, is implicitly unordered)... I think it's probably better for me to think that an IEnumerable can be ordered, but doesn't, by itself, guarantee order. IOrderedEnumerable probably isn't the best name for what it's doing either.. IInTheProcessOfBeingOrderedEnumerable? /shrug Thanks again.

– ruffin – 2018-09-10T15:33:54.560

@ruffin most IEnumerable&lt;T&gt; have an order (for example, array index order). When they do, the order is preserved by the operations. When they don't, there is no order to preserve. All IOrderedEnumerable&lt;T&gt; have a defined order. That defined order is respected and modified by calls to ThenBy. – Amy B – 2018-09-10T16:17:57.503

1I think you were correct to go by the documented behavior of Distinct and not the implementation. Nothing says .Net has to run on a Von Neumann architecture - on a version for a Connection Machine, perhaps not preserving order would be a better implementation. – NetMage – 2018-11-29T00:26:18.333

29

Are you actually talking about SQL, or about arrays? To put it another way, are you using LINQ to SQL or LINQ to Objects?

The LINQ to Objects operators don't actually change their original data source - they build sequences which are effectively backed by the data source. The only operations which change the ordering are OrderBy/OrderByDescending/ThenBy/ThenByDescending - and even then, those are stable for equally ordered elements. Of course, many operations will filter out some elements, but the elements which are returned will be in the same order.

If you convert to a different data structure, e.g. with ToLookup or ToDictionary, I don't believe order is preserved at that point - but that's somewhat different anyway. (The order of values mapping to the same key is preserved for lookups though, I believe.)

Jon Skeet

Posted 2008-10-15T12:20:13.293

Reputation: 1 070 456

What about ToArray? – devinbost – 2015-10-19T21:24:07.220

@bostIT: as per the answer, it's not an operation that changes order... – Jon Skeet – 2015-10-19T21:49:30.083

so because OrderBy is a stable sort, then: seq.OrderBy( => .Key ) will put the elements in to exactly the same order as seq.GroupBy( => .Key ).SelectMany( => ). Is that correct? – dmg – 2016-02-01T22:11:37.623

1@dmg: No, it won't. Just GroupBy followed by SelectMany will give the results grouped by key, but not in ascending key order... it will give them in the order in which the keys originally occurred. – Jon Skeet – 2016-02-01T22:54:53.360

are you saying that LINQ to SQL does not preserver order? – symbiont – 2016-08-19T08:39:09.300

@symbiont: In many SQL operations there is no well-defined order to start with. Basically I'm trying to only make promises about things I can guarantee - such as LINQ to Objects. – Jon Skeet – 2016-08-19T08:48:40.307

@JonSkeet If I use OrderBy does it guarantee that 'n' objects with the same key will preserve their original sequence except that they are all together. ie.:in list&lt;x&gt; {a b c d e f g} if c,d,e all have the same key then the resulting sequence will contain c,d,e next to each other AND in the order c,d,e. I can't seem to find a categorical MS-based answer. – Paulustrious – 2017-10-10T18:28:13.303

@Paulustrious: In LINQ to Objects, yes. In other providers, it's implementation-specific. – Jon Skeet – 2017-10-10T18:29:27.013

@JonSkeet You're good. You answered while I was still editing my question – Paulustrious – 2017-10-10T18:35:05.123

@Paulustrious: From https://msdn.microsoft.com/en-us/library/bb534966(v=vs.110).aspx: "This method performs a stable sort; that is, if the keys of two elements are equal, the order of the elements is preserved. In contrast, an unstable sort does not preserve the order of elements that have the same key."

– Jon Skeet – 2017-10-10T18:36:03.900

6

If you are working on an array, it sounds like you are using LINQ-to-Objects, not SQL; can you confirm? Most LINQ operations don't re-order anything (the output will be in the same order as the input) - so don't apply another sort (OrderBy[Descending]/ThenBy[Descending]).

[edit: as Jon put more clearly; LINQ generally creates a new sequence, leaving the original data alone]

Note that pushing the data into a Dictionary<,> (ToDictionary) will scramble the data, as dictionary does not respect any particular sort order.

But most common things (Select, Where, Skip, Take) should be fine.

Marc Gravell

Posted 2008-10-15T12:20:13.293

Reputation: 772 074

If I'm not mistaken, ToDictionary() merely makes no promises about the order, but in practice maintains the input order (until you remove something from it). I'm not saying to rely on this, but 'scrambling' seems inaccurate. – Timo – 2017-10-17T13:42:58.143

3

I found a great answer in a similar question which references official documentation. To quote it:

For Enumerable methods (LINQ to Objects, which applies to List<T>), you can rely on the order of elements returned by Select, Where, or GroupBy. This is not the case for things that are inherently unordered like ToDictionary or Distinct.

From Enumerable.GroupBy documentation:

The IGrouping<TKey, TElement> objects are yielded in an order based on the order of the elements in source that produced the first key of each IGrouping<TKey, TElement>. Elements in a grouping are yielded in the order they appear in source.

This is not necessarily true for IQueryable extension methods (other LINQ providers).

Source: Do LINQ's Enumerable Methods Maintain Relative Order of Elements?

Curtis Yallop

Posted 2008-10-15T12:20:13.293

Reputation: 4 114

2

Any 'group by' or 'order by' will possibly change the order.

leppie

Posted 2008-10-15T12:20:13.293

Reputation: 96 420