.NETや.NET CoreのOrderBy(keySelector).First()はO(n log n)でなくてO(n)な件

こんなレコードがあります。

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)かかります。

• https://referencesource.microsoft.com/#System.Core/System/Linq/Enumerable.cs,1042

---

ちなみに、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」