以前、 επιστημηさんが、「Hashすげー」
で、HashSetの早さを報告されています。
C#でも 3.5から導入されいて、重複要素の排除などに重宝しています。
C#3.0以前で同様のことをするには Dictionary<object,object> で行えます。 KeyとValueに同値をセットすれば使えますが、Vの部分に冗長性が出ます。
速度コストが気になり試行して見ました。Value部の冗長性がないので、「コスト安であろう」 と勝手に期待してましたが...
▼▼▼テスト結果▼▼▼ AMD64*2:4600+ 2.4G
----------------------------------- mSec mSec
▼回数: 1▼ dict<int,int> : 0 追加数[ 1] Hash<int> : 38 追加数[ 1]
▼回数: 10▼ dict<int,int> : 0 追加数[ 10] Hash<int> : 1 追加数[ 10]
▼回数: 100▼ dict<int,int> : 0 追加数[ 87] Hash<int> : 0 追加数[ 87]
▼回数: 1000▼ dict<int,int> : 0 追加数[428] Hash<int> : 0 追加数[428]
▼回数: 10000▼ dict<int,int> : 2 追加数[499] Hash<int> : 2 追加数[499]
▼回数: 100000▼ dict<int,int> : 20 追加数[499] Hash<int> : 16 追加数[499]
▼回数: 1000000▼ dict<int,int> : 106 追加数[499] Hash<int> : 88 追加数[499]
▼回数: 10000000▼ dict<int,int> : 862 追加数[499] Hash<int> : 948 追加数[499]
▼回数:100000000▼ dict<int,int> :8653 追加数[499] Hash<int> :9196 追加数[499]
僅かですが、「Dictionary<> のほうが早い」場合もありますが、有意差はないようです。
内部の実装がどのようになっているかは、知らないのでずか、同じツリー構造で格納しているのなら、差はもっと小さいと思いますが違うのかな。
これくらの差なら、HashSetを使う価値はありますね。
NameValueCollectionクラスという、Dictionaryの同一キーに対する要素を複数保持できるモノがありますが、知られることなく埋没されていますね。
Dictionary< key , List<object>> で、同じ効果を得られるので、独自性が薄かったとも言えますが。
SortedDictionaryゃSortedList というのもあります。HashでKeyを格納しているので、Hash自体にSort機能は保有していると思うのですが、流用できなかったのでしょうか。
標準で付いているコレクションの種類が増加するのは、進歩なのですが、活用できずに、埋没しているのも散見するので、複雑な気分です。
テストソース
//private int 元ネタ個数 = 1000000000; // 90秒近く
private Dictionary<int, int> 元ネタDICT = new Dictionary<int, int>();
private HashSet<int> 元ネタHash = new HashSet<int>();
private string Report = "";
private void btn_開始_Click(object sender, EventArgs e)
{
for (int 回数 = 1; 回数 < 1000000000; 回数 *= 10)
{
測定(回数);
}
MessageBox.Show(Report);
}
private void 測定(int 回数)
{
Report +=Environment.NewLine+"▼回数:"+回数+ "▼";
Stopwatch sw = new Stopwatch();
//元ネタ作成
{
Random rnd = new Random(0);
sw.Start();
for (int i = 0; i < 回数; i++)
{
int j = (rnd.Next() * 100 ) % 1000;
if (!元ネタDICT.ContainsKey(j))
{
元ネタDICT.Add(j, j);
}
else
{
}
}
Report += Environment.NewLine + " dict<int,int> :" + sw.ElapsedMilliseconds.ToString() + " 追加数[" + 元ネタDICT.Count.ToString() + "]";
}
{
Random rnd = new Random(0);
sw.Reset();
sw.Start();
for (int i = 0; i < 回数; i++)
{
int j = (rnd.Next() * 100) % 1000;
if (!元ネタHash.Contains(j))
{
元ネタHash.Add(j);
}
}
Report += Environment.NewLine + " Hash<int> :" + sw.ElapsedMilliseconds.ToString() + " 追加数[" + 元ネタHash.Count.ToString() + "]";
}
}