はじめに
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などで外部にアクセスするとき)
この記事について、ご意見やご指摘などがありましたら、記事のコメント等へお願いいたします。