關聯矩陣C++太大

Question

哪裏可以減小矩陣的大小？ （x2數組） 例如，我只需要將數據（0,1,2）存儲到數組 中，但元素可以高達250 000。 有沒有一種方法來存儲值，如在字典..？

const int MAX = 250000; 
short data[MAX][MAX] = {};//wont compile.. 

Answer 1

我記得靜態變量的sizeof有一些限制。使用動態內存。 根據元素數量和內存限制，您可以使用不同類型的存儲。

1. 當元素數量少於某個預定義值時，換句話說數據密度低，可以使用稀疏矩陣。 稀疏矩陣的想法很簡單：你不保留所有可能的元素;相反，你保持一些大數目的元素的簡單數組，比如1000，類型爲struct {int line，row;無符號字符值;}。達到某個值時，這種數組的內存消耗小於矩陣。但隨機訪問可能會造成很大的開銷。可以應用一些優化來減少它。
2. 如果數據密度很高，「活動」元素的數量很大，使用壓縮矩陣和位填充可以實現一些效果。這可以通過記憶非常有效。在你的例子中，每個值只需要2位，所以int64會將32個值保留在「行」中。這裏需要精細優化的訪問方法來減少時間消耗。
3. 您可以在上述解決方案之間切換，從稀疏矩陣遷移到壓縮矩陣。

Answer 2

這完美的工作對我來說，因爲我上面的評論（live here）：

#include <iostream> 
#include <unordered_map> 

std::unordered_map<unsigned int, std::unordered_map<unsigned int, unsigned char>> data; 

int main() { 
    std::cout << "oi" << std::endl; 

    data[232432][234234] = 2; 
    data[2][2] = 1; 
    std::cout << int(data[232432][234234]) << std::endl; 
    std::cout << int(data[3][3]) << std::endl; 
    std::cout << int(data[232432][1]) << std::endl; 
    std::cout << int(data[2][2]) << std::endl; 
} 

Answer 3

如果數據非常稀疏，然後Massa's approach具有每每個項目的額外unordered_map的開銷。較低的開銷的解決辦法是指數無序地圖對：

#include <iostream> 
#include <unordered_map> 

/// Hash specialization for a pair of unsigned ints 
template<> struct std::hash<std::pair<unsigned int, unsigned int>> 
{ 
    typedef std::pair<unsigned int, unsigned int> argument_type; 
    typedef std::size_t value_type; 
    value_type operator()(argument_type const& s) const 
    { 
    value_type const h1 (std::hash<unsigned int>()(s.first)); 
    value_type const h2 (std::hash<unsigned int>()(s.second)); 
    return h1^(h2 << 1); 
    } 
}; 

std::unordered_map<std::pair<unsigned int, unsigned int>, unsigned char> data; 

int main() { 
    using std::make_pair; 
    data[make_pair(232432u, 234234u)] = 2; 
    data[make_pair(2u, 3u)] = 1; 
    std::cout << int(data[make_pair(232432u, 234234u)]) << std::endl; 
    std::cout << int(data[make_pair(3u, 3u)]) << std::endl; 
    std::cout << int(data[make_pair(232432u, 1u)]) << std::endl; 
    std::cout << int(data[make_pair(2u, 3u)]) << std::endl; 
} 

Answer 4

壓縮
您可以壓縮的數據值，這將節省你的內存，但增加的訪問時間。

您的取值範圍：0,1,2，佔用2位來表示。因此，一個8位，uint8_t，變量可以容納4列值：

3 2 1 0 
+--+--+--+--+ 
|xx|xx|xx|xx| 
+--+--+--+--+ 

要訪問該值，則需要執行一些二進制算術：

value of column 0 == (byte & 0x03); /* >> 0 */ 
value of column 1 == (byte & 0x0c) >> 2; 
value of column 2 == (byte & 0x30) >> 4; 
value of column 3 == (byte & 0xC0) >> 6; 

字節將被訪問：(index/4)

變化的角度
因爲你只有3個值，你可以在座標存儲在一個數組列表。你會搜索數組的座標。

Data  row col  row col 
+---+  +-----+----+  +-----+---+ 
| 0 | --> | 115 | 25 | --> |20961| 4 | 
+---+  +-----+----+  +-----+---+ 
| 1 | 
+---+ 
| 2 | 
+---+ 

在上面的例子中，矩陣位置[115] [25]包含零以及[4]。

在上述技術中，您可以使用範圍壓縮矩陣位置。