Qual é a maneira mais eficiente de escrever loops 'for' no Matlab?

Eu li que, por exemplo, se eu tenho um forloop duplo que percorre os índices de uma matriz, é mais eficiente colocar o índice de execução da coluna no loop externo. Por exemplo:

a=zeros(1000);
for j=1:1000
 for i=1:1000
  a(i,j)=1;
 end
end

Qual é a maneira mais eficiente de codificá-lo se eu tiver três ou mais forloops?

Por exemplo:

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

Resposta curta: você deseja ter o índice mais à esquerda no loop mais interno. No seu exemplo, os índices de loop iriam k, j, ie os índices da matriz seriam i, j, k. Isso tem a ver com a maneira como o MATLAB armazena as diferentes dimensões na memória. Para mais, consulte o item 13 desta publicação do reddit .

Uma resposta um pouco mais longa que explica por que é mais eficiente ter o índice mais à esquerda variando mais rapidamente. Há duas coisas importantes que você precisa entender.

Primeiro, o MATLAB (e o Fortran, mas não o C e a maioria das outras linguagens de programação) armazena matrizes na memória na "ordem principal da coluna". por exemplo, se A é uma matriz de 2 por 3 por 10, as entradas serão armazenadas na memória na ordem

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)

Essa escolha da ordem principal da coluna é arbitrária - poderíamos adotar facilmente uma convenção de "ordem principal da linha" e, de fato, é isso que é feito em C e em algumas outras linguagens de programação.

A segunda coisa importante que você precisa entender é que os processadores modernos não acessam a memória um local por vez, mas carregam e armazenam "linhas de cache" de 64 ou até 128 bytes contíguos (8 ou 16 números de ponto flutuante de precisão dupla) de cada vez da memória. Esses pedaços de dados são armazenados temporariamente em um cache de memória rápido e gravados de volta conforme necessário. (Na prática, a arquitetura de cache agora é bastante complicada com até 3 ou 4 níveis de memória cache, mas a idéia básica pode ser explicada com um cache de um nível, do tipo que os computadores tinham nos meus dias mais novos.)

$A$

Se os loops estiverem aninhados para que o loop mais interno atualize o subscrito da linha, as entradas da matriz serão acessadas na ordem A (1,1), A (2,1), A (3,1), ... Quando a primeira entrada A (1,1) é acessada, o sistema trará uma linha de cache contendo A (1,1), A (2,1), ..., A (8,1) para o cache da memória principal . As próximas 8 iterações do loop mais interno funcionam nesses dados sem transferências adicionais de memória principal.

Se, em alternativa, estruturarmos os loops para que o índice da coluna varie no loop mais interno, as entradas de A serão acessadas na ordem A (1,1), A (1,2), A (1,3 ), ... Nesse caso, o primeiro acesso traria A (1,1), A (2,1), ..., A (8,1) para o cache da memória principal, mas 7/8 de essas entradas não seriam usadas. O acesso a A (1,2) na segunda iteração traria outras 8 entradas da memória principal e assim por diante. Quando o código começa a trabalhar na linha 2 da matriz, a entrada A (2,1) pode ser liberada do cache para abrir caminho para outros dados necessários. Como resultado, o código está gerando 8 vezes o tráfego necessário.

Alguns compiladores de otimização são capazes de reestruturar loops automaticamente para evitar esse problema.

Muitos algoritmos de álgebra linear numérica para multiplicação e fatoração de matrizes podem ser otimizados para trabalhar eficientemente com o esquema de ordenação de linhas principais ou de colunas principais, dependendo da linguagem de programação. Fazer isso da maneira errada pode ter um impacto negativo significativo no desempenho.