如何存储对称矩阵？

Question

在内存中存储对称矩阵的最佳方式是什么？

如果能节省一半的空间，而又不会过多地影响速度和结构的复杂性，那就太好了。这是一个与语言无关的问题，但如果您需要做出一些假设，只需假设它是一种很好的老式普通编程语言，例如 C 或 C++

。当矩阵本身很大时，我是对的吗？

只是为了正式起见，我的意思是这个断言对于我想要存储的数据总是正确的

matrix[x][y] == matrix[y][x]

Answer 1

这是存储对称矩阵的好方法，它只需要 N(N+1)/2 内存：

int fromMatrixToVector(int i, int j, int N)
{
   if (i <= j)
      return i * N - (i - 1) * i / 2 + j - i;
   else
      return j * N - (j - 1) * j / 2 + i - j;
}

对于某些三角矩阵

0 1 2 3
  4 5 6
    7 8
      9

一维表示（例如，存储在 std::vector 中）看起来像如下：

[0, 1, 2, 3, 4, 5, 6, 7, 8, 9]

并且调用 fromMatrixToVector(1, 2, 4) 返回 5，因此矩阵数据为 vector[5] -> 5.

有关详细信息，请参阅 http://www.codeguru.com/cpp/cpp/algorithms/general/article.php/c11211/TIP-Half-Size-Triangle-Matrix.htm

Answer 2

我发现许多高性能包只存储整个矩阵，但只读取上三角形或下三角形。然后，他们可能会在计算期间使用额外的空间来存储临时数据。

但是，如果存储确实是一个问题，那么只需将构成上三角形的 n(n+1)/2 元素存储在一维数组中即可。如果这使您的访问变得复杂，只需定义一组辅助函数即可。

在 C 中，要访问矩阵 matA，您可以定义一个宏：

#define A(i,j, dim) ((i <= j)?matA[i*dim + j]:matA[j*dim + i])

然后您几乎可以正常访问数组。

Answer 3

好吧，我会尝试一个三角矩阵，如下所示：

int[][] sym = new int[rows][];
for( int i = 0; i < cols; ++i ) {  
     sym=new int[i+1];
}

但是当有人想要访问“另一边”时，您将不得不面对问题。例如，他想访问 [0][10]，但在你的情况下，这个 val 存储在 [10][0] 中（假设 10x10）。

可能“最好”的方法是懒惰的方法 - 在用户请求之前不执行任何操作。因此，如果用户键入 print(matrix[4]) 之类的内容，您可以加载特定行。

Answer 4

如果你想使用一维数组，代码将如下所示：

int[] new matrix[(rows * (rows + 1 )) >> 1];
int z;
matrix[ ( ( z = ( x < y ? y : x ) ) * ( z + 1 ) >> 1 ) + ( y < x ? y : x ) ] = yourValue; 

如果你创建一个额外的查找表，你可以摆脱乘法：

int[] new matrix[(rows * (rows + 1 )) >> 1];
int[] lookup[rows];
for ( int i= 0; i < rows; i++)
{
   lookup[i] = (i * (i+1)) >> 1;
}
matrix[ lookup[ x < y ? y : x ] + ( x < y ? x : y )  ] = yourValue;

Answer 5

如果您使用的是支持运算符重载的东西（例如C++），那么透明地处理这个问题非常容易。只需创建一个矩阵类来检查两个下标，如果第二个下标大于第一个下标，则交换它们：

template <class T>
class sym_matrix { 
    std::vector<std::vector<T> > data;
public:
    T operator()(int x, int y) {
        if (y>x)
            return data[y][x];
        else
            return data[x][y];
    }
};

目前我跳过了其他所有内容，只介绍了下标。实际上，为了正确处理左值和右值的使用，您通常需要返回代理而不是直接返回 T。您需要一个将 data 创建为三角形的 ctor（即，对于 NxN 矩阵，第一行将有 N 个元素，第二行有 N-1 个元素，依此类推 - 或者，相当于 1 , 2, ...N)。您还可以考虑将data创建为单个向量——您必须计算出正确的偏移量，但这并不是非常困难，而且它会使用更少的内存，运行得更快一些，等等。我会在第一个版本中使用简单的代码，并在必要时进行优化。

Answer 6

如果您的语言支持交错数组，并且当 x < 时，您可以使用交错数组（或任何名称）。 y，交换x和y的位置。所以......

nxn 矩阵的伪代码（有点Python风格，但不是真的）：

matrix[n][]

for i from 0 to n-1:
    matrix[i] = some_value_type[i + 1]

[next, assign values to the elements of the half-matrix]

然后当引用值时......

if x < y:
    return matrix[y][x]
else:
    return matrix[x][y]