0

有 100 个玩家 p1, p2, ...... p100，每个玩家与其他玩家进行一场比赛。您必须存储作为每个组合（Pi，Pj）获胜者的比赛结果。

我应该使用什么数据结构来高效存储和搜索结果？

4

4 回答 4

3

查看关联容器，例如std::map。这些允许您以对数查找时间存储键值对。您可以考虑类似索引对的对象的映射，以便您可以像这样搜索结果：

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

其中i和j是两个玩家的指数。

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

我会使用具有聪明功能的一维数组来计算索引。

我会将数组构造为数据包数组：

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

其中第一列对应于i玩家。raw对应j可以和i一起玩的玩家

这是数组在内存中的样子： ||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 项）外，没有其他任何东西被存储

该解决方案的思想类似于 2d 数组，但不存储重复项和 self 以及 self 结果。

于 2012-07-31T06:51:16.157 回答
0

你考虑过二维数组吗？如果您只需要存储结果，那么我认为这将是最好的选择。

于 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 回答