Поредак по врстама

У рачунарству, Поредак по врстама и Поредак по колонама описиују методе за складиштење вишедимензионлних низова у RAM меморију. Према стандардној матричној нотацији, редови су нумерисани првим индексом дводимензионалног низа а колоне другим индексом. Редослед елемената у низу је битан за правилно преношење низова између програма који су написани различитим језицима. За перформансе је битно када се преноси низ да је приступ суседним елементима бржи но кад нису суседни, због кеш меморије.

Поредак по врстама се користи у програмским језицима: C/C++, Mathematica, PL/I, Pascal, Python, Speakeasy, SAS и осталим. Поредак по колонама се користи у програмским језицима: Fortran, OpenGL and OpenGL ES, MATLAB, GNU Octave, R, Julia, Rasdaman, и Scilab.

Поредак по врстама

Вишедимензионални низ у меморији је организован тако да се редови складиште једна после другог. Такав приступ се користи у програмском језику C, као и у осталим језицима.

На пример, размотрите следећу 2×3 матрицу:

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

Низ декларисан у програмском језику С

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

је смештен у меморији:

1  2  3  4  5  6

Да би се овај низ преместио у редоследу којим је смештен у меморији, користи се следећа петља:

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

Разлика офсета од једне колоне до друге је 1 а од једног реда до другог је 3 (нулти индекс). Ако размотримо било коју матрицу једнодимензионалног низа, линеарни офсет од почетка низа до било ког датог елемента А[ред][колона] може бити израчунат као:

офсет = (ред * БРОЈ_КОЛОНА) + колона

Обрнуто, дати елемент низа је линеарни офсет, одговарајући ред и колона могу се одредити из:

ред = офсет / БРОЈ_КОЛОНА колона = офсет % БРОЈ_КОЛОНА

где / представља целобројно дељење и (%) je модуо.

Ове формуле раде једино пратећи С конвенцију, индексирајући први елемент 0. Другим речима, ред 1, колона 2, у матрици А је представљена са А[0][1].

Ова техника генерализује се на веће димензије, тако да 2×3×4 низ изгледа:

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

и низ је у меморији смештен као:

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

Поредак по колонама

Поредак по колонама је сличан метод равнања низова у меморији, али колоне су сврстане секвенцијално. Научни програмски језици Fortran и Julia, матрично оријентисани језици MATLAB, Octave и Scilab, статистички језици S-Plus и R, Нијансирани језици GLSL и HLSL (али не Cg), и низ базе података Rasdaman користе поредак по колонама. Низ

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

који је смештен у меморији са поретком по колонама изгледа овако:

1  4  2  5  3  6

Меморијски офсет се тада може израчунати:

офсет = ред + колона*БРОЈ_РЕДОВА

где БРОЈ_РЕДОВА представља број редова у низу—у овом случају, 2.

Сматрати главни ред низа као главну колону низа је исто као и преносити га. Зато што преношење захтева пренос података и тешко је применити алгоритам за сортирање у месту неквадратних матрица, такав пренос се ретко изводи експлицитно. На пример, (софтверске библиотеке) за линеарну алгебру, као што је BLAS, обично обезбеђују опције да спецификују одређене матрице које се могу интерпретирати у редоследу преношења да би се избегла потреба преноса података.

Генерализација већих димензија

Могуће је генерализовати обе врсте концепта у низовима димензија већим од 2. За вишедимензионалне низове, редослед одређује које димензије у низу су узастопне у меморији. Било која димензија може бити узастопна, као што дводимензионални низ може бити одређен прво редом или прво колоном. Разлика офсета између набрајања те димензије биће онда одређена продуктом осталих димензија. Неуобичајно је користити друге начине осим набрајања димензија од прве до последње или од последње до прве. Ова два начина одговарају поретку по врставам и поретку по колонама.

Посматрајмо d-димензионални $N_{1}\times N_{2}\times \cdots \times N_{d}$ низ са димензијамаN_k (k=1...d). Дати елемент овог низа је одређен N-торком $(n_{1},n_{2},\ldots ,n_{d})$ od d (нулта основа) индекса $n_{k}\in [0,N_{k}-1]$.

У поретку по врстама, меморијски офсет овог елемнта се одређује:

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

У поретку по колонама, меморијски офсет овог елемнта се одређује:

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

Литература

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