C# の HashSet と SortedSet
こんにちは。
仕事の自動化にやりがいと達成感を感じるガッくんです。
この記事の目次
背景・目的
履歴を管理したり、重複を避ける場合には HashSet か SortedSet を使うのが王道だと思います。
HashSet と SortedSet がいったいどれほどの威力なのかを確かめました。
動作環境
・Windows 7
・Visual Studio 2017
プログラム
ソースコード
重複のあるランダムな List から重複のない List を作成します。なお、 1 行目の #define のコメントを外すと、 List の値を出力する事ができるようになります。
//#define OUTPUT_VALUES
using System;
using System.Diagnostics;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.IO;
namespace speed_comparison_duplicate
{
class Program
{
static void Main(string[] args)
{
///////////////////////////////////////////////////////////////////////////////
// 重複のあるランダムな values List を作成し、
// values List から重複のない List を作成する。
///////////////////////////////////////////////////////////////////////////////
// 重複のあるランダムな values List の作成
// ある数の配列を用意する。
// 重複がない様に連番で初期化する。
// 乱数を使って配列の値を入れ替えて並び順をランダムにする。
// ランダムに並べ替えた配列を List に 2 回代入する。
///////////////////////////////////////////////////////////////////////////////
// values List から重複のない List の作成
// values List を調べて追加されたことのない要素で有れば、
// List に要素を追加する。
// パターンＡ
// Contains メソッドで values List の有無を調べる
// パターンＢ
// BinarySearch メソッドで values List の有無を調べる
// パターンＣ
// HashSet で重複のない List を作成する
// パターンＤ
// SortedSet で重複のない List を作成する
///////////////////////////////////////////////////////////////////////////////
///////////////////////////////////////////////////////////////////////////////
// 重複のあるランダムな values List の作成
// ある数の配列を用意する。
// 重複がない様に連番で初期化する。
// 乱数を使って配列の値を入れ替えて並び順をランダムにする。
///////////////////////////////////////////////////////////////////////////////
Stopwatch sw = new Stopwatch();
sw.Reset();
sw.Start();
// cntArray 個の配列作成
int cntArray = 30000;
int[] values = new int[cntArray];
// 配列の初期化
int startValue = 523;
for (int i = 0; i < values.Length; i++)
{
values[i] = startValue + i;
}
// 乱数発生器作成する
Random r = new Random();
// 配列を cntSwap 回シャッフルする
int cntSwap = cntArray;
for (int i = 0; i < cntSwap; i++)
{
// 入れ替える配列インデックスをランダムに選定する
int j = r.Next(0, values.Length);
// 配列の値の入れ替え
int tmpJ = values[j];
values[j] = values[i];
values[i] = tmpJ;
}
// cntDuplicate 個の重複のあるランダムな values List の作成
int cntDuplicate = 2;
List values_List = new List();
for (int i = 0; i < cntDuplicate; i++)
{
for (int j = 0; j < values.Length; j++)
{
values_List.Add(values[j]);
}
}
sw.Stop();
Console.WriteLine("配列作成終了");
string filepath = "C:\\Users\\UserName\\Desktop\\log.txt";
StreamWriter w = new StreamWriter(filepath, false, Encoding.GetEncoding("shift_jis"));
TimeSpan ts = sw.Elapsed;
w.Write("* 値のランダムな values List の個数：");
w.WriteLine(values_List.Count);
w.Write(" 重複数：");
w.WriteLine(cntDuplicate);
w.Write("値のランダムな values List の作成時間：");
w.WriteLine($" {ts.Hours}時間 {ts.Minutes}分 {ts.Seconds}秒 {ts.Milliseconds}ミリ秒");
#if (OUTPUT_VALUES)
w.WriteLine(string.Format("{0,10}", "Index") + ":" + string.Format("{0,20}", "Values"));
for (int i = 0; i < values_List.Count; i++)
{
w.WriteLine(string.Format("{0,10}", i) + ":" + string.Format("{0,20}", values_List[i]));
}
#endif
///////////////////////////////////////////////////////////////////////////////
// values List の空ループの時間調査
///////////////////////////////////////////////////////////////////////////////
sw.Reset();
sw.Start();
for (int i = 0; i < values_List.Count; i++)
{
}
sw.Stop();
Console.WriteLine("空ループ終了");
ts = sw.Elapsed;
w.WriteLine("");
w.Write("* values List の空ループ時間：");
w.WriteLine($" {ts.Hours}時間 {ts.Minutes}分 {ts.Seconds}秒 {ts.Milliseconds}ミリ秒");
///////////////////////////////////////////////////////////////////////////////
// values List から重複のない List の作成
// values List を調べて追加されたことのない要素で有れば、
// List に要素を追加する。
// パターンＡ
// Contains メソッドで values List の有無を調べる
///////////////////////////////////////////////////////////////////////////////
sw.Reset();
sw.Start();
List list1 = new List();
for(int i = 0; i < values_List.Count; i++)
{
if (!list1.Contains(values_List[i]))
{
list1.Add(values_List[i]);
}
}
sw.Stop();
Console.WriteLine(" Contains 終了");
ts = sw.Elapsed;
w.WriteLine("");
w.Write("* 重複のない list1 の個数：");
w.WriteLine(list1.Count);
w.Write(" 重複のない list1 の作成時間：");
w.WriteLine($" {ts.Hours}時間 {ts.Minutes}分 {ts.Seconds}秒 {ts.Milliseconds}ミリ秒");
#if (OUTPUT_VALUES)
w.WriteLine(string.Format("{0,10}", "Index") + ":" + string.Format("{0,20}", "Values"));
for (int i = 0; i < list1.Count; i++)
{
w.WriteLine(string.Format("{0,10}", i) + ":" + string.Format("{0,20}", list1[i]));
}
#endif
///////////////////////////////////////////////////////////////////////////////
// values List から重複のない List の作成
// values List を調べて追加されたことのない要素で有れば、
// List に要素を追加する。
// パターンＢ
// BinarySearch メソッドで values List の有無を調べる
///////////////////////////////////////////////////////////////////////////////
sw.Reset();
sw.Start();
List list2 = new List();
for (int i = 0; i < values_List.Count; i++)
{
int idx = list2.BinarySearch(values_List[i]);
if (idx < 0)
{
list2.Add(values_List[i]);
list2.Sort();
}
}
sw.Stop();
Console.WriteLine(" BinarySearch 終了");
ts = sw.Elapsed;
w.WriteLine("");
w.Write("* 重複のない list2 の個数：");
w.WriteLine(list1.Count);
w.Write(" 重複のない list2 の作成時間：");
w.WriteLine($" {ts.Hours}時間 {ts.Minutes}分 {ts.Seconds}秒 {ts.Milliseconds}ミリ秒");
#if (OUTPUT_VALUES)
w.WriteLine(string.Format("{0,10}", "Index") + ":" + string.Format("{0,20}", "Values"));
for (int i = 0; i < list2.Count; i++)
{
w.WriteLine(string.Format("{0,10}", i) + ":" + string.Format("{0,20}", list2[i]));
}
#endif
///////////////////////////////////////////////////////////////////////////////
// values List から重複のない List の作成
// values List を調べて追加されたことのない要素で有れば、
// List に要素を追加する。
// パターンＣ
// HashSet で重複のない List を作成する
///////////////////////////////////////////////////////////////////////////////
sw.Reset();
sw.Start();
HashSet hash = new HashSet();
for (int i = 0; i < values_List.Count; i++)
{
hash.Add(values_List[i]);
}
List hashList = hash.ToList();
sw.Stop();
Console.WriteLine(" HashSet 終了");
ts = sw.Elapsed;
w.WriteLine("");
w.Write("* 重複のない hash の個数：");
w.WriteLine(hash.Count);
w.Write(" 重複のない hash の作成時間：");
w.WriteLine($" {ts.Hours}時間 {ts.Minutes}分 {ts.Seconds}秒 {ts.Milliseconds}ミリ秒");
#if (OUTPUT_VALUES)
w.WriteLine(string.Format("{0,10}", "Index") + ":" + string.Format("{0,20}", "Values"));
for (int i = 0; i < hashList.Count; i++)
{
w.WriteLine(string.Format("{0,10}", i) + ":" + string.Format("{0,20}", hashList[i]));
}
#endif
///////////////////////////////////////////////////////////////////////////////
// values List から重複のない List の作成
// values List を調べて追加されたことのない要素で有れば、
// List に要素を追加する。
// パターンＤ
// SortedSet で重複のない List を作成する
///////////////////////////////////////////////////////////////////////////////
sw.Reset();
sw.Start();
SortedSet sset = new SortedSet();
for (int i = 0; i < values_List.Count; i++)
{
sset.Add(values_List[i]);
}
List ssetList = sset.ToList();
sw.Stop();
Console.WriteLine(" SortedSet 終了");
ts = sw.Elapsed;
w.WriteLine("");
w.Write("* 重複のない sset の個数：");
w.WriteLine(hash.Count);
w.Write(" 重複のない sset の作成時間：");
w.WriteLine($" {ts.Hours}時間 {ts.Minutes}分 {ts.Seconds}秒 {ts.Milliseconds}ミリ秒");
#if (OUTPUT_VALUES)
w.WriteLine(string.Format("{0,10}", "Index") + ":" + string.Format("{0,20}", "Values"));
for (int i = 0; i < ssetList.Count; i++)
{
w.WriteLine(string.Format("{0,10}", i) + ":" + string.Format("{0,20}", ssetList[i]));
}
#endif
///////////////////////////////////////////////////////////////////////////////
// 終了処理
///////////////////////////////////////////////////////////////////////////////
w.Close();
Console.WriteLine("");
Console.Write("何かキーを押して下さい。");
Console.ReadKey();
}
}
}
結果
ちょっと見づらいですが、結果です。
テキストエディタにコピペしてもらうと、もっと見やすくなると思います。
* 値のランダムな values List の個数：60000
重複数：2
値のランダムな values List の作成時間： 0時間 0分 0秒 1ミリ秒
* values List の空ループ時間： 0時間 0分 0秒 0ミリ秒
* 重複のない list1 の個数：30000
重複のない list1 の作成時間： 0時間 0分 2秒 619ミリ秒
* 重複のない list2 の個数：30000
重複のない list2 の作成時間： 0時間 0分 8秒 441ミリ秒
* 重複のない hash の個数：30000
重複のない hash の作成時間： 0時間 0分 0秒 1ミリ秒
* 重複のない sset の個数：30000
重複のない sset の作成時間： 0時間 0分 0秒 17ミリ秒
コメント
HashSet と SortedSet の威力が絶大でした。
HashSet と SortedSet では HashSet が圧倒的に早かったです。
SortedSet はソートしてる分遅かったのでしょうか。
以上
