こんなレコードがあります。
public record Product(string Name, double Price);
次のようなリストをソートして、新たなリストを作るコードがあります。
List<Product> products = LoadProducts();
List<Product> orderedProducts = source.OrderBy(product => product.Price).ToList();
上のコードでは、ソートをしているから、O(n log n)かかりますね。
次にOrderByとFirstを使って、一番Priceが小さい要素を探してみましょう。
List<Product> products = LoadProducts();
Product minPriceProduct = source.OrderBy(product => product.Price).First();
「リストの中から一番Priceが小さい要素」を見つけたいならば、わざわざOrderByでソートする必要はありませんね。foreach文などで要素を一巡すればいい目的を達成できます。O(n)で済むはずです。
上のコードは、OrderByでソートしているから、一見O(n log n)かかっているように見えます。ところが実は、.NET 5や.NET Core 3.1だと、上記のコードのように「OrderBy(keySelector).First()と連続した呼び出し」の場合はO(n)で済みます。連続した呼び出しの場合でソートしていません。特別な実装を用意していて、要素を一巡して最小の要素を返すようにしています。
.NET 5.0.1のコードは以下を参照
- https://github.com/dotnet/runtime/blob/v5.0.1-servicing.20575.16/src/libraries/System.Linq/src/System/Linq/OrderBy.cs#L10-L11
- https://github.com/dotnet/runtime/blob/v5.0.1-servicing.20575.16/src/libraries/System.Linq/src/System/Linq/First.cs#L13
- https://github.com/dotnet/runtime/blob/v5.0.1-servicing.20575.16/src/libraries/System.Linq/src/System/Linq/First.cs#L48
- https://github.com/dotnet/runtime/blob/v5.0.1-servicing.20575.16/src/libraries/System.Linq/src/System/Linq/OrderedEnumerable.SpeedOpt.cs#L163-L188
.NET Core 3.1.9のコードは以下を参照
- https://github.com/dotnet/corefx/blob/v3.1.9/src/System.Linq/src/System/Linq/OrderBy.cs#L11-L12
- https://github.com/dotnet/corefx/blob/v3.1.9/src/System.Linq/src/System/Linq/First.cs#L13
- https://github.com/dotnet/corefx/blob/v3.1.9/src/System.Linq/src/System/Linq/First.cs#L48
- https://github.com/dotnet/corefx/blob/v3.1.9/src/System.Linq/src/System/Linq/OrderedEnumerable.SpeedOpt.cs#L163-L188
.NET Core 1.0.0のコードは以下を参照
- https://github.com/dotnet/corefx/blob/v1.0.0/src/System.Linq/src/System/Linq/First.cs#L22
- https://github.com/dotnet/corefx/blob/v1.0.0/src/System.Linq/src/System/Linq/OrderBy.cs#L13
- https://github.com/dotnet/corefx/blob/v1.0.0/src/System.Linq/src/System/Linq/OrderedEnumerable.cs#L246-L271
ちなみに.NET Framework 4.8は違うようです。O(n log n)かかります。
ちなみに、OrderBy(keySelector).First()だけでなく、次の組み合わせもO(n)です。
- .OrderBy(keySelector).First()
- .OrderBy(keySelector).FirstOrDefault()
- .OrderBy(keySelector).Last()
- .OrderBy(keySelector).LastOrDefault()
- .OrderByDescending(keySelector).First()
- .OrderByDescending(keySelector).FirstOrDefault()
- .OrderByDescending(keySelector).Last()
- .OrderByDescending(keySelector).LastOrDefault()
OrderBy/OrderByDescendingの後に、ThenByやThenByDescendingを複数回挟んで、その後にFirst/FirstOrDefault/Last/LastOrDefaultを呼んでもO(n)です。
OrderBy/OrderByDescendingは他のオーバーロードでも、O(n)です。
List<Product> products = LoadProducts();
Product minPriceProduct = source.OrderBy(product => product.Price).First();
.NET Core/.NETにおいて、上記のコードは、一見O(n log n)かけてソートして最小要素を探しているように見えるけれど、実は要素を一巡列挙しているだけでO(n)ですみます。ソートをしていません。
しかし、それはメソッド名を読んだだけではそれは分からず、.NET Core/.NETの実装を把握している必要があります。ちょっと、ややこしいですね。
ちなみに私はライブラリ「ImportedLinq」というものを開発・公開しています。、「一番Priceが小さい要素を探してみる」みたいな状況では、ImpotedLinqの「MinByメソッド」を使うことをおすすめします。Scala・Kotlinのコレクションライブラリ・そしてIx.NETと同名のメソッドで同じような処理を提供しています。あるていど知られた名前で、内部実装の解離がなく、読みやすいと思います。
じゃあ、「.OrderBy(keySelector).First(predicate)」はどうなんだと思ったあなた？すばらしい。実は.NET 5でBreaking Changesがあったそうです。詳しくはこちら:「Complexity of LINQ OrderBy.First{OrDefault} increased」