Řádková a sloupcová hlavní objednávka- Row- and column-major order

V práci na počítači, pořadí řádků major a sloupců hlavní pořadí způsoby pro ukládání vícerozměrná pole v lineárním skladování, jako jsou paměti RAM .

Rozdíl mezi řády spočívá v tom, které prvky pole jsou v paměti souvislé. V pořadí hlavních řádků jsou navazující prvky řádku umístěny vedle sebe, zatímco totéž platí pro po sobě jdoucí prvky sloupce v pořadí hlavních sloupců. Zatímco termíny odkazují na řádky a sloupce dvourozměrného pole, tj. Matice , řády lze zobecnit na pole libovolné dimenze tím, že si povšimneme , že výrazy hlavní řádky a hlavní sloupce jsou ekvivalentní lexikografickým a kolexikografickým řádům , resp.

Rozložení dat je zásadní pro správné předávání polí mezi programy napsanými v různých programovacích jazycích. Je také důležité pro výkon při procházení pole, protože moderní procesory zpracovávají sekvenční data efektivněji než data bez následků. Je to primárně kvůli ukládání do mezipaměti CPU, která využívá prostorovou referenční lokalitu . Souvislý přístup navíc umožňuje používat instrukce SIMD, které fungují na vektorech dat. V některých médiích, jako je páska nebo paměť NAND flash , je postupný přístup řádově rychlejší než nesekvenční přístup.

Vysvětlení a příklad

Výrazy hlavní řádky a hlavní sloupce pocházejí z terminologie související s uspořádáním objektů. Obecným způsobem, jak objednat objekty s mnoha atributy, je nejprve seskupit a seřadit je podle jednoho atributu a poté v rámci každé takové skupiny seskupit a seřadit je podle jiného atributu atd. Pokud se řazení účastní více než jeden atribut, první by být nazýván majorem a posledním menším . Pokud se na uspořádání podílejí dva atributy, stačí pojmenovat pouze hlavní atribut.

V případě polí jsou atributy indexy podél každé dimenze. Pro matic v matematickém zápisu, první index udává řádek a druhý označuje sloupce , např, vzhledem k tomu, matice , je v první řadě a druhém sloupci. Tato konvence se přenáší do syntaxe v programovacích jazycích, i když často s indexy začínajícími na 0 místo 1. ${\ displaystyle A}$${\ displaystyle a_ {1,2}}$

I když je řádek označen prvním indexem a sloupec druhým indexem, není tím naznačeno žádné pořadí seskupení mezi dimenzemi. Volba toho, jak seskupit a uspořádat indexy, a to buď metodami hlavní nebo sloupcová, je tedy věcí konvence. Stejnou terminologii lze aplikovat na ještě vyšší dimenzionální pole. Seskupení hlavních řádků začíná od indexu zcela vlevo a hlavní sloupec podle indexu nejvíce vpravo , což vede k lexikografickým a kolexikografickým (nebo colexovým) řádům .

Například pole

${\ displaystyle A = {\ begin {bmatrix} a_ {11} & a_ {12} & a_ {13} \\ a_ {21} & a_ {22} & a_ {23} \ end {bmatrix}}}$

lze uložit dvěma možnými způsoby:

Adresa	Řád hlavní objednávky	Sloupová hlavní objednávka
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ůzné programovací jazyky to řeší různými způsoby. V jazyce C jsou vícerozměrná pole uložena v řádcích hlavních řádků a indexy polí jsou zapsány na prvním řádku (pořadí lexikografického přístupu):

C: řádka-hlavní pořadí (lexikografický přístupový řád), indexování založené na nule

Adresa	Přístup	Hodnota
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}}$

Na druhou stranu, ve Fortranu jsou pole uložena v pořadí hlavních sloupců, zatímco indexy polí jsou stále zapsány na prvním řádku (pořadí kolexikografického přístupu):

Fortran: pořadí hlavních sloupců (pořadí colexikografického přístupu), indexování na základě jednoho

Adresa	Přístup	Hodnota
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}}$

Všimněte si, že používání A[i][j]s multi-step indexování jako v C, na rozdíl od neutrálního notace jako A(i,j)jako ve Fortranu, téměř nevyhnutelně znamená, řádek-major objednávku syntaktických důvodů, tak říkajíc, protože to může být přepsána jako (A[i])[j], a A[i]řada část lze dokonce přiřadit mezilehlé proměnné, která je poté indexována v samostatném výrazu. (Neměly by se předpokládat žádné další implikace, např. Fortran není hlavní sloupec jen kvůli jeho zápisu, a dokonce i výše uvedené implikace by mohly být záměrně obcházeny v novém jazyce.)

Chcete-li použít pořadí hlavních sloupců v prostředí hlavních řádků nebo naopak z jakéhokoli důvodu, jedním řešením je přiřadit nekonvenční role indexům (pomocí prvního indexu pro sloupec a druhého indexu pro řádek), a další je obejít syntaxi jazyka explicitním výpočtem pozic v jednorozměrném poli. Odchylka od konvence samozřejmě pravděpodobně nese náklady, které se zvyšují se stupněm nutné interakce s konvenčními jazykovými funkcemi a dalším kódem, a to nejen ve formě zvýšené zranitelnosti vůči chybám (zapomínání na invertování pořadí násobení matice, návrat k konvenci během kódu údržba atd.), ale také ve formě aktivního přeskupení prvků, z nichž všechny musí být zváženy proti jakémukoli původnímu účelu, jako je zvýšení výkonu. Spouštění smyčky po řádcích je upřednostňováno v jazycích hlavních řádků, jako je C, a naopak u jazyků hlavních sloupců.

Programovací jazyky a knihovny

Programovací jazyky nebo jejich standardní knihovny, které podporují vícerozměrná pole, mají obvykle pro tato pole nativní pořadí ukládání řádků nebo sloupců.

Pořadí hlavní řady se používá v C / C ++ / Objective-C (pro pole ve stylu C), PL / I , Pascal , Speakeasy , SAS a Rasdaman .

Sloupcová hlavní objednávka se používá ve firmách Fortran , MATLAB , GNU Octave , S-Plus , R , Julia a Scilab .

Ani hlavní, ani hlavní

Typickou alternativou pro úložiště s hustou maticí je použití vektorů Iliffe , které obvykle ukládají ukazatele na prvky ve stejném řádku souvisle (jako řádky hlavní řady), ale nikoli samotné řádky. Používají se v (seřazeném podle věku): Java , C# / CLI / .Net , Scala a Swift .

Ještě méně hustá je použít seznamy seznamů, například v Pythonu , a ve Wolfram jazyk z Wolfram Mathematica .

Alternativní přístup využívá tabulky tabulek, např. V Lua .

Externí knihovny

Podporu vícerozměrných polí mohou poskytovat také externí knihovny, které mohou dokonce podporovat libovolné řazení, kde každá dimenze má hodnotu kroku a hlavní nebo sloupcová hlavní jsou pouze dvě možné výsledné interpretace.

V NumPy (pro Python) je výchozí pořadí řádků .

V Eigen a Armadillo (oba pro C ++) je výchozí pořadí sloupců .

Zvláštním případem by bylo OpenGL (a OpenGL ES ) pro grafické zpracování. Protože „nedávné matematické úpravy lineární algebry a souvisejících polí vždy považují vektory za sloupce,“ rozhodl se designér Mark Segal nahradit to konvencí v předchůdci IRIS GL , která měla vektory zapisovat jako řádky; z důvodu kompatibility by transformační matice byly stále uloženy ve vektoru major (= řádek-major) než v pořadí souřadnic-major (= sloupec-major) a poté použil trik „[aby] řekl, že matice v OpenGL jsou uloženy v sloupec-hlavní objednávka “. To bylo skutečně relevantní pouze pro prezentaci, protože maticové násobení bylo založeno na zásobníku a dalo by se stále interpretovat jako post-multiplikace, ale co je ještě horší, realita unikla přes API založené na C, protože k jednotlivým prvkům by se přistupovalo jako M[vector][coordinate]nebo efektivně M[column][row], což bohužel zamotal konvenci, kterou se designér snažil přijmout, a to bylo dokonce zachováno v OpenGL Shading Language, který byl později přidán (ačkoli to také umožňuje místo toho přistupovat k souřadnicím podle jména, např. M[vector].y). V důsledku toho nyní mnoho vývojářů jednoduše prohlásí, že mít sloupec jako první index je definicí sloupce major, i když to zjevně neplatí pro skutečný jazyk pro sloupce major, jako je Fortran.

Pochodeň (pro Lua) se změnila z výchozího pořadí sloupec-major na řádek-hlavní.

Transpozice

Protože výměna indexů pole je podstatou transpozice pole , pole uložené jako hlavní řádek, ale čtené jako hlavní sloupec (nebo naopak) bude vypadat transponováno (pokud je matice čtvercová). Protože ve skutečnosti provádění tohoto přeskupení v paměti je obvykle nákladná operace, některé systémy poskytují možnosti specifikovat jednotlivé matice jako uložené transponované. Programátor se pak musí rozhodnout, zda uspořádá prvky v paměti, na základě skutečného využití (včetně počtu opakovaných použití pole ve výpočtu).

Například funkcím podprogramů Basic Linear Algebra Subprograms jsou předávány příznaky udávající, která pole jsou transponována.

Výpočet adresy obecně

Koncept generalizuje na pole s více než dvěma dimenzemi.

Pro d rozměrné pole s rozměry N _k ( k = 1 ... d ), daný prvek tohoto pole je specifikována n-tice o d (od nuly) indexy . ${\ displaystyle N_ {1} \ times N_ {2} \ times \ cdots \ times N_ {d}}$ ${\ displaystyle (n_ {1}, n_ {2}, \ ldots, n_ {d})}$${\ Displaystyle n_ {k} \ v [0, N_ {k} -1]}$

V pořadí hlavní řádky je poslední dimenze souvislá, takže posun paměti tohoto prvku je dán vztahem:

${\ 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}}$

V pořadí hlavních sloupců je první dimenze souvislá, takže posun paměti tohoto prvku je dán vztahem:

${\ 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 }}$

kde prázdný produkt je multiplikativní prvek identity , tj . ${\ Displaystyle \ prod _ {\ ell = 1}^{0} N _ {\ ell} = \ prod _ {\ ell = d+1}^{d} N _ {\ ell} = 1}$

Pro dané pořadí je krok v dimenzi k dán multiplikační hodnotou v závorkách před indexem n _k v _součtech na pravé straně výše.

Obecněji řečeno, existují d! možné objednávky pro dané pole, jeden pro každou permutaci dimenzí (u řádků velkých a sloupcových pouze 2 speciální případy), přestože seznamy hodnot kroku nejsou nutně vzájemné permutace, např. v 2 po 3 příklad výše, kroky jsou (3,1) pro hlavní řádek a (1,2) pro hlavní sloupec.

Viz také

• Datová struktura pole
• Maticová reprezentace
• Vektorizace (matematika) , ekvivalent přeměny matice na odpovídající sloupcový hlavní vektor
• Formát CSR , technika pro ukládání řídkých matic do paměti
• Mortonův řád , další způsob mapování vícerozměrných dat do jednorozměrného indexu, užitečný ve stromových datových strukturách

Reference

Zdroje

• Donald E. Knuth, The Art of Computer Programming Volume 1: Fundamental Algorithms , third edition, section 2.2.6 (Addison-Wesley: New York, 1997).