.net - HashSetとリストのパフォーマンス

Question

HashSet<T>ジェネリッククラスの検索パフォーマンスがジェネリッククラスよりも高いことは明らかですList<T>。ハッシュベースのキーをList<T>クラスの線形アプローチと比較するだけです。

ただし、ハッシュキーの計算自体にCPUサイクルがかかる場合があるため、少量のアイテムの場合、線形検索がの実際の代替手段になる可能性がありHashSet<T>ます。

私の質問：損益分岐点はどこにありますか？

List<T>シナリオを単純化するために（そして公平を期すために）、クラスが要素のEquals()メソッドを使用してアイテムを識別すると仮定しましょう。

score 930 · Accepted Answer

多くの人は、速度が実際に懸念されるサイズに到達すると、HashSet<T>常にList<T>.

List<T>平均して 5 つのアイテムしか持たないがあるとします。多数のサイクルにわたって、各サイクルで 1 つの項目が追加または削除される場合は、List<T>.

私は自分のマシンでこれのテストを行いましたList<T>. 短い文字列のリストでは、サイズ 5 以降、サイズ 20 以降のオブジェクトでは利点がなくなりました。

1 item LIST strs time: 617ms
1 item HASHSET strs time: 1332ms

2 item LIST strs time: 781ms
2 item HASHSET strs time: 1354ms

3 item LIST strs time: 950ms
3 item HASHSET strs time: 1405ms

4 item LIST strs time: 1126ms
4 item HASHSET strs time: 1441ms

5 item LIST strs time: 1370ms
5 item HASHSET strs time: 1452ms

6 item LIST strs time: 1481ms
6 item HASHSET strs time: 1418ms

7 item LIST strs time: 1581ms
7 item HASHSET strs time: 1464ms

8 item LIST strs time: 1726ms
8 item HASHSET strs time: 1398ms

9 item LIST strs time: 1901ms
9 item HASHSET strs time: 1433ms

1 item LIST objs time: 614ms
1 item HASHSET objs time: 1993ms

4 item LIST objs time: 837ms
4 item HASHSET objs time: 1914ms

7 item LIST objs time: 1070ms
7 item HASHSET objs time: 1900ms

10 item LIST objs time: 1267ms
10 item HASHSET objs time: 1904ms

13 item LIST objs time: 1494ms
13 item HASHSET objs time: 1893ms

16 item LIST objs time: 1695ms
16 item HASHSET objs time: 1879ms

19 item LIST objs time: 1902ms
19 item HASHSET objs time: 1950ms

22 item LIST objs time: 2136ms
22 item HASHSET objs time: 1893ms

25 item LIST objs time: 2357ms
25 item HASHSET objs time: 1826ms

28 item LIST objs time: 2555ms
28 item HASHSET objs time: 1865ms

31 item LIST objs time: 2755ms
31 item HASHSET objs time: 1963ms

34 item LIST objs time: 3025ms
34 item HASHSET objs time: 1874ms

37 item LIST objs time: 3195ms
37 item HASHSET objs time: 1958ms

40 item LIST objs time: 3401ms
40 item HASHSET objs time: 1855ms

43 item LIST objs time: 3618ms
43 item HASHSET objs time: 1869ms

46 item LIST objs time: 3883ms
46 item HASHSET objs time: 2046ms

49 item LIST objs time: 4218ms
49 item HASHSET objs time: 1873ms

グラフとして表示されたデータは次のとおりです。

ここに画像の説明を入力

コードは次のとおりです。

static void Main(string[] args)
{
    int times = 10000000;


    for (int listSize = 1; listSize < 10; listSize++)
    {
        List<string> list = new List<string>();
        HashSet<string> hashset = new HashSet<string>();

        for (int i = 0; i < listSize; i++)
        {
            list.Add("string" + i.ToString());
            hashset.Add("string" + i.ToString());
        }

        Stopwatch timer = new Stopwatch();
        timer.Start();
        for (int i = 0; i < times; i++)
        {
            list.Remove("string0");
            list.Add("string0");
        }
        timer.Stop();
        Console.WriteLine(listSize.ToString() + " item LIST strs time: " + timer.ElapsedMilliseconds.ToString() + "ms");


        timer = new Stopwatch();
        timer.Start();
        for (int i = 0; i < times; i++)
        {
            hashset.Remove("string0");
            hashset.Add("string0");
        }
        timer.Stop();
        Console.WriteLine(listSize.ToString() + " item HASHSET strs time: " + timer.ElapsedMilliseconds.ToString() + "ms");
        Console.WriteLine();
    }


    for (int listSize = 1; listSize < 50; listSize+=3)
    {
        List<object> list = new List<object>();
        HashSet<object> hashset = new HashSet<object>();

        for (int i = 0; i < listSize; i++)
        {
            list.Add(new object());
            hashset.Add(new object());
        }

        object objToAddRem = list[0];

        Stopwatch timer = new Stopwatch();
        timer.Start();
        for (int i = 0; i < times; i++)
        {
            list.Remove(objToAddRem);
            list.Add(objToAddRem);
        }
        timer.Stop();
        Console.WriteLine(listSize.ToString() + " item LIST objs time: " + timer.ElapsedMilliseconds.ToString() + "ms");



        timer = new Stopwatch();
        timer.Start();
        for (int i = 0; i < times; i++)
        {
            hashset.Remove(objToAddRem);
            hashset.Add(objToAddRem);
        }
        timer.Stop();
        Console.WriteLine(listSize.ToString() + " item HASHSET objs time: " + timer.ElapsedMilliseconds.ToString() + "ms");
        Console.WriteLine();
    }

    Console.ReadLine();
}

score 93 · Accepted Answer

異なる動作をする 2 つの構造のパフォーマンスを比較することは、本質的に無意味です。意図を伝える構造を使用します。List<T>重複がなく、反復順序が重要ではなく、に匹敵すると言っても、耐障害性が比較的低いため、HashSet<T>使用するのには適していません。List<T>

そうは言っても、パフォーマンスの他の側面を調べます。

+------------+--------+-------------+-----------+----------+----------+-----------+
| Collection | Random | Containment | Insertion | Addition |  Removal | Memory    |
|            | access |             |           |          |          |           |
+------------+--------+-------------+-----------+----------+----------+-----------+
| List<T>    | O(1)   | O(n)        | O(n)      | O(1)*    | O(n)     | Lesser    |
| HashSet<T> | O(n)   | O(1)        | n/a       | O(1)     | O(1)     | Greater** |
+------------+--------+-------------+-----------+----------+----------+-----------+

どちらの場合も足し算は O(1) ですが、ハッシュコードを格納する前に事前計算するコストがかかるため、HashSet では比較的遅くなります。
HashSet の優れたスケーラビリティには、メモリコストがあります。すべてのエントリは、ハッシュコードとともに新しいオブジェクトとして保存されます。この記事はあなたにアイデアを与えるかもしれません。

score 77 · Accepted Answer

あなたはこれを間違って見ています。はい、リストの線形検索は、少数のアイテムの HashSet に勝ります。ただし、パフォーマンスの違いは通常、それほど小さいコレクションでは問題になりません。一般に、気にしなければならないのは大規模なコレクションであり、それが Big-O の観点から考える場所です。ただし、HashSet パフォーマンスの実際のボトルネックを測定した場合は、ハイブリッドリスト/HashSet の作成を試みることができますが、SO について質問するのではなく、多くの経験的なパフォーマンステストを実施することでそれを行います。

score 56 · Accepted Answer

HashSet<> または List<> のどちらを使用するかは、コレクションへのアクセス方法に依存します。アイテムの順序を保証する必要がある場合は、List を使用します。そうでない場合は、HashSet を使用してください。ハッシュアルゴリズムとオブジェクトの実装については Microsoft に任せてください。

HashSet は、コレクションを列挙する必要なくアイテムにアクセスします ( O(1)の複雑さまたはそれに近い)。List は順序を保証するため、HashSet とは異なり、いくつかのアイテムを列挙する必要があります (O(n) の複雑さ)。

score 35 · Accepted Answer

以前の回答を説明するために、さまざまなシナリオのベンチマークをいくつか試してみようと思っただけです。

いくつか（12〜20）の小さな文字列（5〜10文字の長さ）
多くの（〜10K）小さな文字列
いくつかの長い文字列（200〜1000文字の長さ）
多くの（〜5K）長い文字列
いくつかの整数
多くの（〜10K）整数

そして、シナリオごとに、表示される値を検索します。

リストの先頭（「開始」、インデックス0）
リストの先頭近く（「初期」、インデックス1）
リストの真ん中（「真ん中」、インデックス数/ 2）
リストの終わり近く（「遅い」、インデックス数-2）
リストの最後（「終了」、インデックス数-1）

各シナリオの前に、ランダムなサイズのランダムな文字列のリストを生成し、各リストをハッシュセットにフィードしました。各シナリオは10,000回実行されましたが、基本的には次のとおりです。

（テスト擬似コード）

stopwatch.start
for X times
    exists = list.Contains(lookup);
stopwatch.stop

stopwatch.start
for X times
    exists = hashset.Contains(lookup);
stopwatch.stop

サンプル出力

Windows 7、12GB RAM、64ビット、Xeon2.8GHzでテスト済み

---------- Testing few small strings ------------
Sample items: (16 total)
vgnwaloqf diwfpxbv tdcdc grfch icsjwk
...

Benchmarks:
1: hashset: late -- 100.00 % -- [Elapsed: 0.0018398 sec]
2: hashset: middle -- 104.19 % -- [Elapsed: 0.0019169 sec]
3: hashset: end -- 108.21 % -- [Elapsed: 0.0019908 sec]
4: list: early -- 144.62 % -- [Elapsed: 0.0026607 sec]
5: hashset: start -- 174.32 % -- [Elapsed: 0.0032071 sec]
6: list: middle -- 187.72 % -- [Elapsed: 0.0034536 sec]
7: list: late -- 192.66 % -- [Elapsed: 0.0035446 sec]
8: list: end -- 215.42 % -- [Elapsed: 0.0039633 sec]
9: hashset: early -- 217.95 % -- [Elapsed: 0.0040098 sec]
10: list: start -- 576.55 % -- [Elapsed: 0.0106073 sec]


---------- Testing many small strings ------------
Sample items: (10346 total)
dmnowa yshtrxorj vthjk okrxegip vwpoltck
...

Benchmarks:
1: hashset: end -- 100.00 % -- [Elapsed: 0.0017443 sec]
2: hashset: late -- 102.91 % -- [Elapsed: 0.0017951 sec]
3: hashset: middle -- 106.23 % -- [Elapsed: 0.0018529 sec]
4: list: early -- 107.49 % -- [Elapsed: 0.0018749 sec]
5: list: start -- 126.23 % -- [Elapsed: 0.0022018 sec]
6: hashset: early -- 134.11 % -- [Elapsed: 0.0023393 sec]
7: hashset: start -- 372.09 % -- [Elapsed: 0.0064903 sec]
8: list: middle -- 48,593.79 % -- [Elapsed: 0.8476214 sec]
9: list: end -- 99,020.73 % -- [Elapsed: 1.7272186 sec]
10: list: late -- 99,089.36 % -- [Elapsed: 1.7284155 sec]


---------- Testing few long strings ------------
Sample items: (19 total)
hidfymjyjtffcjmlcaoivbylakmqgoiowbgxpyhnrreodxyleehkhsofjqenyrrtlphbcnvdrbqdvji...
...

Benchmarks:
1: list: early -- 100.00 % -- [Elapsed: 0.0018266 sec]
2: list: start -- 115.76 % -- [Elapsed: 0.0021144 sec]
3: list: middle -- 143.44 % -- [Elapsed: 0.0026201 sec]
4: list: late -- 190.05 % -- [Elapsed: 0.0034715 sec]
5: list: end -- 193.78 % -- [Elapsed: 0.0035395 sec]
6: hashset: early -- 215.00 % -- [Elapsed: 0.0039271 sec]
7: hashset: end -- 248.47 % -- [Elapsed: 0.0045386 sec]
8: hashset: start -- 298.04 % -- [Elapsed: 0.005444 sec]
9: hashset: middle -- 325.63 % -- [Elapsed: 0.005948 sec]
10: hashset: late -- 431.62 % -- [Elapsed: 0.0078839 sec]


---------- Testing many long strings ------------
Sample items: (5000 total)
yrpjccgxjbketcpmnvyqvghhlnjblhgimybdygumtijtrwaromwrajlsjhxoselbucqualmhbmwnvnpnm
...

Benchmarks:
1: list: early -- 100.00 % -- [Elapsed: 0.0016211 sec]
2: list: start -- 132.73 % -- [Elapsed: 0.0021517 sec]
3: hashset: start -- 231.26 % -- [Elapsed: 0.003749 sec]
4: hashset: end -- 368.74 % -- [Elapsed: 0.0059776 sec]
5: hashset: middle -- 385.50 % -- [Elapsed: 0.0062493 sec]
6: hashset: late -- 406.23 % -- [Elapsed: 0.0065854 sec]
7: hashset: early -- 421.34 % -- [Elapsed: 0.0068304 sec]
8: list: middle -- 18,619.12 % -- [Elapsed: 0.3018345 sec]
9: list: end -- 40,942.82 % -- [Elapsed: 0.663724 sec]
10: list: late -- 41,188.19 % -- [Elapsed: 0.6677017 sec]


---------- Testing few ints ------------
Sample items: (16 total)
7266092 60668895 159021363 216428460 28007724
...

Benchmarks:
1: hashset: early -- 100.00 % -- [Elapsed: 0.0016211 sec]
2: hashset: end -- 100.45 % -- [Elapsed: 0.0016284 sec]
3: list: early -- 101.83 % -- [Elapsed: 0.0016507 sec]
4: hashset: late -- 108.95 % -- [Elapsed: 0.0017662 sec]
5: hashset: middle -- 112.29 % -- [Elapsed: 0.0018204 sec]
6: hashset: start -- 120.33 % -- [Elapsed: 0.0019506 sec]
7: list: late -- 134.45 % -- [Elapsed: 0.0021795 sec]
8: list: start -- 136.43 % -- [Elapsed: 0.0022117 sec]
9: list: end -- 169.77 % -- [Elapsed: 0.0027522 sec]
10: list: middle -- 237.94 % -- [Elapsed: 0.0038573 sec]


---------- Testing many ints ------------
Sample items: (10357 total)
370826556 569127161 101235820 792075135 270823009
...

Benchmarks:
1: list: early -- 100.00 % -- [Elapsed: 0.0015132 sec]
2: hashset: end -- 101.79 % -- [Elapsed: 0.0015403 sec]
3: hashset: early -- 102.08 % -- [Elapsed: 0.0015446 sec]
4: hashset: middle -- 103.21 % -- [Elapsed: 0.0015618 sec]
5: hashset: late -- 104.26 % -- [Elapsed: 0.0015776 sec]
6: list: start -- 126.78 % -- [Elapsed: 0.0019184 sec]
7: hashset: start -- 130.91 % -- [Elapsed: 0.0019809 sec]
8: list: middle -- 16,497.89 % -- [Elapsed: 0.2496461 sec]
9: list: end -- 32,715.52 % -- [Elapsed: 0.4950512 sec]
10: list: late -- 33,698.87 % -- [Elapsed: 0.5099313 sec]

score 11 · Accepted Answer

損益分岐点は、ハッシュを計算するコストに依存します。ハッシュ計算は些細なことでも、そうでないこともあります... :-) System.Collections.Specialized.HybridDictionaryクラスが常にあり、損益分岐点について心配する必要がなくなります。

score 6 · Accepted Answer

答えは、いつものように、「場合による」です。タグから、C# について話していると思います。

あなたの最善の策は、決定することです

データのセット
使用要件

いくつかのテストケースを書きます。

また、リストをどのように並べ替えるか (並べ替える場合)、どのような種類の比較を行う必要があるか、リスト内の特定のオブジェクトの「比較」操作にかかる時間、さらには、コレクション。

一般に、選択するのに最適なものは、作業しているデータのサイズではなく、データへのアクセス方法に基づいて決定されます。特定の文字列またはその他のデータに関連付けられた各データがありますか? ハッシュベースのコレクションがおそらく最適です。格納するデータの順序は重要ですか、それともすべてのデータに同時にアクセスする必要がありますか? その場合、通常のリストの方がよい場合があります。

追加：

もちろん、私の上記のコメントは、「パフォーマンス」がデータアクセスを意味することを前提としています。他に考慮すべきこと: 「パフォーマンス」と言うとき、何を探していますか? 性能個体値ルックアップですか？大規模な (10000、100000 以上) 値セットの管理ですか? データ構造をデータで埋める性能でしょうか。データを削除しますか? データの個々のビットにアクセスしますか? 価値観の置き換え？値を反復処理していますか? メモリ使用量？データのコピー速度？たとえば、文字列値でデータにアクセスするが、主なパフォーマンス要件が最小限のメモリ使用量である場合、競合する設計上の問題が発生する可能性があります。

score 4 · Accepted Answer

場合によります。正確な答えが本当に重要な場合は、プロファイリングを行って調べてください。セット内の要素が特定の数を超えることがないと確信している場合は、List を使用します。数に制限がない場合は、HashSet を使用します。

score 3 · Accepted Answer

何をハッシュしているかによって異なります。キーが整数の場合、HashSet が高速になる前に、おそらくそれほど多くのアイテムは必要ありません。文字列にキーを設定している場合は遅くなり、入力文字列に依存します。

確かに、ベンチマークをかなり簡単に作成できますか?

score 3 · Accepted Answer

考慮していない要因の 1 つは、GetHashcode() 関数の堅牢性です。完全なハッシュ関数を使用すると、HashSet の検索パフォーマンスが明らかに向上します。しかし、ハッシュ関数が減少するにつれて、HashSet の検索時間も減少します。

score 1 · Accepted Answer

多くの要因に依存します...リストの実装、CPUアーキテクチャ、JVM、ループセマンティクス、equalsメソッドの複雑さなど...リストが効果的にベンチマークするのに十分な大きさになるまで(1000以上の要素)、ハッシュベースのバイナリルックアップは線形検索を完全に打ち負かし、その差はそこから拡大するだけです。

お役に立てれば！

.net - HashSetとリストのパフォーマンス

12 に答える 12

サンプル出力

Related

Reference