13

これは純粋に私自身の知識のためであり、私が使用するコードを書くつもりなら.Max().

最初の考えでは、最大値を見つけるために.Max()1 回のパススルーを実行するだけでnumbers済みますが、2 番目の方法では、列挙可能なもの全体を並べ替えてから、最初のものを見つける必要があります。だからそれはO(n)対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);

最大() : 70ms

OrderBy() : 2066ms

また、それを超えてカウントを増やしすぎると、OrderBy() は OutOfMemoryException で失敗しますが、Max() はそうではありません。

于 2012-04-24T02:34:44.023 に答える
7

.Max()O（n）ですが、あなたのOrderByDescendingソリューションはそうではありません-ソートによっては、おそらくO（nlog（n））です。

私は明らかにコンパイラーの内部を掘り下げて知りませんでしたが、あなたが求めていること (ソートを実現してから 1 つの項目のみを取得する最適化は .max と同じです) は、コンパイラーからかなりのものです。

于 2012-04-24T02:29:20.380 に答える
6

オブジェクトへの直接の LINQ について話している場合は、いいえ、最適化されていません。

おそらく別の 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 に答える