Poredak po vrstama

U računarstvu, Poredak po vrstama i Poredak po kolonama opisiuju metode za skladištenje višedimenzionlnih nizova u RAM memoriju. Prema standardnoj matričnoj notaciji, redovi su numerisani prvim indeksom dvodimenzionalnog niza a kolone drugim indeksom. Redosled elemenata u nizu je bitan za pravilno prenošenje nizova između programa koji su napisani različitim jezicima. Za performanse je bitno kada se prenosi niz da je pristup susednim elementima brži no kad nisu susedni, zbog keš memorije.

Poredak po vrstama se koristi u programskim jezicima: C/C++, Mathematica, PL/I, Pascal, Python, Speakeasy, SAS i ostalim. Poredak po kolonama se koristi u programskim jezicima: Fortran, OpenGL and OpenGL ES, MATLAB, GNU Octave, R, Julia, Rasdaman, i Scilab.

Poredak po vrstama

Višedimenzionalni niz u memoriji je organizovan tako da se redovi skladište jedna posle drugog. Takav pristup se koristi u programskom jeziku C, kao i u ostalim jezicima.

Na primer, razmotrite sledeću 2×3 matricu:

${\begin{bmatrix}1&2&3\\4&5&6\end{bmatrix}}$

Niz deklarisan u programskom jeziku S

int A[2][3] = { {1, 2, 3}, {4, 5, 6} };

je smešten u memoriji:

1  2  3  4  5  6

Da bi se ovaj niz premestio u redosledu kojim je smešten u memoriji, koristi se sledeća petlja:

for (row = 0; row < 2; row++) 
    for (column = 0; column < 3; column++) 
        printf("%d\n", A[row][column]);

Razlika ofseta od jedne kolone do druge je 1 a od jednog reda do drugog je 3 (nulti indeks). Ako razmotrimo bilo koju matricu jednodimenzionalnog niza, linearni ofset od početka niza do bilo kog datog elementa A[red][kolona] može biti izračunat kao:

ofset = (red * BROJ_KOLONA) + kolona

Obrnuto, dati element niza je linearni ofset, odgovarajući red i kolona mogu se odrediti iz:

red = ofset / BROJ_KOLONA kolona = ofset % BROJ_KOLONA

gde / predstavlja celobrojno deljenje i (%) je moduo.

Ove formule rade jedino prateći S konvenciju, indeksirajući prvi element 0. Drugim rečima, red 1, kolona 2, u matrici A je predstavljena sa A[0][1].

Ova tehnika generalizuje se na veće dimenzije, tako da 2×3×4 niz izgleda:

int A[2][3][4] = {{{1,2,3,4}, {5,6,7,8}, {9,10,11,12}}, {{13,14,15,16}, {17,18,19,20}, {21,22,23,24}}};

i niz je u memoriji smešten kao:

1  2  3  4  5  6  7  8  9  10  11  12  13  14  15  16  17  18  19  20  21  22  23  24

Poredak po kolonama

Poredak po kolonama je sličan metod ravnanja nizova u memoriji, ali kolone su svrstane sekvencijalno. Naučni programski jezici Fortran i Julia, matrično orijentisani jezici MATLAB, Octave i Scilab, statistički jezici S-Plus i R, Nijansirani jezici GLSL i HLSL (ali ne Cg), i niz baze podataka Rasdaman koriste poredak po kolonama. Niz

${\begin{bmatrix}1&2&3\\4&5&6\end{bmatrix}}$

koji je smešten u memoriji sa poretkom po kolonama izgleda ovako:

1  4  2  5  3  6

Memorijski ofset se tada može izračunati:

ofset = red + kolona*BROJ_REDOVA

gde BROJ_REDOVA predstavlja broj redova u nizu—u ovom slučaju, 2.

Smatrati glavni red niza kao glavnu kolonu niza je isto kao i prenositi ga. Zato što prenošenje zahteva prenos podataka i teško je primeniti algoritam za sortiranje u mestu nekvadratnih matrica, takav prenos se retko izvodi eksplicitno. Na primer, (softverske biblioteke) za linearnu algebru, kao što je BLAS, obično obezbeđuju opcije da specifikuju određene matrice koje se mogu interpretirati u redosledu prenošenja da bi se izbegla potreba prenosa podataka.

Generalizacija većih dimenzija

Moguće je generalizovati obe vrste koncepta u nizovima dimenzija većim od 2. Za višedimenzionalne nizove, redosled određuje koje dimenzije u nizu su uzastopne u memoriji. Bilo koja dimenzija može biti uzastopna, kao što dvodimenzionalni niz može biti određen prvo redom ili prvo kolonom. Razlika ofseta između nabrajanja te dimenzije biće onda određena produktom ostalih dimenzija. Neuobičajno je koristiti druge načine osim nabrajanja dimenzija od prve do poslednje ili od poslednje do prve. Ova dva načina odgovaraju poretku po vrstavam i poretku po kolonama.

Posmatrajmo d-dimenzionalni $N_{1}\times N_{2}\times \cdots \times N_{d}$ niz sa dimenzijamaN_k (k=1...d). Dati element ovog niza je određen N-torkom $(n_{1},n_{2},\ldots ,n_{d})$ od d (nulta osnova) indeksa $n_{k}\in [0,N_{k}-1]$.

U poretku po vrstama, memorijski ofset ovog elemnta se određuje:

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

U poretku po kolonama, memorijski ofset ovog elemnta se određuje:

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

Literatura

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