はじめに
Qiita 記事は初投稿となります。いろいろとおかしな点もあるかもしれません。
さて、TwitterでC#における OrderByとSortのパフォーマンスの違いの話になって、自分もどれくらいの差があるのか把握していなかったので、検証して、せっかくなので記事に残すことにしました。
環境
この記事では、以下の環境を使用しました。
Windows 10 Home
Intel Core i5 6400T
.NET Framework 4.6.1
Visual Studio 2019 Debug環境
検証方法
元の配列は、0から(10^6 - 1)を昇順に並べた、100万要素の配列とする。
Array.Sort(array) List<T>.Sort() enumerable.OrderBy(x => x) それぞれについて、ソートを10回行う。
- 以下に記載してある時間は「ミリ秒単位」で「ソート10回分」です。(1回あたりは10で割ってください。)
ランダム順の配列を並び替え
以下の操作を10回行い、ソート10回にかかった時間の平均値・最大値・最小値を計算します。
- 元の配列をランダム順に並び替える。
- それぞれのソート関数でソートを実行する。
結果
| Array.Sort | List.Sort | OrderBy | |
|---|---|---|---|
| Max | 1721ms | 1448ms | 5428ms |
| Min | 1307ms | 1301ms | 5177ms |
| Ave | 1375.5ms | 1347.7ms | 5306.7ms |
ランダム順では、List.Sort が Array.Sortよりわずかに早く、OrderBy はそれらより4倍近く遅い結果となりました。
昇順・降順の配列を並び替え
以下の操作それぞれで、ソート10回にかかった時間を計算します。
- 昇順となっている（すでにソートされている）配列に対してソートを実行する。
- 降順となっている配列に対してソートを実行する。
結果
| Array.Sort | List.Sort | OrderBy | |
|---|---|---|---|
| 昇順 | 175ms | 184ms | 2608ms |
| 降順 | 368ms | 313ms | 1923ms |
昇順配列におけるソートでは、 Array.Sort が List.Sort よりわずかに早く、 OrderBy はそれらより15倍近く(!)遅い結果となりました。
降順配列におけるソートでは、 List.Sort が Array.Sort より少し早く、 OrderBy はそれらより6倍近く遅い結果となりました。
それぞれの関数別にみると、
Array.Sort では、昇順配列におけるソートが降順配列におけるソートより約2倍早く、ランダム配列におけるソートより約8倍早い。
List.Sort では、昇順配列におけるソートが降順配列におけるソートより約1.7倍早く、ランダム配列におけるソートより約7.3倍早い。
OrderBy では、昇順配列におけるソートが降順配列におけるソートより約1.3倍遅く、ランダム配列におけるソートより約2倍早いという結果になりました。
まとめ
今回の検証に使用したコードは、 Gistに載せています。
数値や文字列などの、オブジェクト自体の並び替えには、絶対に Array.Sort や List<T>.Sort() を使いましょう!! (特に私は競技プログラミングをやっていて、数百ミリ秒でも早いほうがいいため、今後はSortを使うことをより意識しようと思います。ソートが原因でTLEはくらいたくない!!)
今回は検証していませんが、オブジェクトのプロパティを指定した並び替えでも、objects.OrderBy(x => x.Target); とするよりも、ToArray() → Array.Sort(objectsArray, (a, b) => a.Target.CompareTo(b.Target); としたほうが高速だと思います。
OrderBy は、IEnumerable<T> を対象に並び替えができるようになっているため、遅い実装になっているんですかね…。
- もしかしたら遅延評価の問題などで、
OrderByのほうが高速になることがあるかもしれません。 (特にEnumerateFilesなどで外部にアクセスするとき)
この記事について、ご意見やご指摘などがありましたら、記事のコメント等へお願いいたします。