.Max()vs OrderByDescending().First()

Question

这纯粹是出于我自己的知识,如果我要编写我将使用的代码.Max().

起初认为.Max()只需要通过一次通过numbers来找到最大值,而第二种方法必须对可枚举的整个事物进行排序然后找到第一种.所以这是O(n)VS O(n lg n).但后来我想也许它知道它只需要最高,只是抓住它.

问题: LINQ和/或编译器是否足够智能,以确定它不需要对整个可枚举进行排序,并将代码缩小到与.Max()基本相同的位置？找到可量化的方法吗？

IEnumerable<int> numbers = Enumerable.Range(1, 1000);

int max  = numbers.Max();
int max2 = numbers.OrderByDescending(x => x).First();

Answer 1

LINQ和/或编译器是否足够聪明,可以确定它不需要对整个可枚举进行排序,并将代码简化为与.Max()基本相同的代码？

没有.

找到可量化的方法吗？

使用秒表的简单基准:

    var numbers = Enumerable.Range(1, 10000000);
    var sw = Stopwatch.StartNew();
    int max = numbers.Max();
    Console.WriteLine(sw.ElapsedMilliseconds);
    sw.Restart();
    int max2 = numbers.OrderByDescending(x => x).First();
    Console.WriteLine(sw.ElapsedMilliseconds);

Max():70ms

OrderBy():2066ms

另外,如果你将计数增加到太多,则OrderBy()会因OutOfMemoryException而失败,Max()则不会.

Answer 2

如果你正在谈论直接LINQ to Objects,那么不,它没有为此进行优化.

可能是另一个LINQ提供商可以做到的,但这取决于实现的细节.

对于Enumerable,Reflector给出的实现是:

public static IOrderedEnumerable<TSource> OrderBy<TSource, TKey>(this IEnumerable<TSource> source, Func<TSource, TKey> keySelector)
{
    return new OrderedEnumerable<TSource, TKey>(source, keySelector, null, false);
}

并为 First()

public static TSource First<TSource>(this IEnumerable<TSource> source)
{
    if (source == null)
    {
        throw Error.ArgumentNull("source");
    }
    IList<TSource> list = source as IList<TSource>;
    if (list != null)
    {
        if (list.Count > 0)
        {
            return list[0];
        }
    }
    else
    {
        using (IEnumerator<TSource> enumerator = source.GetEnumerator())
        {
            if (enumerator.MoveNext())
            {
                return enumerator.Current;
            }
        }
    }
    throw Error.NoElements();
}

Answer 3

.Max()是O(n),而你的OrderByDescending解决方案不是 - 根据排序,它可能是O(nlog(n)).

我显然没有在编译器中挖掘知道,但你要求的是(实现排序然后只抓取一个项目的优化与.max相同的优化)在编译器中相当多.

Answer 4

看来 OrderedEnumerable 现在足够聪明，可以发现它不需要对 First 和 Last() 的列表进行排序。

请注意第 223 行 TryGetFirst() 附近的代码 https://github.com/dotnet/corefx/blob/ed0ee133ac49cee86f10ca4692b1d72e337bc012/src/System.Linq/src/System/Linq/OrderedEnumerable.cs