c# - 評価 - ブレークポイントがバインドできませんでした
なぜ `.Select(…).Last()`が最適化されているのに `.Select(…).Last(…)`が最適化されていないのでしょうか。 (1)
Last()
は、コレクションの最後の要素に一定時間アクセスできるようにするコレクションに対して常に最適化できます( O(1)
)。 これらのコレクションでは、すべてのコレクションを繰り返して最後の要素を返す代わりに、最後の要素に直接アクセスすることができます。
概念的には、少なくとも1つの要素が述語を満たす場合(実際にはそうです)、逆方向に反復すると、ループを早く終了できる可能性があります。
その仮定は、 Last(Func<T,bool>)
一般的な実装のためにはあまりにもフェッチされすぎています。 述語を満たす最後の要素が、一般にコレクションの末尾に近いとは限りません。 その最適化はあなたの例ではうまくいきます( Last(x=>true)
)が、そのような例ごとにその最適化がより悪い( Last(x=>false)
)という反対の例があるかもしれません。
次の列挙子を考えます。
var items = (new int[] { 1, 2, 3, 4, 5 }).Select(x =>
{
Console.WriteLine($"inspect {x}");
return x;
});
これにより要素[1, 2, 3, 4, 5]
1、2、3、4、5 [1, 2, 3, 4, 5]
が生成され、消費されたとおりにそれらが表示されます。
この列挙子でLast
メソッドを呼び出すと、単一の要素にのみアクセスする高速パスがトリガーされます。
items.Last();
inspect 5
しかし、私がLast
にコールバックを渡すとき、それは最初からリスト全体をループします:
items.Last(x => true);
inspect 1
inspect 2
inspect 3
inspect 4
inspect 5
.NET Coreのソースコードを見ると、次のことがわかります。
-
Last(IEnumerable<T>)
はTryGetLast(IEnumerable<T>, out bool)
転送しTryGetLast(IEnumerable<T>, out bool)
。 -
TryGetLast(IEnumerable<T>, out bool)
は、IPartition<T>
高速パスがあります。 - そして、
ArraySelectIterator<T>
はArraySelectIterator<T>
実装しているIPartition<T>
、この高速パスが起動され、すべて問題ありIPartition<T>
。
一方:
-
Last(IEnumerable<T>, Func<T, bool>)
はTryGetLast(IEnumerable<T>, Func<T, bool>, out bool)
転送しTryGetLast(IEnumerable<T>, Func<T, bool>, out bool)
- これには
OrderedEnumerator
とIList<T>
高速パスがありIList<T>
が、ArraySelectIterator<T>
高速パスはありません 。 - したがって、それは遅い道をたどり、最初から繰り返します。
これは、コールバックケースがどのように最適化されていないかを説明しています。 しかし、それは理由を説明していません。
概念的には、少なくとも1つの要素が述語を満たす場合(実際にはそうです)、逆方向に反復すると、ループを早く終了できる可能性があります。
実装するのもそれほど難しいことではありません。私が見たことから言えば、必要なのはIPartition<T>
追加のメソッドだけです。
最適化の欠如もまた驚くべきことです。 これらのオーバーロードは同じ名前を共有しているので、それらも同様に最適化されていると考えるかもしれません。 (少なくともそれが私が考えたことです。)
このケースを最適化するためのこれらの理由から、LINQの作者はなぜそうしないことを選んだのでしょうか。