0

100 人のプレイヤー p1, p2, ...... p100 がいて、各プレイヤーは他のすべてのプレイヤーと対戦します。各組み合わせ (Pi、Pj) の勝者である試合の結果を保存する必要があります。

結果を効率的に保存および検索するには、どのデータ構造を使用すればよいですか?

4

4 に答える 4

3

std::mapなどの連想コンテナーを見てください。これらにより、キーと値のペアを対数のルックアップ時間で保存できます。次のように結果を検索できるように、インデックス ペアのようなオブジェクトのマップを考えることができます。

int result = myMap[PairLikeType(i,j)];

ここでi、 とjは 2 人のプレーヤーのインデックスです。

std::mapはバイナリ検索ツリーとして実装されていますが、ハッシュ テーブル ベースのマップもあります。たとえば、C++11 のstd::unordered_map (tr1/unordered_map少なくとも gcc で利用可能)、またはboost::hash_map.

マップのキーとして独自のインデックス ペアを定義する (またはstd::pair<int,int>、より少ない比較が提供される を使用する) ことでこれを実装できます。インデックス:

struct ResultMap {
  int winnerID(int playerID1, int playerID2)
  {
    return m_map[std::make_pair(playerID1, playerID2)]; // or use map::find
                                                        // of you want to handle
                                                        // non-existent keys specially
  }
 private:
  std::map<std::pair<int,int>, int> m_map;
};

上記を で実装できstd::unordered_mapますが、 に対して独自のハッシュ関数を提供する必要がありますstd::pair<int,int>。

于 2012-07-31T06:26:58.813 に答える
1

インデックスを計算するための巧妙な関数を備えた 1 次元配列を使用します。

配列をパケットの配列として構造化します。

0 
1  0
2  0 1
3  0 1 2
4  0 1 2 3 
//and so on

最初の列はiプレーヤーに対応します。rawはjiで遊べるプレイヤーに対応

配列がメモリ内でどのように見えるかを次に示します。 ||0|0 1|1 0 1|1 0 0 1|//0,1 - bool の結果

インデックスを計算する関数は次のとおりです。(いくつかのインデックスに 1 を追加する必要があるなど、いくつかの間違いがありますが、一般的には正しいです)

int index(int i, int j) // i = [0, 99], j = [0, 99]
{
    assert(i != j);
    if ( i < j) std::swap(i, j); //i should be maximum. i == j not considered

    int num_oponents = i;

    int pack_start_index = num_oponents * (num_oponents + 1) / 2; //sum of 1 + 2 + 3 + ... + num_oponents
    int pack_internal_index = j;

    return pack_start_index + pack_internal_index;
}

その場合、必要なデータ (4950 項目) 以外は保存されません。

このソリューションの考え方は 2 次元配列に似ていますが、複製と自己の結果を保存しません。

于 2012-07-31T06:51:16.157 に答える
0

2次元配列を検討しましたか? 結果だけを保存する必要がある場合は、それが最適な選択になると思います。

于 2012-07-31T06:24:19.647 に答える
0

100x100 配列を取ります。

勝者を各位置に格納する

    p1 p2 p3  
 p1 0  p2 p1  
 p2 p2 0  p3 
 p3 p1 p3 0

スペースの複雑さ O(n^2)

O(1) の格納とクエリにかかる時間の複雑さ

于 2012-07-31T06:34:33.843 に答える