配列のインデックス検索対辞書のキー検索：ルックアップの最適化

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

  •  05-09-2019
  •  | 
  •  

質問

私は私のペットのプロジェクトの一つとして、7カードポーカーハンド評価を書いています。 （私は挑戦が好き）その速度を最適化しようとしている間、私は辞書のキールックアップのパフォーマンスは、配列のインデックス検索に比べてかなり遅かったことを見つけるためにショックを受けた。

たとえば、私は、7 = 133784560人の可能な7人のカードの手を選択すべての52を超える列挙し、このサンプルコードを実行しました 

var intDict = new Dictionary<int, int>();
var intList = new List<int>();
for (int i = 0; i < 100000; i ++)
{
    intDict.Add(i, i);  
    intList.Add(i);
}

int result;

var sw = new Stopwatch();
sw.Start();
for (int card1 = 0; card1 < 46; card1++)
  for (int card2 = card1 + 1; card2 < 47; card2++)
    for (int card3 = card2 + 1; card3 < 48; card3++)
      for (int card4 = card3 + 1; card4 < 49; card4++)
        for (int card5 = card4 + 1; card5 < 50; card5++)
          for (int card6 = card5 + 1; card6 < 51; card6++)
            for (int card7 = card6 + 1; card7 < 52; card7++)
              result = intDict[32131]; // perform C(52,7) dictionary key lookups
sw.Stop();
Console.WriteLine("time for dictionary lookups: {0} ms", sw.ElapsedMilliseconds);

sw.Reset();

sw.Start();
for (int card1 = 0; card1 < 46; card1++)
  for (int card2 = card1 + 1; card2 < 47; card2++)
    for (int card3 = card2 + 1; card3 < 48; card3++)
      for (int card4 = card3 + 1; card4 < 49; card4++)
        for (int card5 = card4 + 1; card5 < 50; card5++)
          for (int card6 = card5 + 1; card6 < 51; card6++)
            for (int card7 = card6 + 1; card7 < 52; card7++)
              result = intList[32131]; // perform C(52,7) array index lookups
sw.Stop();
Console.WriteLine("time for array index lookups: {0} ms", sw.ElapsedMilliseconds);

出力する

time for dictionary lookups: 2532 ms
time for array index lookups: 313 ms

（8倍の性能低下）期待される行動のこのタイプのですか？ IIRC、辞書は、平均して、O（1）検索、配列は、最悪のケースを持っていながら、O（1）検索は、私はではなく、このことによって、配列の検索が速いと期待していくらい！

私は現在、辞書にポーカーハンドのランキングを格納しています。これは早くランキングをインデックス化することは少しトリッキー取得し、私はおそらくそれについて別の質問をする必要がありますが、辞書検索が、私は、代わりに私のアプローチと使用のアレイを再考しなければならないことができるようであれば、私は考えます。

役に立ちましたか？

解決

ビッグ-O表記だけ複雑さはサイズに関して（など）で成長するかと言うことを忘れてはいけない - それは関係する一定の要因のいずれかの表示を与えるものではありません。だからこそ、時にはリニアの検索を十分にいくつかのキーがある場合、キーのために、辞書検索よりも高速です。この場合、あなたもかかわらず、配列で検索をしていない - ちょうどストレートインデックス操作を

。

は、直線インデックス検索のために、アレイは、基本的には理想的である - それは念の

pointer_into_array = base_pointer + offset * size

（そしてポインタ参照。）

辞書検索を実行すると、比較的複雑である - 非常に高速なキーの多くが、はるかに複雑ストレート配列のルックアップよりもあるキーによって、（例えば）リニア検索と比較します。それは、中にする必要があることをどのバケットうまくその後、キーのハッシュを計算し、おそらく重複ハッシュ（または重複したバケット）に対処し、その後の等価性をチェックする必要があります。

いつものように、仕事のための適切なデータ構造を選択してください - あなたは本当にただの配列（またはList<T>）にインデックス付けを離れて得ることができるならば、はい、それは疑いの余地なく、高速になります。

。

他のヒント

  

期待される行動のこのタイプ（8倍の性能低下）ですか？

なぜいけないのでしょうか？辞書検索が少なくとも余分なサブルーチン呼び出しが必要になる場合があり、一方、各配列のルックアップは、無視できる/ほとんどintantaneousです。

自分のことOの両方のポイントは、（1）あなたは、各コレクション内の50倍以上のアイテムを持っている場合でも、パフォーマンスの低下は依然として唯一の要因であることを意味何でもそれがある（8）。

何かがミレニアムを取り、まだO（1）可能性があります。

あなたが逆アセンブルウィンドウでこのコードをシングルステップ、あなたはすぐに違いがあるかを理解するために来る場合ます。

鍵空間は非常に大きく、安定した、配列決定された順にマッピングすることができない場合、

辞書構造が最も便利です。あなたが比較的小さな範囲の単純な整数にあなたの鍵を変換することができた場合は、ハード押された配列よりも良好に機能するデータ構造を見つけることになります。

実装のノートで、 .NETで、辞書は、基本的にhashablesです。あなたはややあなたの鍵は、一意の値の大空間にハッシュことを確実にすることにより、そのキーのルックアップのパフォーマンスを向上させることができます。それはあなたが（私は、独自の値にハッシュを信じている）をキーとして、簡単な整数を使用している、あなたのケースのように見える - 。だから、あなたができる最善のかもしれ

配列の検索は、あなたが行うことができます最速の事についてです - 基本的にそれはすべてあなたが探していました要素に、配列の最初から行くにはポインタ演算のシングルビットです。一方、辞書検索は、それが正しいバケツを見つけると、ハッシュと懸念自身を行う必要があるため、多少遅くなる可能性があります。予想ランタイムもOであるが、（1） - アルゴリズム定数は、それが遅くなるように大きくなっている

。

ビッグO記法へようこそ。あなたは、常に関与一定の要因があることを考慮する必要があります。

1 Dictのルックアップを行うことはもちろん、はるかに高価な配列検索よります。

ビッグ-Oは、唯一のアルゴリズムが拡張する方法を説明します。検索のダブル量と数字がどのように変化するかを参照してください。どちらも、2倍の時間を中心に取る必要があります。

辞書から要素を検索するコストはO（1）が、辞書はハッシュテーブルとして実装されているためです - ので、あなたが最初に返すためにどの要素を知っているハッシュ値を計算する必要があります。ハッシュテーブルは、多くの場合、その効率的ではない - しかし、彼らは独自のハッシュ値の多くを持っている大規模なデータセット、またはデータセットに適しています。

。 それは直接返して欲しい要素を計算して値を返すよう

（離れて、配列ではなく、リンクされたリストをdercribeために使用されるごみの単語であることから！）のリストが高速になります。

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