He leído que si, por ejemplo, tengo un forbucle doble que se ejecuta sobre los índices de una matriz, entonces poner el índice de ejecución de la columna en el bucle externo es más eficiente. Por ejemplo:
a=zeros(1000);
for j=1:1000
for i=1:1000
a(i,j)=1;
end
end
¿Cuál es la forma más eficiente de codificarlo si tengo tres o más forbucles?
Por ejemplo:
a=zeros(100,100,100);
for j=1:100
for i=1:100
for k=1:100
a(i,j,k)=1;
end
end
end
matlab
efficiency
Tensor
fuente
fuente
Forlos bucles son muy lentos en MATLAB. Debe evitar bucles explícitos en MATLAB siempre que sea posible. En cambio, generalmente un problema puede expresarse en términos de operaciones de matriz / vector. Esa es la manera MATÁLICA. También hay muchas funciones incorporadas para inicializar matrices, etc. Por ejemplo, hay una función, ones () , que establecerá todos los elementos de una matriz en 1 (por extensión, a cualquier valor por multiplicación (un escalar multiplicado por la matriz de todos)). También funciona en matrices 3-D (que creo que cubre el ejemplo aquí).Respuestas:
Respuesta corta, desea tener el índice más a la izquierda en el bucle más interno. En su ejemplo, los índices de bucle serían k, j, i y los índices de matriz serían i, j, k. Esto tiene que ver con cómo MATLAB almacena las diferentes dimensiones en la memoria. Para más información, vea el # 13 de esta publicación de reddit .
fuente
Una respuesta algo más larga que explica por qué es más eficiente tener el índice más a la izquierda que varía más rápidamente. Hay dos cosas clave que debes entender.
Primero, MATLAB (y Fortran, pero no C y la mayoría de los otros lenguajes de programación) almacena las matrices en la memoria en "orden principal de columna". por ejemplo, si A es una matriz de 2 por 3 por 10, las entradas se almacenarán en la memoria en el orden
A (1,1,1)
A (2,1,1)
A (1,2,1)
A (2,2,1)
A (1,3,1)
A (2,3,1)
A (1,1,2)
A (2,1,2)
...
A (2,3,10)
Esta elección del orden principal de la columna es arbitraria: podríamos adoptar fácilmente una convención de "orden principal de fila", y de hecho eso es lo que se hace en C y en otros lenguajes de programación.
La segunda cosa importante que debe comprender es que los procesadores modernos no acceden a la memoria una ubicación a la vez, sino que cargan y almacenan "líneas de caché" de 64 o incluso 128 bytes contiguos (8 o 16 números de coma flotante de precisión doble) a la vez de memoria. Estos fragmentos de datos se almacenan temporalmente en una memoria caché rápida y se vuelven a escribir según sea necesario. (En la práctica, la arquitectura de caché ahora es bastante complicada con hasta 3 o 4 niveles de memoria caché, pero la idea básica se puede explicar con un caché de un nivel del tipo que tenían las computadoras en mi juventud).
Si los bucles están anidados para que el bucle más interno actualice el subíndice de fila, se accederá a las entradas de la matriz en el orden A (1,1), A (2,1), A (3,1), ... Cuando se accede a la primera entrada A (1,1), el sistema traerá una línea de caché que contiene A (1,1), A (2,1), ..., A (8,1) en el caché desde la memoria principal . Las siguientes 8 iteraciones del bucle más interno funcionan con estos datos sin ninguna transferencia de memoria principal adicional.
Si, como alternativa, estructuramos los bucles de modo que el índice de la columna varíe en el bucle más interno, entonces se accedería a las entradas de A en el orden A (1,1), A (1,2), A (1,3 ), ... En este caso, el primer acceso traería A (1,1), A (2,1), ..., A (8,1) al caché desde la memoria principal, pero 7/8 de Estas entradas no serían utilizadas. El acceso a A (1,2) en la segunda iteración traería otras 8 entradas desde la memoria principal, y así sucesivamente. En el momento en que el código comenzó a funcionar en la fila 2 de la matriz, la entrada A (2,1) podría eliminarse de la caché para dar paso a otros datos necesarios. Como resultado, el código genera 8 veces más tráfico que el necesario.
Algunos compiladores de optimización son capaces de reestructurar automáticamente los bucles para evitar este problema.
Muchos algoritmos de álgebra lineal numérica para la multiplicación y factorización de matrices se pueden optimizar para que funcionen de manera eficiente con el esquema de orden de filas principales o columnas principales, según el lenguaje de programación. Hacer esto de manera incorrecta puede tener un impacto negativo significativo en el rendimiento.
fuente