modo efficiente per rappresentare una matrice triangolare inferiore/superiore

Question

Sto lavorando sui miei dati in un programma C/C++, che è bidimensionale. Qui il mio valore è calcolato per coppia e qui i valori sarebbero gli stessi per foo[i][j] e foo[j][i].

Quindi se lo implemento utilizzando un semplice array bidimensionale, metà del mio spazio sarebbe sprecato. Quindi quale sarebbe la migliore struttura dati per rappresentare questa matrice triangolare inferiore/superiore.

saluti,

Answer 1

Davvero, si sta meglio fuori usando solo un normale due matrice tridimensionale. La RAM è piuttosto economica. Se davvero non vuoi farlo, allora puoi costruire un array monodimensionale con il giusto numero di elementi e poi capire come accedere a ciascun elemento. Ad esempio, se la matrice è strutturata in questo modo:

j 
    1234 
i 1 A 
    2 BC 
    3 DEF 
    4 GHIJ 

e lo avete memorizzato come un array monodimensionale, da sinistra a destra, ci si accede elemento C(2, 2) con array[3]. Puoi calcolare una funzione per passare da [i][j] a [n] ma non voglio rovinare il tuo divertimento. Ma non devi farlo a meno che l'array triangolare in questione sia davvero enorme o tu sia molto preoccupato per lo spazio.

Answer 2

Utilizzare una matrice irregolare:

int N; 
// populate N with size 

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

creerà serie come

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

Answer 3

Se si dispone di N elementi allora una matrice triangolare inferiore senza la diagonale principale avrà (N - 1) * N/2 elementi o (N + 1) * N/2 elementi con la diagonale principale. Senza la diagonale principale, (I, J) (I, J ∈ 0..N-1, I> J) ⇒ (I * (I - 1)/2 + J). Con la diagonale principale, (I, J ∈ 0..N-1, I ≥ J) ⇒ ((I + 1) * I/2 + J).

(E sì, quando si sta assegnando 4 gigabyte su una macchina da 2,5 gigabyte, tagliandola a metà non fare una differenza enorme.)

Answer 4

Il numero di elementi unici, m, necessarie per essere rappresentato in un n da matrice simmetrica n:

Con diagonale principale

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

Senza la diagonale (per matrice simmetrica come OP descrive, principale la diagonale è necessaria, ma solo per una buona misura ...)

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

Non dividendo per 2 fino a quando l'ultima operazione è importante se viene utilizzato l'aritmetico intero con troncamento.

È inoltre necessario eseguire un po 'di aritmetica per trovare l'indice, i, nella memoria allocata corrispondente alla riga x e alla colonna y nella matrice diagonale.

indice nella memoria allocata, i, di righe x e colonna y della matrice diagonale superiore:

Con la diagonale

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

Senza la diagonale

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

Per matrice diagonale inferiore capovolgi x e y nelle equazioni. Per una matrice simmetrica, scegli x> = y o y> = x internamente e fai ruotare le funzioni membro secondo necessità.

Answer 5

riffing sulla risposta di Dani ...

Invece di allocare molti array di varie dimensioni, che potrebbero portare a modelli di frammentazione della memoria o di accesso cache di strano, si potrebbe allocare un array per contenere i dati e una piccola serie di tieni puntatori alle righe all'interno della prima allocazione.

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

Ora è possibile utilizzare table come se fosse una matrice irregolare come indicato nella risposta di Dani:

table[row][col] = foo; 

Ma tutti i dati sono in un unico blocco, che potrebbe non essere altrimenti a seconda la strategia del tuo allocatore.

L'utilizzo della tabella dei puntatori di riga può essere o meno più veloce del calcolo dell'offset utilizzando la formula di Praxeolitic.

Answer 6

In risposta di Adrian McCarthy, sostituire

p += side - row; 

con

p += row + 1; 

per una matrice triangolare inferiore anziché uno superiore.

Answer 7

Come Dan e Praxeolitic hanno proposto una matrice triangolare inferiore con una regola di transizione diagonale ma corretta.

Per la matrice n per n è necessario il numero di serie (n+1)*n/2 e la regola di transizione è 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]; 
    }; 
}; 

ho fatto con double ma si può fare come template. Questo è solo uno scheletro di base quindi non dimenticare di implementare il distruttore.