Acceder a elementos de una matriz por filas versus por columnas

3 minutos de lectura

avatar de usuario
algo-geeks

una matriz A[i][j] es dado. Si queremos sumar los elementos de la matriz, ¿qué método es mejor y por qué?

  1. columna sabia
  2. fila sabia

Desde mi punto de vista, la fila inteligente es mejor porque en la representación de la matriz los elementos se almacenan en ubicaciones de memoria contiguas, por lo que acceder a ellos lleva menos tiempo. Pero dado que en la RAM, obtener cada ubicación lleva el mismo tiempo, ¿importa?

  • Qué idioma estás usando? Diferentes lenguajes tienen diferentes representaciones para matrices, y eso afecta cómo deben usarse.

    – Karmastán

    17 de enero de 2011 a las 17:49

avatar de usuario
Tomás

Tomar ventaja de Localidad espacial

En C, las matrices se almacenan en rorden mayor. Así que si accedes al elemento a[i][j]un elemento de acceso a[i][j+1] es probable que golpee el caché. No se realizará ningún acceso a la memoria principal. Los cachés son más rápidos que la memoria principal, por lo que el patrón de acceso sí importa.

Por supuesto, se deben tener en cuenta más factores, como el acceso de escritura/acceso de lectura, la política de escritura (escritura simultánea, reescritura/asignación de escritura, asignación sin escritura), cachés multinivel, etc. Pero eso parece una exageración para esta pregunta.

Diviértete con una herramienta de creación de perfiles, como cachegrindy compruébelo usted mismo.

Por ejemplo, considere un programa ficticio que accede a matrices de 4 MB. Consulte las diferencias entre las tasas de fallas en cada patrón de acceso.

acceso a la columna

$ cat col_major.c 
#include <stdio.h>

int main(){

    size_t i,j;

    const size_t dim = 1024 ;

    int matrix [dim][dim];

    for (i=0;i< dim; i++){
        for (j=0;j <dim;j++){
            matrix[j][i]= i*j;
        }
    }
    return 0;
}

$ valgrind --tool=cachegrind ./col_major 

==3228== D   refs:      10,548,665  (9,482,149 rd   + 1,066,516 wr)
==3228== D1  misses:     1,049,704  (      968 rd   + 1,048,736 wr)
==3228== L2d misses:     1,049,623  (      893 rd   + 1,048,730 wr)
==3228== D1  miss rate:        9.9% (      0.0%     +      98.3%  )
==3228== L2d miss rate:        9.9% (      0.0%     +      98.3%  )

acceso a la fila

$ cat row_major.c 
#include <stdio.h>

int main(){
    size_t i,j;
    const size_t dim = 1024 ;
    int matrix [dim][dim];

    for (i=0;i< dim; i++)
        for (j=0;j <dim;j++)
            matrix[i][j]= i*j;

    return 0;
}

$ valgrind --tool=cachegrind ./row_major 

==3524== D   refs:      10,548,665  (9,482,149 rd   + 1,066,516 wr)
==3524== D1  misses:        66,664  (      968 rd   +    65,696 wr)
==3524== L2d misses:        66,583  (      893 rd   +    65,690 wr)
==3524== D1  miss rate:        0.6% (      0.0%     +       6.1%  )
==3524== L2d miss rate:        0.6% (      0.0%     +       6.1%  )

  • ¿Puedo preguntarle si fue su intención escribir i< dim y j <dim?

    – NiklasR

    15 de junio de 2012 a las 13:48

  • @Tom Si almacena sus matrices en columna principal, debe iterar sobre ellas en orden de columna principal, ¿verdad? Supongo que eso corregiría las fallas de caché, ¿o me estoy perdiendo algo?

    – Joren Heit

    16 de enero de 2013 a las 10:59

  • Esta pregunta está etiquetada como C, y C almacena arreglos multidimensionales en orden de fila principal. Si está utilizando algún otro lenguaje que hace el orden principal de las columnas, entonces sí, hacer toda una columna a la vez sería más rápido que hacer toda una fila a la vez.

    – Buge

    10 de abril de 2017 a las 6:23

Si las matrices son pequeñas, no es importante. Si son grandes, el tiempo de lectura puede verse afectado. El gran problema es el caché. Si no puede esperar que su matriz completa se cargue en el caché de una vez, entonces desea minimizar la cantidad de errores de caché que encuentre, porque lidiar con un error de caché lleva relativamente tiempo.

Si las matrices son realmente grandes, entonces podría recibir impactos de rendimiento aún mayores al causar más intercambio de páginas de lo necesario.

avatar de usuario
david harris

Para C, la mejor manera de manejar arreglos multidimensionales es:

int a[MAX_I][MAX_J];
for (i = 0; i < MAX_I; ++i) {
   for (j = 0; j < MAX_J; ++j) {
      /* process a[i][j] */
   }
}

La razón de esto es que el lenguaje C maneja las matrices como punteros con compensaciones, consulte: El lenguaje de programación C.

¿Ha sido útil esta solución?

Esta web utiliza cookies propias y de terceros para su correcto funcionamiento y para fines analíticos y para mostrarte publicidad relacionada con sus preferencias en base a un perfil elaborado a partir de tus hábitos de navegación. Al hacer clic en el botón Aceptar, acepta el uso de estas tecnologías y el procesamiento de tus datos para estos propósitos. Configurar y más información
Privacidad