manera eficiente de representar una matriz triangular inferior/superior

Question

Estoy trabajando en mis datos en un programa C/C++, que es bidimensional. Aquí mi valor se calcula por pares y aquí los valores serían los mismos para foo[i][j] y foo[j][i].

Por lo tanto, si lo implemento utilizando una matriz bidimensional simple, la mitad de mi espacio se desperdiciará. Entonces, ¿cuál sería la mejor estructura de datos para representar esta matriz triangular inferior/superior?

Saludos,

Answer 1

Realmente, estás mejor simplemente utilizando una matriz de dos dimensiones regulares. RAM es bastante barato. Si realmente no quieres hacer eso, entonces puedes construir una matriz unidimensional con la cantidad correcta de elementos y luego descubrir cómo acceder a cada elemento. Por ejemplo, si la matriz está estructurada de la siguiente manera:

j 
    1234 
i 1 A 
    2 BC 
    3 DEF 
    4 GHIJ 

y lo tienes almacenado como una matriz unidimensional, de izquierda a derecha, es posible acceder a C elemento (2, 2) con array[3]. Puede encontrar una función para ir de [i][j] a [n], pero no voy a arruinar su diversión. Pero no tienes que hacer esto a menos que la matriz triangular en cuestión sea realmente grande o estés muy preocupado por el espacio.

Answer 2

Utilice una matriz escalonada:

int N; 
// populate N with size 

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

creará matriz como

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

Answer 3

Si usted tiene N elementos continuación, una matriz triangular inferior sin la diagonal principal tendrá (N - 1) * N/2 elementos, o (N + 1) * N/2 elementos con la diagonal principal. Sin la diagonal principal, (I, J) (I, J ∈ 0..N-1, I> J) ⇒ (I * (I - 1)/2 + J). Con la diagonal principal, (I, J ∈ 0..N-1, I ≥ J) ⇒ ((I + 1) * I/2 + J).

(Y sí, cuando se está asignando 4 gigabytes en una máquina de 2,5 gigabytes, cortándolo medio no hacer una gran diferencia.)

Answer 4

El número de elementos únicos, m, necesarios para ser representada en una n por la matriz n simétrica:

Con la diagonal principal

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

Sin la diagonal (por matriz simétrica como la OP describe, principal diagonal es necesaria, pero solo para una buena medida ...)

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

No se divide por 2 hasta que la última operación es importante si se usa la aritmética de enteros con truncamiento.

También necesita hacer algo de aritmética para encontrar el índice, i, en la memoria asignada correspondiente a la fila xy la columna y en la matriz diagonal.

Índice en la memoria asignada, i, de la fila x y la columna y en la matriz diagonal superior:

Con la diagonal

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

Sin la diagonal

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

Para una matriz diagonal más baja invierte xey en las ecuaciones. Para una matriz simétrica simplemente elija x> = y o y> = x internamente y haga que las funciones de miembros se volteen según sea necesario.

Answer 5

Riffing sobre la respuesta de Dani ...

En lugar de asignar muchas matrices de diferentes tamaños, lo que podría conducir a patrones de fragmentación de memoria o acceder caché raro, se podría asignar una matriz para contener los datos y una pequeña gama de mantenga punteros a las filas dentro de la primera asignación.

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; 
} 

Ahora puede utilizar table como si fuera una matriz escalonada como se muestra en la respuesta de Dani:

table[row][col] = foo; 

Pero todos los datos están en un solo bloque, que no podría de otra manera ser en función de la estrategia de tu asignador.

El uso de la tabla de punteros de fila puede o no ser más rápido que calcular el desplazamiento con la fórmula de Praxeolitic.

Answer 6

en la respuesta de Adrian McCarthy, reemplazar

p += side - row; 

con

p += row + 1; 

para una matriz triangular inferior en lugar de una superior.

Answer 7

Como Dan y Praxeolitic propusieron para la matriz triangular inferior con diagonal pero con la regla de transición corregida.

Para la matriz n por n necesita la matriz (n+1)*n/2 y la regla de transición es 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]; 
    }; 
}; 

lo hice con double pero puede que sea lo más template. Esto es solo un esqueleto básico, así que no te olvides de implementar el destructor.