c++ - superior - tipos de matrices pdf

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 para 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 perdería. Entonces, ¿cuál sería la mejor estructura de datos para representar esta matriz triangular inferior / superior?

Saludos,

Answer 1

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

Para la matriz n por n necesita matriz (n+1)*n/2 longitud 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 puedes hacerlo como template . Este es solo un esqueleto básico, así que no olvides implementar el destructor.

Answer 2

En la respuesta de Adrian McCarthy, reemplaza

p += side - row;

con

p += row + 1;

para una matriz triangular inferior en lugar de una superior.

Answer 3

Realmente, es mejor usar una matriz bidimensional normal. RAM es bastante barato. Si realmente no quieres hacer eso, entonces puedes construir una matriz unidimensional con el número correcto de elementos y luego averiguar cómo acceder a cada elemento. Por ejemplo, si la matriz está estructurada de esta manera:

    j
    1234
i 1 A
  2 BC
  3 DEF
  4 GHIJ

y lo tiene almacenado como una matriz unidimensional, de izquierda a derecha, tendría acceso al elemento C (2, 2) con la array[3] . Puedes elaborar una función para pasar de [i][j] a [n] pero no arruinaré tu diversión. Pero no tiene que hacer esto a menos que la matriz triangular en cuestión sea realmente enorme o esté muy preocupado por el espacio.

Answer 4

Riffing en la respuesta de Dani ...

En lugar de asignar muchas matrices de varios tamaños, lo que podría conducir a fragmentación de la memoria o patrones de acceso a caché extraños, podría asignar una matriz para contener los datos y una pequeña matriz para mantener los 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 usar la table como si fuera una matriz irregular como se muestra en la respuesta de Dani:

table[row][col] = foo;

Pero todos los datos están en un solo bloque, que de otro modo no podría depender de la estrategia de su asignador.

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

Answer 5

Si tiene N elementos, una matriz triangular inferior sin la diagonal principal tendrá (N - 1) * elementos N / 2, o (N + 1) * elementos N / 2 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 asignas 4 gigabytes en una máquina de 2.5 gigabytes, cortarlo a la mitad hace una gran diferencia).

Answer 6

Utilice una matriz irregular:

int N;
// populate N with size

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

se creará como matriz

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

Answer 7

El número de elementos únicos, m, debía representarse en una matriz simétrica n por n:

Con la diagonal principal.

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

Sin la diagonal (para la matriz simétrica, como lo describe el OP, se necesita la diagonal principal, pero solo para una buena medida ...)

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

No dividir entre 2 hasta la última operación es importante si se utiliza 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 x y la columna y en la matriz diagonal.

Índice en la memoria asignada, i, de la fila x y 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, voltea x e y en las ecuaciones. Para una matriz simétrica, simplemente elija x> = y o y> = x internamente y haga que las funciones de los miembros cambien según sea necesario.