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

Из Википедије, слободне енциклопедије

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

Поредак по врстама се користи у програмским језицима: C/C++, Mathematica, PL/I, Pascal, Python, Speakeasy, SAS и осталим. Column-major order се користи у програмским језицима: 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,[1] Octave и Scilab, статистички језици S-Plus[2] и R,[3] Нијансирани језици GLSL и HLSL (али не Cg), и низ базе података Rasdaman користe поредак по колонама. Низ

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

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

1  4  2  5  3  6

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

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

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

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

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

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

Посматрајмо d-димензионални N_1 \times N_2 \times \cdots \times N_d низ са димензијамаNk (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

Референце[уреди]

  1. ^ MATLAB documentation, MATLAB Data Storage (retrieved from Mathworks.co.uk, January 2014).
  2. ^ Spiegelhalter et al. (2003, p. 17): Spiegelhalter, David; Thomas, Andrew; Best, Nicky; Lunn, Dave (January 2003), „Formatting of data: S-Plus format“, WinBUGS User Manual (Version 1.4 ed.), Robinson Way, Cambridge CB2 2SR, UK: MRC Biostatistics Unit, Institute of Public Health, PDF document 
  3. ^ An Introduction to R, Section 5.1: Arrays (retrieved March 2010).