35

お気に入りのプロジェクトの 1 つとして、7 カード ポーカーのハンド評価を書いています。その速度を最適化しようとしている間 (私はその挑戦が好きです)、Dictionary キー検索のパフォーマンスが配列インデックス検索と比較して非常に遅いことにショックを受けました。

たとえば、52 の choose 7 = 133,784,560 の可能な 7 枚のカード ハンドすべてを列挙するこのサンプル コードを実行しました。

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 分の 1 に低下します)。IIRC では、ディクショナリには平均で O(1) ルックアップがあり、配列には最悪の O(1) ルックアップがあるため、配列ルックアップが高速になると期待していますが、それほどではありません!

現在、ポーカーハンドのランキングを辞書に保存しています。これが辞書検索と同じくらい速い場合は、アプローチを再考して代わりに配列を使用する必要があると思いますが、ランキングのインデックス作成は少し難しくなり、おそらくそれについて別の質問をする必要があります.

4

7 に答える 7

67

Big-O 表記法は、サイズ (など) に応じて複雑さがどのように増加するかを示しているだけであることを忘れないでください。関連する一定の要因を示すものではありません。そのため、キーの数が十分に少ない場合、キーの線形検索でも辞書検索よりも高速になることがあります。ただし、この場合、配列を使用して検索を行っているわけではありません。単純なインデックス操作です。

単純なインデックス ルックアップの場合、配列は基本的に理想的です。

pointer_into_array = base_pointer + offset * size

(そして、ポインター逆参照。)

ディクショナリ ルックアップの実行は比較的複雑です。たとえば、多数のキーがある場合のキーによる線形ルックアップに比べて非常に高速ですが、単純な配列ルックアップよりもはるかに複雑です。キーのハッシュを計算し、次にどのバケットに入れるかを決定し、場合によっては重複ハッシュ (または重複バケット) を処理し、同等性をチェックする必要があります。

いつものように、ジョブに適したデータ構造を選択してください。配列 (または ) にインデックスを付けるだけで本当にうまくいく場合は、そうです。それは非常にList<T>高速です。

于 2009-05-25T21:09:02.410 に答える
8

このタイプの動作は予想されますか（パフォーマンスが8分の1に低下します）？

なぜだめですか？各配列ルックアップはほとんど瞬時/無視可能ですが、辞書ルックアップには少なくとも追加のサブルーチン呼び出しが必要になる場合があります。

両方ともO（1）であるという点は、各コレクションに50倍のアイテムがある場合でも、パフォーマンスの低下はそれが何であれ（8）の要因にすぎないことを意味します。

于 2009-05-25T21:13:34.477 に答える
3

配列ルックアップは、実行できる最速の処理です。基本的には、配列の先頭から検索したい要素に移動するための 1 ビットのポインター演算だけです。一方、ディクショナリ ルックアップは、ハッシュを行う必要があり、正しいバケットを見つけることに関与する必要があるため、多少遅くなる可能性があります。予想される実行時間も O(1) ですが、アルゴリズム定数が大きいため、遅くなります。

于 2009-05-25T21:09:56.963 に答える
2

Big-O記法へようこそ。一定の要因が関与していることを常に考慮する必要があります。

もちろん、Dict-Lookup を 1 回実行すると、配列の検索よりもはるかにコストがかかります。

Big-O は、アルゴリズムがどのようにスケーリングするかを示すだけです。ルックアップの量を 2 倍にして、数値がどのように変化するかを確認します。どちらも約 2 倍の時間がかかるはずです。

于 2009-05-25T21:10:19.943 に答える
1

ディクショナリから要素を取得するコストはO（1）ですが、これはディクショナリがハッシュテーブルとして実装されているためです。したがって、最初にハッシュ値を計算して、返す要素を知る必要があります。多くの場合、ハッシュテーブルはそれほど効率的ではありませんが、大規模なデータセットや、一意のハッシュ値が多数あるデータセットには適しています。

リスト（リンクリストではなく配列をdercribeするために使用されるごみの単語であることは別として！）は、返される要素を直接計算することによって値を返すため、より高速になります。

于 2009-05-25T21:18:37.977 に答える