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

I am working on my data in a C/C++ program, which is 2 dimensional. Here my value is calculated for pair-wise and here values would be same for foo[i][j] and foo[j][i].

我正在一个C/ c++程序中处理我的数据，它是二维的。这里我的值是成对计算的这里的值对于foo[i][j]和foo[j][i]都是一样的。

Thus if I implement it by using a simple 2 dimensional array, half of my space would be wasted. So what would be best data structure to represent this lower/upper triangular matrix.

因此，如果我使用一个简单的二维数组来实现它，我的一半空间就会被浪费掉。所以最好的数据结构代表这个下/上三角矩阵。

Regards,

问候,

7 个解决方案

#1

Really, you're best off just using a regular two dimensional matrix. RAM is pretty cheap. If you really don't want to do that, then you can build a one-dimensional array with the right number of elements and then figure out how to access each element. For example, if the array is structured like this:

实际上，你最好使用一个普通的二维矩阵。RAM是相当便宜的。如果您真的不想这样做，那么您可以构建一个具有正确数量元素的一维数组，然后计算如何访问每个元素。例如，如果数组的结构是这样的:

    j
    1234
i 1 A
  2 BC
  3 DEF
  4 GHIJ

and you have it stored as a one dimensional array, left to right, you'd access element C (2, 2) with array[3]. You can work out a function to go from [i][j] to [n] but I won't spoil your fun. But you don't have to do this unless the triangular array in question is really huge or you're very concerned about space.

它以一维数组的形式存储，从左到右，用数组[3]访问元素C (2,2)你可以想出一个从[j]到[n]的函数，但我不会破坏你的乐趣。但是你不需要这样做除非这个三角形数组真的很大或者你非常关心空间。

#2

If you have N items then a lower triangular array without the main diagonal will have (N - 1) * N / 2 elements, or (N + 1) * N / 2 elements with the main diagonal. Without the main diagonal, (I, J) (I,J ∈ 0..N-1, I > J) ⇒ (I * (I - 1) / 2 + J). With the main diagonal, (I,J ∈ 0..N-1, I ≥ J) ⇒ ((I + 1) * I / 2 + J).

如果有N个元素，那么没有主对角线的下三角数组将有(N - 1) * N / 2个元素，或者(N + 1) * N / 2个主对角线元素。没有主对角线,(I,J)(I,J∈0 . .n - 1,我> J)⇒(我*(I - 1)/ 2 + J),与主对角线(I,J∈0 . .n - 1,我≥J)⇒((I + 1)*我/ 2 + J)。

(And yes, when you're allocating 4 gigabytes on a 2.5 gigabyte machine, cutting it half does make a huge difference.)

(是的，当你在一台2.5 g的机器上配置4g时，将其减半确实会带来巨大的不同。)

#3

Use a jagged array:

使用多重数组:

int N;
// populate N with size

int **Array = new Array[N];
for(int i = 0; i < N; i++)
{
    Array[i] = new Array[N - i];
}

it will create array like

它将创建类似的数组

   0 1 2 3 4 5
0 [           ]
1 [         ]
2 [       ]
3 [     ]
4 [   ]
5 [ ]

#4

The number of unique elements, m, needed to be represented in an n by n symmetric matrix:

唯一元素m的个数，需要用n×n对称矩阵表示:

With the main diagonal

与主对角线

m = (n*(n + 1))/2

m = (n*(n + 1))/2

Without the diagonal (for symmetric matrix as the OP describes, main diagonal is needed, but just for good measure...)

没有对角线(对于OP描述的对称矩阵，需要主对角线，但只是为了更好的测量…)

m = (n*(n - 1))/2.

m = (n*(n - 1))/2。

Not dividing by 2 until the last operation is important if integer arithmetic with truncation is used.

如果使用具有截断的整数算法，在最后一次操作之前不除以2是很重要的。

You also need to do some arithmetic to find the index, i, in the allocated memory corresponding to row x and column y in the diagonal matrix.

你还需要做一些算术来找到索引i，在分配的内存中对应于x行和y列的对角线矩阵。

Index in allocated memory, i, of row x and column y in upper diagonal matrix:

第x行和第y列在上对角矩阵的分配内存i中的索引:

With the diagonal

的对角线

i = (y*(2*n - y + 1))/2 + (x - y - 1)

Without the diagonal

没有对角

i = (y*(2*n - y - 1))/2 + (x - y -1)

For a lower diagonal matrix flip x and y in the equations. For a symmetric matrix just choose either x>=y or y>=x internally and have member functions flip as needed.

对于一个较低的对角矩阵翻转x和y。对于对称矩阵，只需在内部选择x>=y或y>=x，并让成员函数按需翻转即可。

#5

In Adrian McCarthy's answer, replace

在阿德里安·麦卡锡的回答中，替换

p += side - row;

with

与

p += row + 1;

for a lower triangular matrix instead of an upper one.

对于下三角矩阵而不是上三角矩阵。

#6

As Dan and Praxeolitic proposed for lower triangular matrix with diagonal but with corrected transition rule.

就像Dan和Praxeolitic提出的对角线下三角形矩阵，但有修正的过渡规则。

For matrix n by n you need array (n+1)*n/2 length and transition rule is Matrix[i][j] = Array[i*(i+1)/2+j].

对于n×n矩阵，需要数组(n+1)*n/2长度，过渡规则为矩阵[i][j] =数组[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];
  };
};

I did it with double but you can make it as template. This is just basic skeleton so don't forget to implement destructor.

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

#7

Riffing on Dani's answer...

专注于达尼的回答…

Instead of allocating many arrays of various sizes, which could lead to memory fragmentation or weird cache access patterns, you could allocate one array to hold the data and one small array to hold pointers to the rows within the first allocation.

与其分配不同大小的数组(这可能导致内存碎片或奇怪的缓存访问模式)，不如分配一个数组来保存数据，而分配一个小数组来保存第一个分配中的指向行的指针。

const int side = ...;
T *backing_data = new T[side * (side + 1) / 2];  // watch for overflow
T **table = new T*[side];
auto p = backing_data;
for (int row = 0; row < side; ++row) {
   table[row] = p;
   p += side - row;
}

Now you can use table as though it was a jagged array as shown in Dani's answer:

现在你可以使用表格，就像它是一个锯齿状的数组，如Dani的答案所示:

table[row][col] = foo;

But all the data is in a single block, which it might not otherwise be depending on your allocator's strategy.

但是所有的数据都在一个块中，否则它可能不会依赖于分配器的策略。

Using the table of row pointers may or may not be faster than computing the offset using Praxeolitic's formula.

使用行指针表可能比使用Praxeolitic公式计算偏移速度快，也可能慢。

#1

    j
    1234
i 1 A
  2 BC
  3 DEF
  4 GHIJ

#2