[C#] 開発メモ クラス検索のパフォーマンスについて

Uncategorized

現在開発中のC#のプロジェクトで静的フィールドのメモリ内に
リストを持ち、必要に応じてメモリのリストよりクラスを検索して
返しているロジックがあります。

この検索ロジックですが、List<T>で持っており、LINQのwhere句で
検索を行っています。

もし遅いようであれば、リストをSortedListを使うなり、ListのBinarySearch
を利用することで対応しようと思っていたのですが、せっかくなので
多めのテストデータを使ってパフォーマンステストを実施してみました。

ここでデータは予めソートされていることを前提とします。

先に比較結果を記述します。

[リストへ100,000件追加]
List型(1回目)：0.234秒
List型(2回目)：0.234秒
List型(3回目)：0.218秒
SortedList型(1回目)：1.093秒
SortedList型(2回目)：1.125秒
SortedList型(3回目)：1.171秒

[100,000件から1件のレコードを1,000回検索]
List型(LINQのwhere句)(1回目)：51.312秒
List型(LINQのwhere句)(2回目)：51.171秒
List型(LINQのwhere句)(3回目)：51.093秒
List型(BinarySearch)(1回目)：0.015秒
List型(BinarySearch)(2回目)：0.015秒
List型(BinarySearch)(3回目)：0.015秒
SortedList型(1回目)：0.015秒
SortedList型(2回目)：0.015秒
SortedList型(3回目)：0.015秒

この結果を見る限り、利用するならリストへの追加、検索の
ともに速いList型のBinarySearchがよさそうです。

ただ、ここでは1レコードを取得するテストを行いましたが
実際のプロジェクトでは範囲検索でリストを取得する処理も
行っているので、若干工夫が必要になりそうです。

ちなみにSortedList型でLINQを使って同じように検索すると
53.062秒と遅くなりました。LINQを使う場合はSortedListにしても
変わりはないようです・・・

参考までにテストの際に使用したソースを以下に記述します。

[検索するクラス]
public class Table
{
public String Key1 { get; set; }
public String Key2 { get; set; }
public String Key3 { get; set; }
public String Key4 { get; set; }
public String Key5 { get; set; }
public String Value { get; set; }
}

[比較用クラス]
public class TableCompare : IComparer<Table>
{
public int Compare(Table x, Table y)
{
if (x.Key1 != y.Key1)
{
return String.Compare(x.Key1, y.Key1);
}
if (x.Key2 != y.Key2)
{
return String.Compare(x.Key2, y.Key2);
}
if (x.Key3 != y.Key3)
{
return String.Compare(x.Key3, y.Key3);
}
if (x.Key4 != y.Key4)
{
return String.Compare(x.Key4, y.Key4);
}
return String.Compare(x.Key5, y.Key5);
}
}

リストへの追加処理

[List型]
List<Table> lstTable = new List<Table>();
for (Int32 i = 0; i < 100000; i++)
{
Table table = new Table();
table.Key1 = “1”;
table.Key2 = “2”;
table.Key3 = “3”;
table.Key4 = “4”;
table.Key5 = String.Format(“{0:00000}”, i);
table.Value = i.ToString();
lstTable.Add(table);
}

[SortedList型]
SortedList<Table, Table> slstTable = new SortedList<Table, Table>(new TableCompare());
for (Int32 i = 0; i < 100000; i++)
{
Table table = new Table();
table.Key1 = “1”;
table.Key2 = “2”;
table.Key3 = “3”;
table.Key4 = “4”;
table.Key5 = String.Format(“{0:00000}”, i);
table.Value = i.ToString();
slstTable.Add(table, table);
}

検索の比較

[List型(LINQのwhere句)]
for (Int32 i = 0; i < 1000; i++)
{
Random rm = new Random(i);
Int32 key = rm.Next(100000);

Table table = lstTable.Where(m =>
m.Key1 == “1”
&& m.Key2 == “2”
&& m.Key3 == “3”
&& m.Key4 == “4”
&& m.Key5 == String.Format(“{0:00000}”, key))
.FirstOrDefault();
}

[List型(BinarySearch)]
for (Int32 i = 0; i < 1000; i++)
{
Random rm = new Random(i);
Int32 key = rm.Next(100000);

Table tableKey = new Table();
tableKey.Key1 = “1”;
tableKey.Key2 = “2”;
tableKey.Key3 = “3”;
tableKey.Key4 = “4”;
tableKey.Key5 = String.Format(“{0:00000}”, key);

Int32 index = lstTable.BinarySearch(tableKey, new TableCompare());
Table table = lstTable[index];
}

[SortedList型]
for (Int32 i = 0; i < 1000; i++)
{
Random rm = new Random(i);
Int32 key = rm.Next(100000);

Table tableKey = new Table();
tableKey.Key1 = “1”;
tableKey.Key2 = “2”;
tableKey.Key3 = “3”;
tableKey.Key4 = “4”;
tableKey.Key5 = String.Format(“{0:00000}”, key);

Table table = slstTable[tableKey];
}