13

这纯粹是为了我自己的知识，如果我要编写我会使用的代码.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();
4

4 回答 4

12

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);

最大（）：70毫秒

OrderBy() : 2066 毫秒

此外，如果您将计数增加太多，OrderBy() 会失败并出现 OutOfMemoryException，Max() 不会。

于 2012-04-24T02:34:44.023 回答
7

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

我显然没有在编译器内部挖掘知道，但是你所要求的（实现排序然后只抓取一个项目的优化与.max 相同）来自编译器。

于 2012-04-24T02:29:20.380 回答
6

如果您正在谈论直接 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();
}
于 2012-04-24T02:29:41.537 回答
4

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

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

于 2017-12-05T09:44:40.683 回答