表示下/上三角矩阵的有效方法

Question

我正在使用C/C++程序处理我的数据,这是2维的.这里我的值是按成对计算的,这里的值对于foo[i][j]和是相同的foo[j][i].

因此,如果我使用一个简单的二维数组实现它,我的一半空间将被浪费.那么表示这种下/上三角矩阵的最佳数据结构是什么.

问候,

Answer 1

如果你有N个项目,那么没有主对角线的下三角形阵列将具有(N-1)*N/2个元素,或者具有主对角线的(N + 1)*N/2个元素.没有主对角线,(I,J)(I,J∈0..N-1,I> J)⇒(I*(I - 1)/ 2 + J).对于主对角线,(I,J∈0..N-1,I≥J)⇒((I + 1)*I/2 + J).

(是的,当你在一台2.5千兆字节的机器上分配4千兆字节时,削减一半会产生巨大的差异.)

Answer 2

真的,你最好只使用常规的二维矩阵.RAM非常便宜.如果你真的不想这样做,那么你可以构建一个具有正确数量元素的一维数组,然后找出如何访问每个元素.例如,如果数组的结构如下:

    j
    1234
i 1 A
  2 BC
  3 DEF
  4 GHIJ

你把它保存为一个维数组,左到右,你会访问元素C (2, 2)用array[3].你可以制定出一个功能从去[i][j]到[n],但我不会让你扫兴.但是你不必这样做,除非所讨论的三角形阵列真的很大或者你非常关心空间.

Answer 3

正如 Dan 和 Praxeolitic 提出的具有对角线但具有修正的转移规则的下三角矩阵。

对于矩阵 n × n，您需要数组(n+1)*n/2长度，并且转换规则为Matrix[i][j] = Array[i*(i+1)/2+j]。

#include<iostream>
#include<cstring>

struct lowerMatrix {
  double* matArray;
  int sizeArray;
  int matDim;

  lowerMatrix(int matDim) {
    this->matDim = matDim;
    sizeArray = (matDim + 1)*matDim/2;
    matArray = new double[sizeArray];
    memset(matArray, .0, sizeArray*sizeof(double));
  };

  double &operator()(int i, int j) {
    int position = i*(i+1)/2+j;
    return matArray[position];
  };
};

我用的是，double但你可以把它做成template。这只是基本框架，所以不要忘记实现析构函数。