.NET汎用辞書は、含まれるアイテムの数に等しい容量で初期化する必要がありますか？

StackOverflow https://stackoverflow.com/questions/414109

質問

たとえば、辞書に保存される100個のアイテムがある場合、そのように初期化する必要がありますか？

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

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

これは、上記の辞書に100個のアイテムが追加された場合、アイテムの1つが追加されたときに自分自身のサイズを変更することを提案します。辞書のサイズを変更すると、パフォーマンスが低下し、メモリが無駄になるため、避けたいものです。

ハッシュの衝突の確率は、辞書の負荷に比例します。したがって、ディクショナリがそれ自体のサイズを変更しない場合（およびすべてのスロットを使用する場合）でも、これらの衝突によりパフォーマンスが低下する必要があります。

辞書内にいくつのアイテムがあるかを知っていると仮定して、辞書を初期化する能力をどのように決定するのが最善ですか？

役に立ちましたか？

解決

辞書の容量を初期化する対象は、次の2つの要因に依存します。 （1）gethashcode関数の分布、および （2）挿入する必要のあるアイテムの数。

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

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

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

他のヒント

簡単なテストを行いましたが、おそらく科学的ではありませんが、サイズを設定すると、100万個のアイテムを追加するのに1.2207780秒かかり、辞書にサイズを与えなかった場合は追加するのに1.5024960秒かかりました...私には無視できます。

ここに私のテストコードがあります。誰かがもっと厳密なテストを行うことができるかもしれませんが、私はそれが重要だとは思いません。 

static void Main(string[] args)
        {
            DateTime start1 = DateTime.Now;
            var dict1 = new Dictionary<string, string>(1000000);

            for (int i = 0; i < 1000000; 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 < 1000000; 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();
        }

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

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

Dictionary コンストラクタに初期容量kを指定することを考慮して、次のようにします。

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

MSDN から：

  

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

     

コレクションのサイズが   推定、初期を指定   容量は必要性を除去します   いくつかのサイズ変更を実行します   要素を追加しながらの操作   辞書（TKey、TValue）。

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

を使用します。

初期サイズは単なる提案です。たとえば、ほとんどのハッシュテーブルのサイズは素数または2のべき乗です。

ライセンス： CC-BY-SA と 帰属
所属していません StackOverflow
scroll top