关联矩阵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]。

在上述技术中，您可以使用范围压缩矩阵位置。