In C, c'è una differenza di tempo e di spazio tra una matrice m × n bidimensionale rispetto a una matrice monodimensionale di lunghezza m × n (per grandi valori di me n)? L'accesso agli elementi sarà più veloce con un array monodimensionale?Prestazioni dell'array bidimensionale rispetto all'array 1-dimensionale
In C, gli array bidimensionali sono solo uno schema di indicizzazione accurato per gli array monodimensionali. Proprio come con un array 1D, gli array 2D allocano un singolo blocco di memoria contigua e la notazione A[row][col] è simile a A[row*NCOLS+col].
Di solito se si dovesse implementare i propri array multidimensionali utilizzando singole matrici tridimensionali, devi scrivere una funzione di indicizzazione:
int getIndex(int row, int col) { return row*NCOLS+col; }
Assumendo che il compilatore inline questa funzione, le prestazioni qui sarebbe esattamente la stessa se hai usato la "funzione di indicizzazione" incorporata degli array 2D.
Facciamo un esempio:
#define NROWS 10
#define NCOLS 20
questo:
int main(int argc, char *argv[]) {
int myArr[NROWS*NCOLS];
for (int i=0; i<NROWS; ++i) {
for (int j=0; j<NCOLS; ++j) {
myArr[getIndex(i,j)] = i+j;
}
}
return 0;
}
deve eseguire lo stesso di questo:
int main(int argc, char *argv[]) {
int myArr[NROWS][NCOLS];
for (int i=0; i<NROWS; ++i) {
for (int j=0; j<NCOLS; ++j) {
myArr[i][j] = i+j;
}
}
return 0;
}
Anche se, come AraKpointed out, se siete saltare le righe un sacco e le file sono molto grandi, potresti colmare un sacco di errori di pagina ... in tal caso la cust La funzione di indicizzazione om (con le righe e le colonne scambiate) potrebbe aiutare, ma potrebbe semplicemente cambiare quale delle dimensioni in un array bidimensionale trattate come le righe e quali trattate come colonne.
Non penso ci sia alcuna differenza. Internamente, c tratta una matrice bidimensionale come diversi array monodimensionali in sequenza.
Tuttavia, come per tutte le prestazioni, il tuo chilometraggio può variare. Potrebbe esserci una sorta di sottile differenza aritmetica puntatore. Esegui test a tempo su entrambi gli scenari. Chi corre più velocemente vince.
Non è possibile implementare anche array in C come ad esempio 'int ** array' e quindi' array = malloc (sizeof (int *) * rows); for (i = 0; i
@derobert: Quella struttura viene spesso chiamata "matrice frammentata". Ha un accesso sintattico simile, ma in realtà non è lo stesso di un normale array 2d. – dmckee
@dmckee irregolare o frastagliato? –
Sto solo supponendo, ma direi che un array 1d è più veloce di un array 2d. Tuttavia, non sarebbe misurabilmente più veloce. Un po 'come $ 1,000,000.01 è più di $ 1,000,000.
Vorrei usare tutto ciò che è più facile da codificare.
In realtà, se si utilizza la cosiddetta matrice bidimensionale in C, il compilatore eseguirà il mapping in un array monodimensionale. Se utilizzi un array monodimensionale e ti piace considerarlo bidimensionale, devi scrivere tu stesso la mappatura.
L'unica cosa che devi fare è che devi accedere all'array in termini di righe, perché il compilatore C memorizzerà l'array bidimensionale riga dopo riga. Se si accede a un array di colonne bidimensionale "grande", è probabile che si verifichino errori di pagina. Anche se si sta programmando in linguaggio che supporta solo array monodimensionali, è possibile scrivere facilmente la mappatura in qualsiasi numero di dimensioni.
Dai un'occhiata a questo articolo di Wikipedia se vuoi fare lo mapping row-wise. La mappatura potrebbe essere a livello di colonna, come ad esempio le matrici FORTRAN.
Robert è corretto.Le espressioni di indicizzazione sono compilate per indicare le espressioni aritmetiche e quindi non c'è differenza.
Ciò che può avere un impatto è comunque l'ordine di accesso, quindi è consigliabile implementare le cose da soli in modo da poter controllare l'ordine di accesso. Ad esempio prima colonna vs prima riga forme.
Sui processori moderni, l'accesso a grandi array a vari passi può avere differenze di prestazioni impreviste. L'accesso sequenziale è sempre più veloce e le altre falcate possono essere fino a 30 volte più lente a causa delle interazioni nella cache. Gli array multidimensionali in cui le dimensioni interne sono una potenza di due spesso hanno prestazioni scadenti a causa del modo in cui interagiscono con l'associatività della cache. Per capire questi problemi non c'è un vero sostituto per fare misurazioni.
Non è necessario scrivere il proprio per decidere il layout; il layout del built-in C è ben definito. Puoi scegliere quale usare scrivendo 'array [row] [column]' vs. 'array [column] [row]' – derobert
Sì, è vero. Avrei dovuto dare un esempio migliore come i vari schemi per le matrici bloccate. –
Come detto da altri, la differenza è in realtà il modo in cui si accede ai tuoi articoli: ciò che conta è se i tuoi articoli sono disposti nella memoria, che è lineare, almeno su architetture comuni. Quindi tutto quello che hai veramente è un array 1d, il 2d, ecc ... è "solo" una comodità, e un compilatore ragionevole dovrebbe ottimizzare l'indicizzazione - ma in pratica, una volta che hai più di poche variabili, i compilatori spesso falliscono nell'arco come x86 a causa della fame di registro.
Ora, dipende dall'applicazione, ma penso che dovresti pensare con un layout 1d per impostazione predefinita, specialmente se devi gestire più dimensioni. Il primo problema con gli array multidimensionali in C è che non è possibile allocarli dinamicamente: se si allocano su una base per riga, si avranno prestazioni pessime perché non si dispone di una memoria contigua. Vedere lo FFTW doc per i dettagli su questo.
Si noti che è sempre possibile descrivere il singolo pezzo di memoria con l'indicizzazione di array conveniente su di esso (allocare un blocco di memoria grande nxm e quindi creare un array di n puntatore su ogni riga).
Ottima spiegazione, grazie! –