Count IOrderedEnumerable without consuming it

Question

What I want to do is short version:

var source = new[]{2,4,6,1,9}.OrderBy(x=>x); int count = source.Count; // <-- get the number of elements without performing the sort 

---

Long version:

To determine the number of elements in IEnumerable, you need to iterate over all the elements. This can be a very expensive operation.

If IEnumerable can be attributed to ICollection, then the score can be quickly determined without repetition. The LINQ Count () method does this automatically.

The myEnumerable.OrderBy () function returns the value of IOrderedEnumerable. Obviously, IOrderedEnumerable cannot be attributed to ICollection, so calling Count () will consume all of this.

But sorting does not change the number of elements, and IOrderedEnumerable should contain a link to its source. Therefore, if this source is an ICollection, it should be able to determine the counter from IOrderedEnumerable without consuming it.

My goal is to have a library method that takes an IEnumerable with n elements, and then, for example, extracts the element at position n / 2;

I want to avoid repeating IEnumerable twice to get its score, but I also want to avoid making an unnecessary copy, if at all possible.

---

Here is the skeleton of the function I want to create

 public void DoSomething(IEnumerable<T> source) { int count; // What we do with the source depends on its length if (source is ICollection) { count = source.Count(); // Great, we can use ICollection.Count } else if (source is IOrderedEnumerable) { // TODO: Find out whether this is based on an ICollection, // TODO: then determine the count of that ICollection } else { // Iterating over the source may be expensive, // to avoid iterating twice, make a copy of the source source = source.ToList(); count = source.Count(); } // do some stuff } 

Answer 1

Think about what this code looks like:

 var source = new[]{ 2, 4, 6, 1, 9 }.OrderBy(x => x); int count = source.Count(); 

This is the same as

 int count = Enumerable.Count(Enumerable.OrderBy(new[]{ 2, 4, 6, 1, 9 }, x => x)); 

The result of Enumerable.OrderBy(new[]{ 2, 4, 6, 1, 9 }, x => x) is passed to the Count extension. You cannot avoid executing OrderBy . And thus, this is not a streaming operator; it consumes the entire source before returning anything that will be passed to Count .

Thus, the only way to avoid iterating the entire collection is to avoid OrderBy by counting items before sorting.

---

UPDATE: you can call this extension method on any OrderedEnumerable - it will use reflection to get the source OrderedEnumerable<T> field that contains the original sequence. Then check if this sequence is a collection and use Count without completing the order:

 public static class Extensions { public static int Count<T>(this IOrderedEnumerable<T> ordered) { // you can check if ordered is of type OrderedEnumerable<T> Type type = ordered.GetType(); var flags = BindingFlags.NonPublic | BindingFlags.Instance; var field = type.GetField("source", flags); var source = field.GetValue(ordered); if (source is ICollection<T>) return ((ICollection<T>)source).Count; return ordered.Count(); } } 

Using:

 var source = new[]{ 2, 4, 6, 1, 9 }.OrderBy(x => x); int count = source.Count(); 

Answer 2

If you want to create a solution for performers, I would think of creating overloads that take either a collection or IOrderedEnumerable, etc. all that "is" and "like" typechecking and casting may not be good for the kind that you create.

You reinvent the wheel. The linq "Count ()" function does everything you need.

Also, add this keyword and make it a great way to expand to please yourself and others with code.

 DoSomething(this Collection source); DoSomething<T>(this List<T> source); DoSomething<T>(this IOrderedEnumerable<T> source); 

etc...

Answer 3

Another approach is to implement a class that implements IOrderedEnumerable<T> . You can then implement class members that will lock down regular Linq extension methods and provide a counting method that looks at the original enumeration.

 public class MyOrderedEnumerable<T> : IOrderedEnumerable<T> { private IEnumerable<T> Original; private IOrderedEnumerable<T> Sorted; public MyOrderedEnumerable(IEnumerable<T> orig) { Original = orig; Sorted = null; } private void ApplyOrder<TKey>(Func<T, TKey> keySelector, IComparer<TKey> comparer, bool descending) { var before = Sorted != null ? Sorted : Original; if (descending) Sorted = before.OrderByDescending(keySelector, comparer); else Sorted = before.OrderBy(keySelector, comparer); } #region Interface Implementations public IEnumerator<T> GetEnumerator() { return Sorted != null ? Sorted.GetEnumerator() : Original.GetEnumerator(); } IEnumerator IEnumerable.GetEnumerator() { return GetEnumerator(); } public IOrderedEnumerable<T> CreateOrderedEnumerable<TKey>( Func<T, TKey> keySelector, IComparer<TKey> comparer, bool descending) { var newSorted = new MyOrderedEnumerable<T>(Original); newSorted.ApplyOrder(keySelector, comparer, descending); return newSorted; } #endregion Interface Implementations //Ensure that OrderBy returns the right type. //There are other variants of OrderBy extension methods you'll have to short-circuit public MyOrderedEnumerable<T> OrderBy<TKey>(Func<T, TKey> keySelector) { Console.WriteLine("Ordering"); var newSorted = new MyOrderedEnumerable<T>(Original); newSorted.Sorted = (Sorted != null ? Sorted : Original).OrderBy(keySelector); return newSorted; } public int Count() { Console.WriteLine("Fast counting.."); var collection = Original as ICollection; return collection == null ? Original.Count() : collection.Count; } public static void Test() { var nums = new MyOrderedEnumerable<int>(Enumerable.Range(0,10).ToList()); var nums2 = nums.OrderBy(x => -x); var z = nums.Count() + nums2.Count(); } }