On Tuesday, 15 December 2015 at 09:57:00 UTC, ZombineDev wrote:


And then you have one of the most used methods - .Count:
https://msdn.microsoft.com/en-us/library/bb338038(v=vs.100).aspx

Where presumably, for the sake of simplicity, the docs don't even bother to mention that it is almost always O(n), because non of the Enumerable extention methods preserve the underlying ICollection interace.

Looking at the .net source code, the Count extension method is also doing a best effort "count" by querying the ICollection interface.

public static int Count<TSource>(this IEnumerable<TSource> source)
    {
      if (source == null)
        throw Error.ArgumentNull("source");
ICollection<TSource> collection1 = source as ICollection<TSource>;
      if (collection1 != null)
        return collection1.Count;
      ICollection collection2 = source as ICollection;
      if (collection2 != null)
        return collection2.Count;
      int num = 0;
using (IEnumerator<TSource> enumerator = source.GetEnumerator())
      {
        while (enumerator.MoveNext())
          checked { ++num; }
      }
      return num;
    }

The Remarks section clearly states the same thing:

"If the type of source implements ICollection<T>, that implementation is used to obtain the count of elements. Otherwise, this method determines the count."


And personally, I found the MS remark more compact and more user friendly than:

"This is a best-effort implementation of length for any kind of range. If hasLength!Range, simply returns range.length without checking upTo (when specified). Otherwise, walks the range through its length and returns the number of elements seen. Performes Ο(n) evaluations of range.empty and range.popFront(), where n is the effective length of range."

Not everybody is licensed in computational complexity theory to understand what O(n) means.



Reply via email to