¿Cómo almacenar una matriz simétrica?

Question

¿Cuál es la mejor manera de almacenar una matriz simétrica en la memoria?

Sería bueno ahorrar la mitad del espacio sin comprometer demasiado la velocidad y la complejidad de la estructura. Esta es una pregunta independiente del lenguaje, pero si necesita hacer algunas suposiciones simplemente asuma que es un buen viejo lenguaje de programación simple como C o C++.

Parece una cosa que tiene sentido solo si hay una manera de mantener cosas simples o solo cuando la matriz en sí misma es realmente grande, ¿estoy en lo cierto?

Sólo por el bien de formalidad quiero decir que esta afirmación es siempre cierto para los datos que yo quiero para almacenar

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

Answer 1

encuentro que muchos paquetes de alto rendimiento simplemente almacenan toda la matriz, pero luego solo leen el triángulo superior o el triángulo inferior. Luego pueden usar el espacio adicional para almacenar datos temporales durante el cálculo.

Sin embargo, si el almacenamiento es realmente un problema, simplemente almacene los elementos n(n+1)/2 que forman el triángulo superior en una matriz unidimensional. Si eso hace que el acceso sea complicado para usted, simplemente defina un conjunto de funciones auxiliares.

En C para acceder a una matriz matA se podría definir una macro:

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

continuación, puede acceder a su gama casi normalmente.

Answer 2

Bueno me gustaría probar una matriz triangular, como esto:

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

Pero entonces tendrás que enfrentar el problema cuando alguien quiera acceder al "otro lado". Por ejemplo, quiere acceder a [0] [10] pero en su caso este valor se almacena en [10] [0] (suponiendo 10x10).

Probablemente la "mejor" manera es la de latencia: no haga nada hasta que el usuario lo solicite. De modo que podría cargar la fila específica si el usuario escribe algo como imprimir (matriz [4]).

Answer 3

Si está utilizando algo que admita la sobrecarga del operador (por ejemplo, C++), es bastante fácil de manejar esto de forma transparente. Basta con crear una clase de matriz que controla los dos subíndices, y si el segundo es mayor que la primera, intercambiarlos:

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

Por el momento me he saltado por encima de todo lo demás, y acaba de cubrir el subíndice. En realidad, para manejar el uso tanto como lvalue como rvalue correctamente, normalmente querrá devolver un proxy en lugar de una T directamente. Querrá un ctor que cree data como un triángulo (es decir, para una matriz NxN, la primera fila tendrá N elementos, la segunda N-1, y así sucesivamente - o, equivalentemente 1, 2, ... N) También puede considerar crear data como un solo vector - tiene que calcular el desplazamiento correcto en él, pero eso no es terriblemente difícil, y utilizará un poco menos de memoria, ejecutará un poco más rápido, etc. Utilizaría el sencillo código para la primera versión, y optimice más tarde si es necesario.

Answer 4

Puede usar una matriz escalonada (o como se llamen) si su idioma lo admite, y cuando x < y, cambie la posición de xey. Así que ...

Pseudocódigo (un poco de estilo de Python, pero no realmente) para una matriz nxn:

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] 

Y a continuación, cuando se hace referencia a los valores ....

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

Answer 5

Si desea utilizar una matriz unidimensional el código sería algo como esto:

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

Usted puede deshacerse de las multiplicaciones si crea una tabla de consulta adicional:

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 6

Aquí es un buen método para almacenar una matriz simétrica, que sólo requiere N (N + 1)/2 memoria:

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

Para algunos matriz triangular

0 1 2 3 
    4 5 6 
    7 8 
     9 

representación 1D (almacenado en std::vector, por ejemplo) se parece a la siguiente:

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

Y llama fromMatrixToVector (1, 2, 4) devuelve 5, por lo que la matriz datos es vector [5] -> 5.

Para más información ver http://www.codeguru.com/cpp/cpp/algorithms/general/article.php/c11211/TIP-Half-Size-Triangular-Matrix.htm