LINQ OrderBy.First{OrDefault} の複雑さが増大

  • [アーティクル]

OrderBy.First<TSource>(IEnumerable<TSource>, Func<TSource,Boolean>) と OrderBy.FirstOrDefault<TSource>(IEnumerable<TSource>, Func<TSource,Boolean>) の実装が変更され、その結果として操作の複雑さが増大します。

変更の説明

.NET Core 1.x - 3.x では、OrderBy または OrderByDescending に続けて、First<TSource>(IEnumerable<TSource>, Func<TSource,Boolean>) または FirstOrDefault<TSource>(IEnumerable<TSource>, Func<TSource,Boolean>) を呼び出した場合、O(N) の複雑さで動作します。 最初の (または既定の) 要素のみが必要であるため、それを検索するのに必要な列挙は 1 つのみです。 ただし、First<TSource>(IEnumerable<TSource>, Func<TSource,Boolean>) または FirstOrDefault<TSource>(IEnumerable<TSource>, Func<TSource,Boolean>) に指定された述語は厳密には N 回呼び出されます。ここで、N はシーケンスの長さです。

.NET 5 以降のバージョンでは、次のような変更が加えられました: OrderBy または OrderByDescending の後に First<TSource>(IEnumerable<TSource>, Func<TSource,Boolean>) または FirstOrDefault<TSource>(IEnumerable<TSource>, Func<TSource,Boolean>) を呼び出すと、O(N) の複雑さではなく O(N log N) の複雑さで動作します。 ただし、First<TSource>(IEnumerable<TSource>, Func<TSource,Boolean>) または FirstOrDefault<TSource>(IEnumerable<TSource>, Func<TSource,Boolean>) に指定された述語の呼び出し回数は、N 回より "少なく" することができます。これは、全体的なパフォーマンスにとって重要なことです。

注意

この変更は、.NET Framework での操作の実装と複雑さに一致します。

変更理由

述語を呼び出す回数を減らすことの利点は、全体的な複雑さが低いことより重要であるため、.NET Core 1.0 で導入された実装は元に戻されました。 詳細については、こちらの dotnet、ランタイムに関する問題を参照してください。

導入されたバージョン

5.0

開発者側では、何も行う必要はありません。

影響を受ける API