Główna kolejność wierszy i kolumn - Row- and column-major order

Ilustracja różnicy między porządkowaniem wierszy i kolumn głównych

W komputerowych, wiersz znaczne zamówienie i kolumny głównym celu są sposoby przechowywania wielowymiarowych tablic w pamięci liniowej, takich jak pamięci o dostępie swobodnym .

Różnica między zamówieniami polega na tym, które elementy tablicy są ciągłe w pamięci. W kolejności wiersz-główny, kolejne elementy wiersza znajdują się obok siebie, podczas gdy to samo dotyczy kolejnych elementów kolumny w kolejności kolumnowej-głównej. Podczas gdy terminy nawiązują do wierszy i kolumn tablicy dwuwymiarowej, tj. macierzy , rzędy można uogólnić na tablice o dowolnym wymiarze, zauważając, że terminy wiersz-major i kolumna-major są równoważne rzędom leksykograficznym i koleksykograficznym , odpowiednio.

Układ danych ma kluczowe znaczenie dla prawidłowego przekazywania tablic między programami napisanymi w różnych językach programowania. Jest to również ważne dla wydajności podczas przechodzenia przez tablicę, ponieważ nowoczesne procesory przetwarzają dane sekwencyjne wydajniej niż dane niesekwencyjne. Wynika to przede wszystkim z buforowania procesora, które wykorzystuje przestrzenną lokalizację odniesienia . Ponadto ciągły dostęp umożliwia korzystanie z instrukcji SIMD operujących na wektorach danych. W przypadku niektórych nośników, takich jak taśma lub pamięć flash NAND , dostęp sekwencyjny jest o rząd wielkości szybszy niż dostęp niesekwencyjny.

Wyjaśnienie i przykład

Terminy wiersz-dur i kolumna-dur wywodzą się z terminologii związanej z porządkowaniem obiektów. Ogólnym sposobem porządkowania obiektów z wieloma atrybutami jest najpierw pogrupowanie i uporządkowanie według jednego atrybutu, a następnie, w ramach każdej takiej grupy, pogrupowanie i uporządkowanie według innego atrybutu itd. Jeśli w porządkowaniu uczestniczy więcej niż jeden atrybut, pierwszy nazywać się major i ostatni minor . Jeśli w porządkowaniu uczestniczą dwa atrybuty, wystarczy nazwać tylko główny atrybut.

W przypadku tablic atrybutami są indeksy wzdłuż każdego wymiaru. Do matryc w notacji matematycznej, pierwszy wskaźnik wskazuje rząd , a drugi oznacza kolumnę , na przykład, biorąc pod uwagę macierz , jest w pierwszym rzędzie i drugiej kolumnie. Konwencja ta została przeniesiona do składni w językach programowania, chociaż często indeksy zaczynają się od 0 zamiast 1. ${\ Displaystyle A}$${\ Displaystyle a_ {1,2}}$

Mimo że wiersz jest wskazywany przez pierwszy indeks, a kolumna przez drugi indeks, nie wynika z tego kolejność grupowania między wymiarami. Wybór sposobu grupowania i porządkowania indeksów, czy to metodą wierszową, czy kolumnową, jest więc kwestią umowną. Tę samą terminologię można zastosować do tablic o jeszcze wyższych wymiarach. Row-major grupowanie rozpoczyna się od skrajnej lewej indeksu i kolumny-dur z prawej skrajnej indeksu, prowadzące do leksykograficznego i colexicographic (lub Colex) zamówień , odpowiednio.

Na przykład tablica

${\ Displaystyle A = {\ zacząć {bmatrix} a_ {11} i a_ {12} i a_ {13} \ \ a_ {21} i a_ {22} i a_ {23} \ koniec {bmatrix}}}$

można przechowywać na dwa sposoby:

Adres	Wiersz-główne zamówienie	Kolumna-główne zamówienie
0	${\ Displaystyle a_ {11}}$	${\ Displaystyle a_ {11}}$
1	${\ Displaystyle a_ {12}}$	${\ Displaystyle a_ {21}}$
2	${\ Displaystyle a_ {13}}$	${\ Displaystyle a_ {12}}$
3	${\ Displaystyle a_ {21}}$	${\ Displaystyle a_ {22}}$
4	${\ Displaystyle a_ {22}}$	${\ Displaystyle a_ {13}}$
5	${\ Displaystyle a_ {23}}$	${\ Displaystyle a_ {23}}$

Różne języki programowania radzą sobie z tym na różne sposoby. W języku C tablice wielowymiarowe są przechowywane w kolejności wiersz-główny, a indeksy tablicy zapisywane są od pierwszego wiersza (kolejność dostępu leksykograficznego):

C: rząd główny (leksykograficzny porządek dostępu), indeksowanie od zera

Adres	Dostęp	Wartość
0	A[0][0]	${\ Displaystyle a_ {11}}$
1	A[0][1]	${\ Displaystyle a_ {12}}$
2	A[0][2]	${\ Displaystyle a_ {13}}$
3	A[1][0]	${\ Displaystyle a_ {21}}$
4	A[1][1]	${\ Displaystyle a_ {22}}$
5	A[1][2]	${\ Displaystyle a_ {23}}$

Z drugiej strony w Fortranie tablice są przechowywane w kolejności kolumnowej, podczas gdy indeksy tablic są nadal zapisywane w kolejności od pierwszego wiersza (koleksykograficzna kolejność dostępu):

Fortran: kolejność kolumn-główna (kolejnograficzna kolejność dostępu), indeksowanie oparte na jedynce

Adres	Dostęp	Wartość
1	A(1,1)	${\ Displaystyle a_ {11}}$
2	A(2,1)	${\ Displaystyle a_ {21}}$
3	A(1,2)	${\ Displaystyle a_ {12}}$
4	A(2,2)	${\ Displaystyle a_ {22}}$
5	A(1,3)	${\ Displaystyle a_ {13}}$
6	A(2,3)	${\ Displaystyle a_ {23}}$

Zwróć uwagę, jak użycie A[i][j]z indeksowaniem wieloetapowym, jak w C, w przeciwieństwie do neutralnej notacji, jak A(i,j)w Fortranie, prawie nieuchronnie implikuje porządek wiersz-główny ze względów składniowych, że tak powiem, ponieważ można go przepisać jako (A[i])[j], a A[i]wiersz część można nawet przypisać do zmiennej pośredniej, która jest następnie indeksowana w oddzielnym wyrażeniu. (Nie należy zakładać żadnych innych implikacji, np. Fortran nie jest kolumną główną po prostu ze względu na jej notację, a nawet powyższa implikacja może zostać celowo ominięta w nowym języku.)

Aby użyć porządku kolumna-główna w środowisku wiersza-głównego lub odwrotnie, z jakiegokolwiek powodu, jednym obejściem jest przypisanie niekonwencjonalnych ról do indeksów (używając pierwszego indeksu dla kolumny i drugiego indeksu dla wiersza), a innym jest ominięcie składni języka poprzez jawne obliczenie pozycji w jednowymiarowej tablicy. Oczywiście odejście od konwencji wiąże się zapewne z kosztem, który wzrasta wraz ze stopniem niezbędnej interakcji z konwencjonalnymi funkcjami języka i innym kodem, nie tylko w postaci zwiększonej podatności na błędy (zapominając także o odwróceniu kolejności mnożenia macierzy, powrót do konwencji podczas kodu konserwacja itp.), ale także w postaci konieczności aktywnego przestawiania elementów, z których wszystkie muszą być brane pod uwagę w stosunku do pierwotnego celu, takiego jak zwiększenie wydajności. Uruchamianie pętli w wierszach jest preferowane w językach z głównymi wierszami, takich jak C i na odwrót w przypadku języków z głównymi kolumnami.

Języki programowania i biblioteki

Języki programowania lub ich standardowe biblioteki, które obsługują tablice wielowymiarowe, zazwyczaj mają dla tych tablic natywną kolejność przechowywania głównych wierszy lub kolumn.

Porządek rzędów głównych jest używany w językach C / C++ / Objective-C (dla tablic w stylu C), PL/I , Pascal , Speakeasy , SAS i Rasdaman .

Porządek główny kolumna jest używany w Fortran , MATLAB , GNU Octave , S-Plus , R , Julia i Scilab .

Ani wiersz-główny, ani kolumna-główny

Typową alternatywą dla gęstego przechowywania tablic jest użycie wektorów Iliffe , które zazwyczaj przechowują wskaźniki do elementów w tym samym wierszu w sposób ciągły (jak wiersz główny), ale nie same wiersze. Są one używane w (uporządkowanych według wieku): Java , C# / CLI / .Net , Scala i Swift .

Nawet mniej gęsta jest użycie list list, na przykład w Pythonie , aw Wolfram Języka od Wolfram Mathematica .

Alternatywne podejście wykorzystuje tabele tabel, np. w Lua .

Biblioteki zewnętrzne

Wsparcie dla tablic wielowymiarowych mogą być również zapewniane przez biblioteki zewnętrzne, które mogą nawet obsługiwać dowolne porządkowanie, gdzie każdy wymiar ma wartość kroku, a wiersz-major lub column-major to tylko dwie możliwe interpretacje wynikowe.

Kolejność rzędów głównych jest domyślna w NumPy (dla Pythona).

Kolumna-główna kolejność jest domyślna w Eigen i Armadillo (oba dla C++).

Szczególnym przypadkiem byłby OpenGL (i OpenGL ES ) do przetwarzania grafiki. Ponieważ „ostatnie zabiegi matematyczne dotyczące algebry liniowej i powiązanych pól niezmiennie traktują wektory jako kolumny”, projektant Mark Segal postanowił zastąpić to konwencją w poprzedniku IRIS GL , która polegała na zapisaniu wektorów jako wierszy; ze względu na zgodność, macierze transformacji nadal byłyby przechowywane w kolejności wektora-głównego (=wiersz-główny), a nie współrzędnej-głównej (=kolumna-główna), a następnie użył sztuczki „[że] powiedzieć, że macierze w OpenGL są przechowywane w kolumna-główny porządek". Było to tak naprawdę istotne tylko w przypadku prezentacji, ponieważ mnożenie macierzy było oparte na stosie i nadal można je interpretować jako post mnożenie, ale, co gorsza, rzeczywistość wyciekła przez API oparte na C, ponieważ dostęp do poszczególnych elementów byłby możliwy jako M[vector][coordinate]lub, w rzeczywistości, M[column][row], który niestety pomyliła konwencję, którą projektant chciał przyjąć, i została ona nawet zachowana w dodanym później języku cieniowania OpenGL (chociaż umożliwia to również dostęp do współrzędnych po nazwie, np M[vector].y. ). W rezultacie wielu programistów po prostu zadeklaruje teraz, że posiadanie kolumny jako pierwszego indeksu jest definicją kolumny głównej, chociaż wyraźnie nie jest tak w przypadku prawdziwego języka głównego kolumny, takiego jak Fortran.

Pochodnia (dla Lua) zmieniona z domyślnej kolejności kolumna-główna na wiersz-główna.

Transpozycja

Ponieważ wymiana indeksów tablicy jest istotą transpozycji tablicy , tablica przechowywana jako wiersz-główny, ale odczytywana jako kolumna-główna (lub odwrotnie) będzie wyświetlana jako transponowana (o ile macierz jest kwadratowa). Ponieważ faktycznie przeprowadzanie tego przegrupowania w pamięci jest zazwyczaj kosztowną operacją, niektóre systemy zapewniają opcje określania poszczególnych macierzy jako przechowywanych transponowanych. Programista musi następnie zdecydować, czy zmienić kolejność elementów w pamięci, na podstawie rzeczywistego użycia (w tym liczby ponownego użycia tablicy w obliczeniach).

Na przykład, funkcje podstawowych podprogramów algebry liniowej otrzymują flagi wskazujące, które tablice są transponowane.

Ogólne obliczanie adresu

Koncepcja uogólnia się na tablice o więcej niż dwóch wymiarach.

Dla d- wymiarowej tablicy o wymiarach N _k ( k =1... d ), dany element tej tablicy jest określony przez krotkę indeksów d ( liczonych od zera) . ${\ Displaystyle N_ {1} \ razy N_ {2} \ razy \ cdots \ razy N_ {d}}$ ${\displaystyle (n_{1},n_{2},\ldots,n_{d})}$${\ Displaystyle n_ {k} \ w [0, N_ {k}-1]}$

W porządku wiersz-główny ostatni wymiar jest ciągły, tak że przesunięcie pamięci tego elementu jest określone przez:

${\ Displaystyle n_ {d} + N_ {d} \ cdot (n_ {d-1} + N_ {d-1} \ cdot (n_ {d-2} + N_ {d-2}) \ cdot (\ cdots + N_{2}n_{1})\cdots)))=\sum _{k=1}^{d}\left(\prod _{\ell =k+1}^{d}N_{\ell } \right)n_{k}}$

W porządku kolumnowym, pierwszy wymiar jest ciągły, tak że przesunięcie pamięci tego elementu jest określone wzorem:

${\displaystyle n_{1}+N_{1}\cdot (n_{2}+N_{2}\cdot (n_{3}+N_{3}\cdot (\cdots +N_{d-1}n_{) d})\cdots )))=\sum _{k=1}^{d}\left(\prod _{\ell =1}^{k-1}N_{\ell }\right)n_{k }}$

gdzie pusty produkt jest multiplikatywnym elementem tożsamości , czyli . ${\ Displaystyle \ prod _ {\ ell =1} ^ {0} N_ {\ ell} = \ prod _ {\ ell = d + 1} ^ {d} N_ {\ ell} = 1}$

Dla danego zamówienia krok w wymiarze k jest podany przez wartość mnożenia w nawiasach przed indeksem n _k w podsumowaniach po prawej stronie powyżej.

Ogólnie rzecz biorąc, istnieje d! możliwe porządki dla danej tablicy, po jednym dla każdej permutacji wymiarów (z wierszami-głównymi i kolumnowymi tylko 2 przypadkami specjalnymi), chociaż listy wartości kroków niekoniecznie są permutacjami siebie nawzajem, np. w 3 przykład powyżej, kroki to (3,1) dla wiersza-głównego i (1,2) dla kolumny-głównej.

Zobacz też

• Tablica struktury danych
• Reprezentacja macierzowa
• Wektoryzacja (matematyka) , odpowiednik zamiany macierzy na odpowiedni wektor kolumny-główny
• Format CSR , technika przechowywania rzadkich macierzy w pamięci
• Porządek Mortona , inny sposób mapowania danych wielowymiarowych na indeks jednowymiarowy, przydatny w drzewiastych strukturach danych

Bibliografia

Źródła

• Donald E. Knuth, The Art of Computer Programming Tom 1: Fundamental Algorithms , wydanie trzecie, sekcja 2.2.6 (Addison-Wesley: New York, 1997).