2018.04.25
C#

【C#】Listのソート速度比較

お久しぶりです、エンジニアの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を使用して降順にソート

テストコード

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;
        }
    }
}

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でソートする方法を行ってみました。
この記事が少しでも皆さんのお役に立てば幸いです。

【Vue.jsでSPAへの移行】コンポーネントを使ってみよう

PandasをDaskで簡単に並列処理して高速化しよう

【C#】Listのソート速度比較

測定までの流れ

測定環境

対象データ

測定対象

テストコード

Listの測定結果

まとめ

最近の記事

レイアウト解析

ChatGPTを用いた画像異常検知

クォータニオンと回転行列の関係

OpenCVで深層学習

OpenCVのcv::Matに関する小ネタ集

テンソルネットワークの入り口（その2）

C#のnull許容参照型を使う

【C#】文字列分割の速度比較

Blazor WASMで作ったチャットアプリをMVVMにしてみた

【C#】ファイル読み取り速度比較

Blazor WebAssembly で MVVM を実現する(第1回)

【C#】【Linq】データ取得速度比較

Google Vision APIでOCR

アーカイブ

カテゴリー