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

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


```csharp
public record Product(string Name, double Price);
```

次のようなリストをソートして、新たなリストを作るコードがあります。

```csharp
List<Product> products = LoadProducts();
List<Product> orderedProducts = source.OrderBy(product => product.Price).ToList();
```

上のコードでは、ソートをしているから、O(n log n)かかりますね。

次に`OrderBy`と`First`を使って、一番Priceが小さい要素を探してみましょう。

```csharp
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)です。

---



```csharp
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](https://github.com/RyotaMurohoshi/ImportedLinq)」というものを開発・公開しています。、「一番Priceが小さい要素を探してみる」みたいな状況では、ImpotedLinqの「[MinByメソッド](https://github.com/RyotaMurohoshi/ImportedLinq#maxby--minby)」を使うことをおすすめします。Scala・Kotlinのコレクションライブラリ・そしてIx.NETと同名のメソッドで同じような処理を提供しています。あるていど知られた名前で、内部実装の解離がなく、読みやすいと思います。

---

じゃあ、「.OrderBy(keySelector).First(predicate)」はどうなんだと思ったあなた？すばらしい。実は.NET 5でBreaking Changesがあったそうです。詳しくはこちら:「[Complexity of LINQ OrderBy.First{OrDefault} increased](https://docs.microsoft.com/en-us/dotnet/core/compatibility/core-libraries/5.0/orderby-firstordefault-complexity-increase)」