お久しぶりです、エンジニアのMasashiです。
今回はListの中身をソートする際の速度について検証を行ってみます。
Sort関数を使用する、Linqを使う、Compare関数を拡張する等々
ソートの行い方は様々ありますが、今回は単純な数値の入ったデータをSort関数とLinqを使った方法で検証してみたいと思います。
また、昇順だけでなく降順の並び替えも実施して速度に違いが出るか検証しています。
ListやArrayの降順に並び替える方法としてはよくない方法で並び替えていますが、
今回は純粋なソートの速度差を見るだけですので、テストコードの実装で検証しています。
測定までの流れ
今回測定を行うのは、Listに格納されている乱数を昇順・降順に並び替えるまでにかかった時間になっています。
比較対象として配列のソート、Listのソート、ListをLinqでソートの3つで速度を検証しています。
測定環境
- Visual Studio 2015
対象データ
- データ数:1,000,000
- Listの中身:0~100,000までの乱数
測定対象
- 配列をArray.Sortを使用して昇順にソート
- ListをList.Sortを使用して昇順にソート
- ListをLinqを使用して昇順にソート
- 配列をArray.Sort・Array.Reverseを使用して降順にソート
- ListをList.Sort・List.Reverseを使用して降順にソート
- ListをLinqを使用して降順にソート
テストコード
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 |
using System; using System.Collections.Generic; using System.Diagnostics; using System.Linq; namespace ListSortSpeed { internal class Program { // テストデータ数 private const int DataCount = 1000000; // 乱数:最大値 private const int MaxValue = 100000; private static void Main() { var arr = MakeArray(); for (var i = 0; i < 10; i++) { Console.WriteLine("----------------"); ArraySortAsc(arr); ArraySortDesc(arr); ListSortAsc(arr); ListSortDesc(arr); ListLinqSortAsc(arr); ListLinqSortDesc(arr); Console.WriteLine("----------------"); } Console.WriteLine("続行するには何かキーを押してください:"); Console.ReadKey(); } // Array.Sortで並び替え(昇順) private static void ArraySortAsc(int[] arr) { var copyArr = new int[DataCount]; Array.Copy(arr, copyArr, arr.Length); var stopwatch = new Stopwatch(); stopwatch.Start(); Array.Sort(copyArr); stopwatch.Stop(); Console.WriteLine("計測時間【ArraySortAsc】: " + stopwatch.Elapsed.TotalMilliseconds + "ms"); } // Array.Sortで並び替え(降順) private static void ArraySortDesc(int[] arr) { var copyArr = new int[DataCount]; Array.Copy(arr, copyArr, arr.Length); var stopwatch = new Stopwatch(); stopwatch.Start(); Array.Sort(copyArr); Array.Reverse(copyArr); stopwatch.Stop(); Console.WriteLine("計測時間【ArraySortDesc】: " + stopwatch.Elapsed.TotalMilliseconds + "ms"); } // List.Sortで並び替え(昇順) private static void ListSortAsc(int[] arr) { var list = new List<int>(); list.AddRange(arr); var stopwatch = new Stopwatch(); stopwatch.Start(); list.Sort(); stopwatch.Stop(); Console.WriteLine("計測時間【ListSortAsc】: " + stopwatch.Elapsed.TotalMilliseconds + "ms"); } // List.Sortで並び替え(降順) private static void ListSortDesc(int[] arr) { var list = new List<int>(); list.AddRange(arr); var stopwatch = new Stopwatch(); stopwatch.Start(); list.Sort(); list.Reverse(); stopwatch.Stop(); Console.WriteLine("計測時間【ListSortDesc】: " + stopwatch.Elapsed.TotalMilliseconds + "ms"); } // Linqを使用して並び替え(昇順) private static void ListLinqSortAsc(int[] arr) { var list = new List<int>(); list.AddRange(arr); var stopwatch = new Stopwatch(); stopwatch.Start(); var sortedData = list.OrderBy(x => x).ToList(); stopwatch.Stop(); Console.WriteLine("計測時間【ListLinqSortAsc】: " + stopwatch.Elapsed.TotalMilliseconds + "ms"); } // Linqを使用して並び替え(降順) private static void ListLinqSortDesc(int[] arr) { var list = new List<int>(); list.AddRange(arr); var stopwatch = new Stopwatch(); stopwatch.Start(); var sortedData = list.OrderByDescending(x => x).ToList(); stopwatch.Stop(); Console.WriteLine("計測時間【ListLinqSortDesc】: " + stopwatch.Elapsed.TotalMilliseconds + "ms"); } // テストデータを配列形式で作成 private static int[] MakeArray() { var r = new Random(); var arr = new int[DataCount]; for (var i = 0; i < DataCount; i++) { arr[i] = r.Next(0, MaxValue); } return arr; } } } |
Listの測定結果
10回試行した結果の平均値が下記になっています。小数点以下は四捨五入しています。
計測項目 | 計測時間(ms) |
---|---|
配列をArray.Sortを使用して昇順にソート | 108 |
ListをList.Sortを使用して昇順にソート | 109 |
ListをLinqを使用して昇順にソート | 533 |
配列をArray.Sort・Array.Reverseを使用して降順にソート | 113 |
ListをList.Sort・List.Reverseを使用して降順にソート | 107 |
ListをLinqを使用して降順にソート | 540 |
上記の結果を比較してみるとLinqが遅く、それ以外はあまり結果が変わらない形になりました。
Linqを使ったものは速度が圧倒的に遅くなっていますが、これはLinqの内容を評価させるためにtoListをおこなっているため、
List化するのに時間がかかっており、ソート自体の速度にはそこまで速度差がない可能性があります。
昇順・降順単位で結果を見てみるとListの降順が昇順より速くなっていますが、これは測定誤差であると考えられます。
実際は配列の昇順・降順の結果のように降順にReverse関数が入っている分処理が遅くなると考えられます。
まとめ
ソートの速度比較という面では、Linq以外にはあまり違いがみられませんでした。
単純なデータのソートであれば、特に意識することなくSort関数を使用して問題ないかと思います。
Linqのソートを使用するのは、Listの中身がObjectである際のソートやソート順番を詳細に指定したい場合に使用する形がベストだと思います。
今回はC#のListをソートする方法としてSort関数とLinqでソートする方法を行ってみました。
この記事が少しでも皆さんのお役に立てば幸いです。