LoginSignup
2

More than 1 year has passed since last update.

posted at

updated at

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

次にOrderByFirstを使って、一番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のコードは以下を参照

.NET Core 3.1.9のコードは以下を参照

.NET Core 1.0.0のコードは以下を参照

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

Register as a new user and use Qiita more conveniently

  1. You get articles that match your needs
  2. You can efficiently read back useful information
What you can do with signing up
2