13

たとえば、辞書に保存される項目が 100 個ある場合、このように初期化する必要がありますか?

var myDictionary = new Dictionary<Key, Value>(100);

私の理解では、.NET ディクショナリは、特定の負荷に達すると内部的にサイズが変更され、負荷のしきい値は容量の比率として定義されます。

これは、上記の辞書に 100 個のアイテムが追加された場合、アイテムの 1 つが追加されたときにサイズが変更されることを示唆しています。ディクショナリのサイズを変更すると、パフォーマンスが低下し、メモリが無駄になるため、避けたいと思います。

ハッシュ衝突の確率は、辞書の読み込みに比例します。したがって、ディクショナリがそれ自体のサイズを変更しなくても (そしてすべてのスロットを使用しなくても)、これらの衝突のためにパフォーマンスが低下するはずです。

ディクショナリ内にいくつのアイテムがあるかを知っていると仮定して、ディクショナリを初期化する容量をどのように決定するのが最善でしょうか?

4

6 に答える 6

6

ディクショナリ容量を初期化する必要があるのは、（1）gethashcode関数の分布、および（2）挿入する必要のあるアイテムの数の2つの要因によって異なります。

ハッシュ関数はランダムに分散するか、入力セット用に特別に作成する必要があります。最初のものを想定しましょう。ただし、2番目のものに興味がある場合は、完全なハッシュ関数を調べてください。

辞書に挿入するアイテムが100個あり、ランダムに分散されたハッシュ関数で、容量を100に設定した場合、i番目のアイテムをハッシュテーブルに挿入すると、（i-1）/100の確率でi番目のアイテムが挿入されます。アイテムは挿入時に別のアイテムと衝突します。この衝突の可能性を低くしたい場合は、容量を増やしてください。予想される容量を2倍にすると、衝突の可能性が半分になります。

さらに、辞書内の各アイテムにアクセスする頻度がわかっている場合は、最初に挿入するアイテムの方が平均してアクセスが速いため、頻度の高い順にアイテムを挿入することをお勧めします。

于 2009-09-04T01:08:55.237 に答える
6

改善されたベンチマーク:

  • ハードウェア: Intel Core i7-10700K x64、.NET 5、最適化されたビルド。.NET 5 の実行には LINQPad 6、.NET Fx 4.8 の実行には LINQPad 5。
  • 時間はミリ秒の小数部から 3 桁までです。
    • 0.001msは 1 マイクロ秒です。
    • の実際の解像度はStopwatchシステムに依存するため、よくわかりません。マイクロ秒レベルの違いを強調しないでください。
  • ベンチマークは何十回も再実行され、一貫した結果が得られました。表示される時間は、すべての実行の平均です。
  • 結論:コンストラクターで設定することにより、一貫して 10 ～ 20% 全体capacityDictionary<String,String>の速度が向上します。
。ネット： .NET フレームワーク 4.8 .NET5
初期容量 1,000,000
コンストラクタ 1.170ms 0.003ms
ループを埋める 353.420ms 181.846ミリ秒
合計時間 354.590ms 181.880ms
初期容量なし
コンストラクタ 0.001ms 0.001ms
ループを埋める 400.158ms 228.687ms
合計時間 400.159ms 228.688ミリ秒
初期容量設定からの高速化
時間 45.569ms 46.8ms
スピードアップ ％ 11% 20%
  • より小さい初期サイズ ( 10、100、1000、10000および100000) のベンチマークを繰り返しましたが、それらのサイズでも 10 ～ 20% の高速化が観察されましたが、絶対的には、数分の 1 ミリ秒かかる操作で 20% の高速化が見られました。
  • 一定の結果が得られましたが (表示されている数値は平均値です)、注意点がいくつかあります。
    • このベンチマークは、1,000,000 アイテムというかなり極端なサイズで実行されましたが、現実的なシナリオではないタイト ループ (つまり、ループ本体内で他に多くのことが行われていない) を使用して実行されました。したがって、インターネットで見つけたランダムなベンチマークを信頼するのではなく、常に自分のコードをプロファイリングしてベンチマークし、確実に知るようにしてください(このようなものです)。
    • Stringベンチマークは、100 万個ほどのインスタンスの生成に費やされた時間を分離しません( i.ToString().
    • 参照型 ( String) がキーと値の両方に使用され、ネイティブ ポインター サイズ (x64 では 8 バイト) と同じサイズを使用するため、キーや値がより大きな値を使用する場合、再実行すると結果が異なります。値の型 ( a などValueTuple)。考慮すべき他のタイプサイズ要因もあります。
    • .NET Framework 4.8 から .NET 5 に大幅に改善されたため、.NET 6 以降で実行している場合は、これらの数値を信頼してはいけません。
      • また、新しい .NET リリースが_常に) 高速化すると仮定しないでください..NET の更新と OS セキュリティ パッチの両方で実際にパフォーマンスが低下した場合があります。
// Warmup:
{
    var foo1 = new Dictionary<string, string>();
    var foo2 = new Dictionary<string, string>( capacity: 10_000 );
    foo1.Add( "foo", "bar" );
    foo2.Add( "foo", "bar" );
}


Stopwatch sw = Stopwatch.StartNew();

// Pre-set capacity:
TimeSpan pp_initTime;
TimeSpan pp_populateTime;
{
    var dict1 = new Dictionary<string, string>(1000000);

    pp_initTime = sw.GetElapsedAndRestart();

    for (int i = 0; i < 1000000; i++)
    {
        dict1.Add(i.ToString(), i.ToString());
    }
}
pp_populateTime = sw.GetElapsedAndRestart();

//
TimeSpan empty_initTime;
TimeSpan empty_populateTime;
{
    var dict2 = new Dictionary<string, string>();

    empty_initTime = sw.GetElapsedAndRestart();

    for (int i = 0; i < 1000000; i++)
    {
        dict2.Add(i.ToString(), i.ToString());
    }
}
empty_populateTime = sw.GetElapsedAndRestart();

//

Console.WriteLine("Pre-set capacity. Init time: {0:N3}ms, Fill time: {1:N3}ms, Total time: {2:N3}ms.", pp_initTime.TotalMilliseconds, pp_populateTime.TotalMilliseconds, ( pp_initTime + pp_populateTime ).TotalMilliseconds );
Console.WriteLine("Empty capacity. Init time: {0:N3}ms, Fill time: {1:N3}ms, Total time: {2:N3}ms.", empty_initTime.TotalMilliseconds, empty_populateTime.TotalMilliseconds, ( empty_initTime + empty_populateTime ).TotalMilliseconds );

// Extension methods:

[MethodImpl( MethodImplOptions.AggressiveInlining | MethodImplOptions.AggressiveOptimization )]
public static TimeSpan GetElapsedAndRestart( this Stopwatch stopwatch )
{
    TimeSpan elapsed = stopwatch.Elapsed;
    stopwatch.Restart();
    return elapsed;
}

元のベンチマーク:

コールド スタートアップ ウォームアップ フェーズと精度の低いDateTimeタイミングのない元のベンチマーク:

  • キャパシティ ( dict1) の合計時間は1220.778ms(建設と人口の) です。
  • 容量なし ( dict2) の合計時間は1502.490ms(建設と人口の) です。
  • したがって、容量を設定しない場合と比較して、容量は 320 ミリ秒 (~20%) 節約されました。
static void Main(string[] args)
{
    const int ONE_MILLION = 1000000;

    DateTime start1 = DateTime.Now;
    
    {
        var dict1 = new Dictionary<string, string>( capacity: ONE_MILLION  );

        for (int i = 0; i < ONE_MILLION; i++)
        {
            dict1.Add(i.ToString(), i.ToString());
        }
    }
        
    DateTime stop1 = DateTime.Now;
        
    DateTime start2 = DateTime.Now;

    {
        var dict2 = new Dictionary<string, string>();

        for (int i = 0; i < ONE_MILLION; i++)
        {
            dict2.Add(i.ToString(), i.ToString());
        }
    }
        
    DateTime stop2 = DateTime.Now;
        
    Console.WriteLine("Time with size initialized: " + (stop1.Subtract(start1)) + "\nTime without size initialized: " + (stop2.Subtract(start2)));
    Console.ReadLine();
}
于 2009-01-05T19:10:21.680 に答える
5

問題を複雑にしすぎていると思います。ディクショナリに含まれる項目の数がわかっている場合は、必ずそれを作成時に指定してください。これにより、ディクショナリが内部データ構造に必要なスペースを割り当てて、データの再割り当てと再シャッフルを回避できます。

于 2009-01-05T19:03:17.340 に答える
2

コンストラクターに初期容量を指定すると、DictionaryADD 操作中に辞書値を格納する内部構造体のサイズ変更の回数が少なくなるため、パフォーマンスが向上します。

Dictionaryコンストラクターに k の初期容量を指定すると、次のようになります。

  1. はDictionary、k 個の要素を格納するために必要なメモリ量を確保します。
  2. ディクショナリに対する QUERY のパフォーマンスは影響を受けず、速くも遅くもなりません。
  3. ADD 操作は、より多くのメモリ割り当てを必要としない (おそらくコストがかかる) ため、高速になります。

MSDNから:

Dictionary(TKey, TValue) の容量は、サイズ変更が必要になる前に Dictionary(TKey, TValue) に追加できる要素の数です。要素が Dictionary(TKey, TValue) に追加されると、内部配列を再割り当てすることにより、必要に応じて容量が自動的に増加します。

コレクションのサイズを見積もることができる場合は、初期容量を指定することで、Dictionary(TKey, TValue) に要素を追加する際に何度もサイズ変更操作を実行する必要がなくなります。

于 2009-01-05T19:09:04.910 に答える
1

HashTableはい、衝突を解決する方法として再ハッシュを使用する a とは対照的に、Dictionary連鎖を使用します。そうです、カウントを使用するのは良いことです。HashTableあなたがおそらく使いたいcount * (1/fillfactor)

于 2009-01-05T19:08:14.350 に答える
-1

初期サイズはあくまでも目安です。たとえば、ほとんどのハッシュ テーブルは、素数または 2 のべき乗のサイズを好みます。

于 2009-01-05T19:10:42.910 に答える