¿Cuál es la forma más eficiente de escribir bucles 'for' en Matlab?

12

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
Tensor
fuente
44
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í).
Peter Mortensen
3
@PeterMortensen ¿Por qué factor (aproximadamente) la eficiencia de los bucles en Matlab es menor en comparación con C y Python? ¿Y por qué es eso? Además, ¿no ha mejorado la eficiencia de los bucles en Matlab en los últimos años?
TensoR
3
@PeterMortensen "por lo general, un problema puede expresarse en términos de operaciones de matriz / vector" - para ciertos valores de "generalmente", sí. En mi opinión, es más exacto decir que las personas que trabajan en Matlab y similares tienen una cultura de décadas de ignorar todas las cosas que no se pueden hacer con las operaciones de matriz / vector, tanto que todo parece un clavo para ese martillo. . Y no deberíamos decir simplemente “porque los bucles en Matlab son lentos” sino “Matlab es lento” (solo está vinculado a una biblioteca rápida de primitivas de LA escrita en C y Fortran).
Leftaroundabout
55
El rendimiento de for loops es controvertido: matlabtips.com/matlab-is-no-longer-slow-at-for-loops
realidad el
@leftaroundabout True. Estar preocupado por la velocidad en un lenguaje interpretado (o semiinterpretado) es una indicación bastante clara de que tiene un problema XY donde la solución real es "no use este lenguaje". La excepción, por supuesto, es si está utilizando la generación de código en Simulink, pero la pregunta es qué C construye el generador de código y qué tan eficiente es.
Graham

Respuestas:

18

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 .

whpowell96
fuente
2
O use las funciones integradas ones () .
Peter Mortensen
55
El ejemplo de @Peter OP es casi seguro que es solo un ejemplo de un bucle for que hace algo y no el caso de uso real.
Matt
@ Matt Estás en lo correcto.
TensoR
11

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).

A

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.

Brian Borchers
fuente