En C, existe una diferencia en el tiempo y el espacio entre una matriz m × n bidimensional frente a una matriz 1 dimensional de longitud m × n (para valores grandes de m y n)? ¿Los elementos de acceso serán más rápidos con una matriz de 1 dimensión?Rendimiento de matriz bidimensional vs matriz 1 dimensional
En C, las matrices bidimensionales son solo un ordenado esquema de indexación para matrices de 1-dimensión. Al igual que con una matriz 1D, las matrices 2D asignan un solo bloque de memoria contigua, y la notación A[row][col] es similar a decir A[row*NCOLS+col].
lo general, si se va a poner en práctica sus propias matrices multidimensionales utilizando matrices unidimensionales, que iba a escribir una función de indexación:
int getIndex(int row, int col) { return row*NCOLS+col; }
Suponiendo sus inlines compilador esta función, el rendimiento en este caso sería exactamente la misma que si usó la 'función de indexación' incorporada de las 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;
}
debe 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 AraKpointed out, si usted está saltando alrededor filas mucho , y las filas son muy grandes, podría golpear una gran cantidad de fallas de página ... en ese caso, el cust La función de indexación OM (con filas y columnas conmutadas) podría ayudar, pero también podría cambiar simplemente cuál de las dimensiones de una matriz bidimensional trata como filas y cuáles trata como columnas.
No creo que haya ninguna diferencia. Internamente, c trata una matriz bidimensional como varias matrices unidimensionales en secuencia.
Sin embargo, como con todas las prestaciones, su kilometraje puede variar. Puede haber algún tipo de diferencia aritmética puntero sutil. Ejecute pruebas cronometradas en ambos escenarios. Cualquiera que corra más rápido gana.
No se puede también aplicar las matrices de C como, por ejemplo, 'array' ** int y luego array' = malloc (sizeof (int *) * filas); para (i = 0; i
@derobert: Esa estructura a menudo se denomina "matriz desigual". Tiene un acceso sintáctico similar, pero en realidad no es lo mismo que una matriz bidimensional ordinaria. – dmckee
@dmckee harapiento o irregular? –
Solo estoy adivinando, pero diría que una matriz 1d es más rápida que una matriz 2d. Sin embargo, no sería mensurablemente más rápido. Un poco como $ 1,000,000.01 es más de $ 1,000,000.
Utilizaría lo que sea más fácil de codificar.
En realidad, si usa la denominada matriz bidimensional en C, el compilador hará la asignación en una matriz unidimensional por usted. Si usa una matriz unidimensional y le gusta tratarla como una de dos dimensiones, entonces usted debe escribir la asignación usted mismo.
Lo único que tiene que encargarse es acceder a la matriz en fila, porque el compilador de C almacenará su matriz bidimensional fila tras fila. Si accede a una matriz "grande" bidimensional en forma de columna, es probable que ocurran fallas de página. Incluso si está programando en un lenguaje que solo admite matrices unidimensionales, puede escribir fácilmente la asignación en cualquier cantidad de dimensiones.
Echa un vistazo a este artículo de Wikipedia si quieres hacer el mapping row-wise. Su mapeo podría ser en columnas, como matrices FORTRAN por ejemplo.
Robert es correcto.Las expresiones de indexación se compilan a las expresiones aritméticas del puntero y, por lo tanto, no hay diferencia.
¿Qué puede tener un impacto orden de acceso es, sin embargo, y por lo tanto es posible que desee poner en práctica las cosas a sí mismo para que pueda controlar el orden de acceso. Por ejemplo columna primero vs filas primeras formas.
En los procesadores modernos, el acceso a grandes conjuntos en varios pasos pueden tener diferencias inesperadas de rendimiento. El acceso secuencial es siempre el más rápido, y otros avances pueden ser hasta 30 veces más lentos debido a las interacciones de la memoria caché. Las matrices multidimensionales donde las dimensiones internas son una potencia de dos a menudo tienen un rendimiento deficiente debido a su forma de interactuar con la asociatividad de la memoria caché. Para comprender estos problemas, no existe un sustituto real para hacer mediciones.
No necesita escribir el suyo para decidir el diseño; el diseño del C incorporado está bien definido. Puede seleccionar cuál usar escribiendo 'array [row] [column]' vs. 'array [column] [row]' – derobert
Sí, eso es cierto. Debería haber dado un ejemplo mejor, como los diversos esquemas de matrices bloqueadas. –
Como dijo por otra, la diferencia realmente es la forma de acceder a sus elementos: lo que importa si cómo sus artículos son diseño en la memoria, que es lineal, por lo menos en arquitecturas comunes. Entonces todo lo que tiene realmente es 1d array, 2d, etc ... es "solo" una conveniencia, y un compilador razonable debería optimizar la indexación, pero en la práctica, una vez que tiene más de unas pocas variables, los compiladores a menudo fallan en el arco como x86 debido a la falta de registro.
Ahora, depende de su aplicación, pero creo que se debe pensar con un diseño 1d por defecto, sobre todo, si usted necesita para manejar múltiples dimensiones. El primer problema con las matrices multidimensionales en C es que no se pueden asignar dinámicamente; si se asignan por fila, tendrá un rendimiento horrible porque no tiene una pieza contigua de memoria. Vea el FFTW doc para detalles sobre esto.
Tenga en cuenta que siempre puede describir su única pieza de memoria con conveniente indexación de matriz en la parte superior (asigna un gran bloque de memoria nxm y luego crea una matriz de n puntero a cada fila).
Excelente explicación, ¡gracias! –