Comment stocker une matrice symétrique?

Question

Quel est le meilleur moyen de stocker une matrice symétrique en mémoire?

Il serait bon de sauver la moitié de l'espace sans compromettre la vitesse et de la complexité de la structure trop. Il s'agit d'une question indépendante des langages, mais si vous avez besoin de faire des suppositions, supposez que c'est un bon vieux langage de programmation simple comme C ou C++.

Il semble que quelque chose ait un sens juste s'il y a un moyen de garder choses simples ou juste quand la matrice elle-même est vraiment grande, ai-je raison?

juste pour le plaisir de formalité, je veux dire que cette affirmation est toujours vrai pour les données que je veux stocker

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

Answer 1

Je trouve que beaucoup de paquets de haute performance stockent juste la matrice entière, mais seulement lisent le triangle supérieur ou le triangle inférieur. Ils pourraient alors utiliser l'espace supplémentaire pour stocker des données temporaires pendant le calcul.

Toutefois, si le stockage est vraiment un problème alors juste stocker les éléments qui n(n+1)/2 le triangle supérieur dans un tableau à une dimension. Si cela vous complique l'accès, définissez simplement un ensemble de fonctions auxiliaires.

En C pour accéder à une matrice matA vous pouvez définir une macro:

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

alors vous pouvez accéder à votre tableau presque normalement.

Answer 2

Eh bien je tenterais une matrice triangulaire, comme ceci:

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

Mais alors vous devrez faire face au problème quand quelqu'un veut accéder à "l'autre côté". Par exemple, il veut accéder à [0] [10] mais dans votre cas, ce val est stocké dans [10] [0] (en supposant 10x10).

Le probablement « meilleur » moyen est paresseux un - ne rien faire jusqu'à ce que les demandes des utilisateurs. Vous pouvez donc charger la ligne spécifique si l'utilisateur tape quelque chose comme print (matrix [4]).

Answer 3

Si vous utilisez quelque chose qui prend en charge la surcharge des opérateurs (par exemple C++), il est assez facile de gérer cette transparence. Il suffit de créer une classe de matrice qui vérifie les deux indices, et si le second est supérieur au premier, les échanger:

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

Pour le moment, je l'ai sauté sur tout le reste, et juste couvert la subscripting. En réalité, pour gérer correctement l'utilisation à la fois comme lvalue et comme valeur, vous souhaiterez généralement renvoyer un proxy au lieu d'un T directement. Vous aurez besoin d'un cteur qui crée data comme un triangle (ie pour une matrice NxN, la première ligne aura des éléments N, le second N-1, et ainsi de suite - ou, equivalantly 1, 2, ... N). Vous pouvez également envisager de créer data comme une seule vector - vous devez calculer le décalage correct en elle, mais ce n'est pas très difficile, et il utilisera un peu moins de mémoire, courir un peu plus vite, etc. J'utilise simple code pour la première version, et optimiser plus tard si nécessaire.

Answer 4

Vous pouvez utiliser un tableau en quinconce (ou quel que soit son nom) si votre langue le prend en charge, et lorsque x < y, changez la position de x et y. Alors ...

pseudocode (un peu de style Python, mais pas vraiment) pour une matrice 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] 

Et puis en se référant à des valeurs ....

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

Answer 5

Si vous souhaitez utiliser un tableau à deux dimensions le code ressemblerait à quelque chose comme ceci:

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

Vous pouvez vous débarrasser des multiplications si vous créez une table de consultation supplémentaire:

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

Voici une bonne méthode pour stocker une matrice symétrique, il ne nécessite que N (N + 1)/2 mémoire:

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

Pour une matrice triangulaire

0 1 2 3 
    4 5 6 
    7 8 
     9 

représentation 1D (stocké dans std::vector, par exemple) ressemble comme suit:

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

Et appelez fromMatrixToVector (1, 2, 4) renvoie 5, de sorte que la matrice données est vecteur [5] -> 5.

Pour plus d'informations, voir http://www.codeguru.com/cpp/cpp/algorithms/general/article.php/c11211/TIP-Half-Size-Triangular-Matrix.htm