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.