Rendimiento de una matriz bidimensional frente a una matriz unidimensional
En C, ¿hay una diferencia en el tiempo y el espacio entre una matriz bidimensional m×n y una matriz unidimensional de longitud m×n (para valores grandes de myn)? ¿Será más rápido el acceso a los elementos con una matriz unidimensional?
En C, los arreglos bidimensionales son simplemente un esquema de indexación ordenado para arreglos unidimensionales. Al igual que con una matriz 1D, las matrices 2D asignan un único bloque de memoria contigua y la A[row][col]notación es similar a decirA[row*NCOLS+col] .
Por lo general, si implementaras tus propios arreglos multidimensionales usando arreglos unidimensionales, escribirías una función de indexación:
int getIndex(int row, int col) { return row*NCOLS+col; }
Suponiendo que su compilador incluya esta función, el rendimiento aquí sería exactamente el mismo que si utilizara la 'función de indexación' incorporada de matrices 2D.
Para ilustrar:
#define NROWS 10
#define NCOLS 20
Este:
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;
}
Debería realizar lo mismo que esto:
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;
}
Aunque, como señaló AraK , si saltas mucho entre filas y las filas son muy grandes, podrías encontrar muchos errores de página... en ese caso, la función de indexación personalizada (con filas y columnas intercambiadas) podría ayudar , pero también podría simplemente cambiar cuáles de las dimensiones de una matriz bidimensional trata como filas y cuáles como columnas.
En realidad, si utiliza la llamada matriz bidimensional en C, el compilador hará el mapeo en una matriz unidimensional por usted. Si utiliza una matriz unidimensional y desea tratarla como bidimensional, entonces debe escribir el mapeo usted mismo.
Lo único que debe tener en cuenta es acceder a la matriz fila por fila, porque el compilador de C almacenará su matriz bidimensional fila tras fila. Si accede a una matriz bidimensional "grande" por columnas, es probable que se produzcan errores de página. Incluso si está programando en un lenguaje que solo admite matrices unidimensionales, puede escribir fácilmente el mapeo en cualquier número de dimensiones.
Eche un vistazo a este artículo de Wikipedia si desea realizar el mapeo por filas . Su mapeo podría ser por columnas, como matrices FORTRAN, por ejemplo.
