個別の値ごとに複数のキーを使用して辞書を最適化するにはどうすればよいですか？

Question

私は、C＃の辞書オブジェクトに非常に自然に役立つ比較的大きなデータセットを持っています。現在、私のプログラムが起動するときに準動的に生成される102400個のキーと値のペアがあります。私の問題は、できるだけ早く多数の検索操作を実行する必要があることです。

This Pageによれば、ルックアップの速度は、辞書内のキーと値のペアの数によって直接影響されます。多数の異なるキーが同じ値につながるという点で私のデータはちょっと奇妙です。実際、私には4900個の異なる値があります...これは、それぞれの別個の値に対して平均20個のキーと値のペアがあることを意味します。

私の最初の本能は、値のキーを入れ替えることでした（私はデータ内の別個の値だけを気にするので）。リストまたは配列の古いキーを新しい値として使用します。これは私の辞書サイズを102400のキーと値のペアから4900に減らしましたが、キーを取得する特定の値のすべてのリストを効率的に検索する方法はありません。

は、私は私の記述はおそらく私がキーと値を切り替えるようdificultビットが続くようになったことを知っているので、私は私のデータのモックアップは、私が何を意味するかをお見せするために含めました：

古い方法を：

Key Value 
--- ----- 
1  1 
2  2 
3  3 
4  1 
5  3 
6  2 
7  2 
8  1 
9  3 
10 2 
11 3 
12 1 

新構造：私のプログラムで

Key Value 
--- ----- 
1  {1,4,8,12} 
2  {2,6,7,10} 
3  {3,9,5,11} 

、私は '11' 与えられることになるだろうと私は返す必要があります '3'。最初の構造は簡単なルックアップですが、遅くなっているように見える巨大なリストです...第2の構造は、私が探している値リストを追跡するために非常に多くの論理的なオーバーヘッドを追加します。それを実装しようとする速度。

ここで間違った木を吠えていますか？私は大きなリストの速度を受け入れるべきですか、またはルックアップスピードを上げるためにデータを保存することができる他の方法がありますか？

Answer 1

すべてのキーが別個で連続している場合は、単純な配列を考慮する必要があります。キーが連続していない場合は、構造体のハッシュマップ型でなければなりません。これは、ハッシング関数が良好であればO（1）に近づき、すべて整数であれば、多くのスペースを取るべきではありません。

それでも102400要素の場合、バイナリツリーのルックアップはルックアップごとにlog2（102400）回の操作を必要としますが、ルックアップは正確には遅くなく16.64回の操作です。

Answer 2

Lookup（.NET 3.5以上）を使用してください。 MSDNから

：

（TElement、処理鍵の）

ルックアップは、それぞれが1つまたは複数の値にマッピングされたキーのコレクションを表します。

EDIT：ところで 、すべてのキーが連続している場合（すなわち1、2、3、...）、単純な配列を使用します。

Answer 3

辞書は、あなたのキーが連続していない場合に行く方法です。私はその種のデータの検索方法が高速であることに気づいていません。あなたの例では、配列に直接値を格納し、キーに基づいてインデックスを修正するために直接ジャンプすることで利益を得られる連続した連続データが表示されます。あなたの実際のデータのキーがあなたのサンプルキーを模倣する限り、私は配列に行くでしょう。私は理解されるようにあなたは限り、あなたの新しいstrutcure、このようなものを作っ

Answer 4

ある時、firstとsecondは整数で

Dictionary<first, List<second>>、。 List<second>の内容がとなっていることに注意してください。

あなたが挑戦することを考慮すると、安全なList,BinarySearch、リスト項目のうちデータを見つけるための最速の方法を実行できるようになるList<second>を持つ、データのない高速な構図が、高速アクセスと回復です。

Answer 5

Dictionary<int, ulong>のパラメータを使用して、一意の値ごとに20個のキー/値のペア、合計102400個のキーと値のペア、およびcode you linkedを使用して、102,400カウントの辞書とその10倍のサイズのテストを実行しました：

int entries = 102400; 
    var full = new Dictionary<int, ulong>(); 
    var half = new Dictionary<int, ulong>(); 
    var both = new Dictionary<int, ulong>(); 

    for (int i = 0; i < entries * 10; i++) 
    { 
     full.Add(i, (ulong)(i % 20)); 
     if (i < entries) 
     { 
      both.Add(i, (ulong)(i % 20)); 
      half.Add(i, (ulong)(i % 20)); 
     } 
    } 

    const int m = 100; 
    Stopwatch s1 = Stopwatch.StartNew(); 
    for (int i = 0; i < m; i++) 
    { 
     foreach (var key in both.Keys) 
     { 
      if (!full.ContainsKey(key)) 
      { 
       throw new Exception(); 
      } 
     } 
    } 
    s1.Stop(); 

    Stopwatch s2 = Stopwatch.StartNew(); 
    for (int i = 0; i < m; i++) 
    { 
     foreach (var key in both.Keys) 
     { 
      if (!half.ContainsKey(key)) 
      { 
       throw new Exception(); 
      } 
     } 
    } 
    s2.Stop(); 
    Console.WriteLine("{0},{1}, difference = {2}", s1.ElapsedMilliseconds, s2.ElapsedMilliseconds, s1.ElapsedMilliseconds - s2.ElapsedMilliseconds); 

両方のテストがお互いに10ミリ秒以内に終了しました。

私はあなたのルックアップのスピードはここでは問題ではないと思います。