用於存儲和搜索比賽結果的數據結構

有100個玩家p1，p2，...... p100，每個玩家對每個其他玩家進行比賽。您必須存儲每個組合（Pi，Pj）的勝者的比賽結果。用於存儲和搜索比賽結果的數據結構

什麼數據結構應該用於高效存儲和搜索結果？

來源

2012-07-31 Jatin

你會用什麼數據結構？ – Andrew 2012-07-31 06:23:30

@Andrew我正在考慮一些散列方式，因此我必須通過n/10（n，這裏是4950）或更少的元素來訪問我所尋找的元素。 – Jatin 2012-07-31 06:32:19

將一對作爲關鍵字並將勝出的玩家作爲數據進行映射可能有效。 – 2012-07-31 06:40:01

您是否考慮過2維數組？如果你只需要存儲結果，那麼我認爲這將是最好的選擇。

來源

2012-07-31 06:24:19 pidabrow

查詢結構會發生什麼，這是效率低下的。一個100X100二維數組將有100,00個元素，而我們只需要存儲4950個匹配的結果。 – Jatin 2012-07-31 06:27:13

查看關聯容器，例如std::map。這些允許您以對數查找時間存儲鍵值對。你可以考慮地圖索引對狀物體，讓你可以搜索的結果是這樣的：

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

其中i和j是兩名球員的指數。

std::map實現爲二叉搜索樹，但也有基於哈希表地圖周圍，例如C++ 11的std::unordered_map（提供tr1/unordered_map，海合會至少），或boost::hash_map。

您可以通過定義您自己的索引對（或使用std::pair<int,int>，提供少於比較）作爲地圖的關鍵字來實現此目的，也可以使用accessor方法將其包含在類中，以允許您檢查給出一對索引：

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-31 06:26:58 juanchopanza

你打算使用std :: multimap嗎？因爲如果一名球員贏得了多名球員的勝利，std :: map將不會有用。 – Sach 2012-07-31 08:10:17

@Sachin非常好。我將刪除第一個選項，並留下一對類似對象的地圖。謝謝。 – juanchopanza 2012-07-31 08:12:52

以100x100陣列。

商店贏家中的每個位置

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

空間複雜度爲O（n^2）

時間複雜度來存儲和查詢O（1）

來源

2012-07-31 06:34:33

但我不需要10,000個元素。我只需要存儲4950（100C2）匹配的結果。這是浪費記憶。 – Jatin 2012-07-31 06:36:35

我會去與一個維數組用巧妙的函數來計算索引。當第一列對應於i玩家

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

：

我將結構中的陣列作爲分組的陣列。原始對應j玩家這可能與我

這裏玩的是陣列的外觀在內存： ||0|0 1|1 0 1|1 0 0 1| // 0,1 - 布爾結果

這裏是計算指數的功能。（使它有一些錯誤，就像你有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數組，但是沒有存儲重複和自我結果。

來源

2012-07-31 06:51:16 Andrew

用於存儲和搜索比賽結果的數據結構

回答

相關問題