C#でListの要素検索の速度比較

はじめに

業務アプリの実装で、秒毎のデータを収集して後でグラフを書くってのを作る時に、どういったデータ構造にすれば良いのかが社内で話題になり、その時に要素検索の速度が大事だよね～ってなったけど、実際速度ってどうなの？って事で調べてみた。

環境

C#を使用しています。.net6環境で動作確認してます。

データ構造

実際のデータ構造に似せたかったので、時間とdouble型のデータ10個を持つclassを使用する。プロパティの名前は適当。

class Data
    {
        public DateTime time { get; set; }
        public double date01 { get; set; }
        public double date02 { get; set; }
        public double date03 { get; set; }
        public double date04 { get; set; }
        public double date05 { get; set; }
        public double date06 { get; set; }
        public double date07 { get; set; }
        public double date08 { get; set; }
        public double date09 { get; set; }
        public double date10 { get; set; }
    }

いろんなList型を作成

処理時間を比較するために、いろんな型を使用した。

var dataList = new List<Data>();
var dataDict = new Dictionary<DateTime,Data>();
var sortList = new SortedList<DateTime,Data>();
var sortDict = new SortedDictionary<DateTime,Data>();
var hashTable = new Hashtable(); 

データの作成

上記のデータ構造に、適当なデータを入れる。時間は、0時0分0秒から23時59分59秒までを想定、各プロパティには乱数を代入した。

var StartTime = new DateTime(2021,12,24,0,0,0);     //開始時間
Random rad = new Random();                          //乱数の作成
for(var i=0;i<60*60*24;i++)                         //24時間分
{
    data.Add(new Data(){
        time=startTime,
        date01=rad.NextDouble(),
        date02=rad.NextDouble(),
        date03=rad.NextDouble(),
        date04=rad.NextDouble(),
        date05=rad.NextDouble(),
        date06=rad.NextDouble(),
        date07=rad.NextDouble(),
        date08=rad.NextDouble(),
        date09=rad.NextDouble(),
        date10=rad.NextDouble(),
    });
    StartTime = startTime.AddSeconds(1);
}

他の型も同じように代入。

要素の検索

前もって、検索する日時をリストに作成しておく。検索日時も乱数で決めて、とりあえず10000個ぐらい作った。

List<DateTime> ansList = new List<DateTime>();
for(var i=0;i<10000;i++)
{
    ansList.Add(new DateTime(2021,12,24,rad.Next(0,23),rad.Next(0,59),radNext(0,59)));
}

10000個分の時間を使って、Listから検索を行い、時間を計測した。

double total = 0;
var sp = new System.Diagnostics.Stopwatch();

sp.Start();
for(var i=0;i<10000;i++)
{
    var value = data.FirstOrDefault(n=>n.time == ansList[i]);
    total += value == null ? 0 : (double)(value.date01);
}
sp.Stop();
Console.WriteLine($"List型 {sp.Elapsed.Minutes}[分]{sp.Elapsed.Seconds}[s]{sp.Elapsed.Milliseconds}[ms]");    

こんな感じで、定義した分全部の時間を計測してみた

結果

型	時間
List<Data>	6841[ms]
Dictionary<DateTime,Data>	3[ms]
SortedList<DateTime,Data>	3[ms]
SortedDictionary<DateTime,Data>	7[ms]
Hashtable	2[ms]

という事でdictionaly型やsorted～型が非常に速い様です。dictionary型には、時間データを昇順で代入しているので、sortedと変わらない結果になったのかもしれません。実際のアプリでもこういった代入方法なので、ここでは問題にしないという事で。
HashTableも早いですが、最近はジェネリックを使用しましょう、ってことで非推奨みたいなので、これは止めておきます。