Jaki jest najbardziej efektywny sposób pisania pętli „for” w Matlabie?

12

Czytałem, że jeśli na przykład mam podwójną forpętlę, która przebiega nad indeksami macierzy, umieszczenie indeksu pracy kolumny w zewnętrznej pętli jest bardziej wydajne. Na przykład:

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

Jaki jest najskuteczniejszy sposób kodowania, jeśli mam trzy lub więcej forpętli?

Na przykład:

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
Napinacz
źródło
4
Forw MATLAB pętle są bardzo wolne. W miarę możliwości należy unikać jawnych pętli w MATLAB. Zamiast tego zwykle problem można wyrazić w postaci operacji macierzowych / wektorowych. To jest sposób MATLABIC. Istnieje również wiele wbudowanych funkcji do inicjalizacji macierzy itp. Na przykład istnieje funkcja, ones () , która ustawi wszystkie elementy macierzy na 1 (przez rozszerzenie, na dowolną wartość przez mnożenie (skalar) pomnożone przez macierz jedynek)). Działa również na tablicach 3-D (co myślę, że obejmuje tutaj przykład).
Peter Mortensen
3
@PeterMortensen Przez jaki czynnik (z grubsza) wydajność pętli w Matlabie jest mniejsza w porównaniu do C i Pythona? A dlaczego to? Ponadto, czy wydajność pętli w Matlabie nie poprawiła się w ciągu ostatnich kilku lat?
TensoR
3
@PeterMortensen „zwykle problem można wyrazić w postaci operacji macierzowych / wektorowych” - dla niektórych wartości „zwykle” tak. IMO dokładniej jest powiedzieć, że ludzie pracujący w Matlabie i tym podobnych mają dziesięciolecia kultury ignorowania wszystkich rzeczy, których nie można zrobić za pomocą operacji matrycowych / wektorowych, do tego stopnia, że ​​wszystko wygląda jak gwóźdź do tego młota . I nie powinniśmy po prostu mówić „bo pętle w Matlabie są wolne”, ale „Matlab jest wolny” (zdarza się to tylko w połączeniu z szybką biblioteką prymitywów LA napisanych w C i Fortranie).
leftaroundabout
5
Wydajność pętli for jest kontrowersyjna: matlabtips.com/matlab-is-no-longer-slow-at-for-loops
ohreally
@leftaroundabout True. Zaniepokojenie szybkością w tłumaczonym (lub częściowo zinterpretowanym) języku jest dość wyraźnym wskazaniem, że masz problem z XY, gdzie rzeczywistym rozwiązaniem jest „nie używaj tego języka”. Wyjątkiem jest oczywiście to, czy używasz generowania kodu w Simulink, ale pytanie brzmi: co C generuje kod i jak to jest wydajne.
Graham

Odpowiedzi:

18

Krótka odpowiedź, chcesz mieć lewy indeks w najbardziej wewnętrznej pętli. W twoim przykładzie indeksy pętli będą miały wartości k, j, i, a indeksami tablicowymi będą i, j, k. Ma to związek z tym, jak MATLAB przechowuje różne wymiary w pamięci. Aby uzyskać więcej, zobacz # 13 tego reddit postu .

whpowell96
źródło
2
Lub użyj wbudowanej funkcji one () .
Peter Mortensen
5
Przykład @Peter OP to prawie na pewno tylko zabawkowy przykład pętli for, która coś robi, a nie rzeczywisty przypadek użycia.
Matt
@Matt Masz rację.
TensoR
11

Nieco dłuższa odpowiedź, która wyjaśnia, dlaczego bardziej efektywne jest, aby lewy indeks najbardziej zmieniał się najszybciej. Są dwie kluczowe rzeczy, które musisz zrozumieć.

Po pierwsze, MATLAB (i Fortran, ale nie C i większość innych języków programowania) przechowuje tablice w pamięci w „porządku głównym kolumny”. np. jeśli A jest matrycą 2 na 3 na 10, wpisy zostaną zapisane w pamięci w kolejności

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)

Ten wybór kolejności głównej kolumny jest arbitralny - moglibyśmy z łatwością przyjąć konwencję „rzędu dużych zamówień”, a tak naprawdę dzieje się to w C i niektórych innych językach programowania.

Drugą ważną rzeczą, którą musisz zrozumieć, jest to, że współczesne procesory nie uzyskują dostępu do pamięci pojedynczej lokalizacji na raz, ale raczej ładują i przechowują „linie pamięci podręcznej” 64 lub nawet 128 ciągłych bajtów (8 lub 16 liczb zmiennoprzecinkowych podwójnej precyzji) naraz z pamięci. Te fragmenty danych są tymczasowo przechowywane w szybkiej pamięci podręcznej i zapisywane w razie potrzeby w razie potrzeby. (W praktyce architektura pamięci podręcznej jest teraz dość skomplikowana z aż 3 lub 4 poziomami pamięci podręcznej, ale podstawową ideę można wyjaśnić jednopoziomową pamięcią podręczną, taką jak komputery, które miałem w młodości).

A

Jeśli pętle są zagnieżdżone, aby wewnętrzna pętla aktualizowała indeks wiersza, wówczas dostęp do wpisów tablicy będzie możliwy w kolejności A (1,1), A (2,1), A (3,1), ... Kiedy dostęp do pierwszego wpisu A (1,1), system wprowadzi do pamięci podręcznej wiersz zawierający A (1,1), A (2,1), ..., A (8,1) . Kolejne 8 iteracji najbardziej wewnętrznej pętli działa na tych danych bez żadnych dodatkowych transferów pamięci głównej.

Jeśli alternatywnie, konstruujemy pętle w taki sposób, aby indeks kolumny zmieniał się w wewnętrznej pętli, wówczas wpisy A byłyby dostępne w kolejności A (1,1), A (1,2), A (1,3 ), ... W tym przypadku pierwszy dostęp wprowadziłby A (1,1), A (2,1), ..., A (8,1) do pamięci podręcznej z pamięci głównej, ale 7/8 z te wpisy nie zostaną wykorzystane. Dostęp do A (1,2) w drugiej iteracji przyniósłby wtedy kolejne 8 wpisów z pamięci głównej i tak dalej. Zanim kod zacznie działać w drugim rzędzie macierzy, wpis A (2,1) może zostać usunięty z pamięci podręcznej, aby zrobić miejsce dla innych potrzebnych danych. W rezultacie kod generuje 8-krotnie większy ruch, niż to konieczne.

Niektóre kompilatory optymalizujące są w stanie automatycznie restrukturyzować pętle, aby uniknąć tego problemu.

Wiele numerycznych algorytmów algebry liniowej do mnożenia i faktoryzacji macierzy można zoptymalizować w celu wydajnej pracy ze schematem porządkowania rzędów lub kolumn w zależności od języka programowania. Zrobienie tego w niewłaściwy sposób może mieć znaczący negatywny wpływ na wydajność.

Brian Borchers
źródło