행 및 열 주 순서

컴퓨팅에서 행-주문, 컬럼-주문 순서는 다차원 배열을 랜덤 액세스 메모리와 같은 선형 저장소에 저장하는 방법이다.

순서의 차이는 배열의 요소들이 메모리에 연속적으로 존재하는 것에 있다.행 주계열 순서에서 행의 연속적인 요소는 서로 옆에 있는 반면, 열 주계열의 연속적인 요소도 마찬가지다.이 용어는 2차원 배열의 행과 열, 즉 행렬을 암시하지만 행-주요 및 열-주요 용어가 각각 사전 편찬 및 편독성 주문과 동일하다는 점에 유의하여 모든 차원의 배열로 일반화할 수 있다.

데이터 레이아웃은 서로 다른 프로그래밍 언어로 작성된 프로그램 간에 배열을 올바르게 전달하기 위해 중요하다.최신 CPU는 비순차적 데이터보다 순차적 데이터를 더 효율적으로 처리하기 때문에 어레이를 통과할 때 성능에도 중요하다.이는 주로 참조의 공간적 인접성을 이용하는 CPU 캐싱 때문이다.^[1]또한 연속적인 액세스는 데이터의 벡터에서 작동하는 SIMD 지침을 사용할 수 있게 해준다.테이프나 NAND 플래시 메모리와 같은 일부 미디어에서 순차적 액세스는 비순차적 액세스보다 더 빠른 규모의 순서다.^{[citation needed]}

설명 및 예

행-주요 및 열-주요 용어는 주문 객체와 관련된 용어에서 유래한다.속성이 많은 객체를 주문하는 일반적인 방법은 먼저 한 속성별로 그룹화하여 정렬하고, 그런 각 그룹 내에서 다른 속성 등으로 그룹화하여 정렬하는 것이다.둘 이상의 속성이 순서에 참여하면 첫 번째 속성은 major, 마지막 minor라고 한다.만약 두 가지 속성이 순서에 참여한다면, 주요 속성만 명명하는 것으로 충분하다.

배열의 경우 속성은 각 차원을 따르는 지수들이다.수학 표기법 행렬의 경우 첫 번째 인덱스는 행을 나타내고 두 번째 인덱스는 열을 나타내며, 예를 들어 $행렬{\displaystyle }$ A ${\displaystyle A$ ${\displaystyle {1\mathrm{}}_{}}$,${\displaystyle 2_{}}$ ${\$,2$}}$개가 첫 $번째$ 행과 두 번째 열에 있다$$.이 협약은 프로그래밍 언어의 구문으로 넘어가지만,^[2] 종종 인덱스가 1이 아닌 0에서 시작하는 경우가 많다.^[3]

행은 첫 번째 색인으로 표시되고 열은 두 번째 색인으로 표시되더라도 치수 사이의 그룹화 순서는 여기에 함축되어 있지 않다.따라서 지수를 행-주요 방식 또는 열-주요 방식으로 그룹화하고 정렬하는 방법의 선택은 관례에 따라 결정된다.동일한 용어를 훨씬 더 높은 치수 배열에도 적용할 수 있다.행-주요 그룹은 맨 왼쪽 색인에서 시작하여 가장 오른쪽 색인에서 열-주요 색인화되며, 각각 사전 편찬 및 편찬(또는 colex) 주문으로 이어진다.

예를 들어 배열

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

다음 두 가지 방법으로 저장할 수 있다.

주소	행주문	열주주문
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}}$

다른 프로그래밍 언어들은 이것을 다른 방식으로 처리한다.C에서 다차원 배열은 행 주 순서로 저장되며, 배열 색인은 행 우선(사전적 접근 순서)으로 작성된다.

C: 행 주요 순서(사전 액세스 순서), 제로 기반 인덱싱

주소	접근	가치
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}}$

한편, Fortran의 경우, 배열 색인은 여전히 행 우선(독서적 접근 순서)으로 작성되는 반면, 배열은 열 주 순서로 저장된다.

Fortran: 컬럼 주요 순서(독소 접근 순서), 1 기반 인덱싱

주소	접근	가치
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}}$

의 사용 방법에 유의하십시오.A[i][j]C와 같이 다단계 인덱싱으로, 다음과 같은 중립 표기법과 대조적으로A(i,j)포트란에서와 마찬가지로, 말하자면, 통사적 이유로 거의 필연적으로 행의 주요한 질서를 내포하고 있다. 왜냐하면 그것은 다시 쓰여질 수 있기 때문이다.(A[i])[j]그리고A[i]행 부분은 별도의 식에서 색인화된 중간 변수에 할당될 수도 있다.(예를 들어, 포트란은 단순히 표기법 때문에 칼럼을 전공하지 않으며, 위의 함축조차도 의도적으로 새로운 언어로 우회될 수 있다.)

열 주계열 환경에서 열 주계열 순서를 사용하거나, 그 반대로 어떤 이유로든 하나의 해결책은 인덱스에 비전통적인 역할을 할당하는 것이다(열 주계열의 첫 번째 인덱스와 행의 두 번째 인덱스를 사용). 또 다른 방법은 1차원 배열의 위치를 명시적으로 계산하여 언어 구문을 우회하는 것이다.물론 관습에서 벗어나는 것은 아마도 전통적인 언어 특징과 다른 코드와의 필요한 상호작용의 정도에 따라 증가하는 비용을 유발할 것이다. 이는 실수에 대한 취약성 증가의 형태일 뿐만 아니라(매트릭스 곱셈 순서를 뒤집는 것을 잊어버리고, 코드 유지 관리 중 관례로 되돌리는 것 등)적극적으로 요소를 재정렬해야 하는 형태로, 이 모든 것들은 성능 향상과 같은 어떤 원래의 목적에 대해서도 저울질해야 한다.루프를 열로 실행하는 것은 열로 된 언어의 경우 C와 그 반대의 경우처럼 행으로 된 주요 언어에서 선호된다.

언어 및 라이브러리 프로그래밍

다차원 배열을 지원하는 프로그래밍 언어 또는 표준 라이브러리는 일반적으로 이러한 배열을 위한 기본 행 주 또는 열 주 저장 순서를 가진다.

행주식은 C/C+/Objective-C(C 스타일 어레이의 경우), PL/I,^[4] Pascal,^[5] Spakeasy,^{[citation needed]} SAS,^[6] Rasdaman에서 사용된다.^[7]

기둥주문은 포트란, MATLAB,^[8] GNU 옥타브, S-Plus,^[9] R,^[10] 줄리아,^[11] 실랍에서 사용된다.^[12]

행-주요도-주요도-주요도-주요도 없음

고밀도 배열 저장을 위한 일반적인 대안은 Ilife 벡터를 사용하는 것인데, 이 벡터는 일반적으로 같은 행의 요소에 포인터를 연속적으로 저장하지만(열 주계열 순서처럼) 행 자체는 저장하지 않는다.(연령별로 정렬)에 사용된다.Java,^[13] C#/CLI/.넷, 스칼라,^[14] 스위프트.

더 조밀하지 않은 것은 예를 들어 파이톤과 ^[15]울프램 매티매틱카의 울프램 언어와 같은 목록 목록을 사용하는 것이다.^[16]

대안적 접근방식은 예를 들어 루아에서 표의 표를 사용한다.^[17]

외부 라이브러리

다차원 배열에 대한 지원은 또한 외부 라이브러리에 의해 제공될 수 있으며, 이것은 각 차원이 보폭 값을 가지고 있고, 행 주 또는 열 주조는 두 가지 가능한 결과 해석에 불과하다.

행 주 순서는 NumPy^[18](Python의 경우)의 기본값이다.

열 주^[19] 순서는 아이겐과 아르마딜로(C++의 경우 둘 다)에서 기본값이다.

특별한 경우는 그래픽 처리를 위한 OpenGL (및 OpenGL ES)이다."선형대수학과 관련 분야의 최근 수학적 치료는 벡터를 항상 컬럼으로 취급하기 때문에, 설계자 마크 시걸은 벡터를 행으로 쓰는 이전의 IRIS GL에서의 협약으로 이것을 대체하기로 결정했다. 호환성을 위해 변환 매트릭스는 여전히 coor가 아닌 벡터 전공(=행 전공)에 저장될 것이다.그는 "OpenGL의 매트릭스는 주요 컬럼 순서로 저장된다"는 트릭을 사용했다.^[20]이는 매트릭스 곱셈이 스택 기반이고 여전히 포스트 곱셈으로 해석될 수 있기 때문에 발표에만 실제로 관련이 있었지만, 더 나쁜 것은 개별 요소들이 접속될 것이기 때문에 C 기반 API를 통해 현실이 누출되었다.M[vector][coordinate]아니면, 효과적으로M[column][row]설계자가 채택하려고 했던 관례를 불행히도 혼동시켰고, 이것은 나중에 추가된 OpenGL Shading Language에도 보존되었다(이 또한 이름으로 좌표에 접근하는 것을 가능하게 하지만, 예:M[vector].y그 결과, 많은 개발자들은 포트란과 같은 실제 칼럼 전공 언어가 분명히 그렇지는 않지만, 이제 칼럼을 첫 번째 인덱스로 하는 것이 칼럼 전공의 정의라고 간단히 선언할 것이다.

Torch(Lua의 경우)가 column-major에서^[21] row-major^[22] 기본 순서로 변경되었다.

전치

배열의 지수를 교환하는 것이 배열 전환의 핵심이기 때문에, 행-주요로 저장되지만 컬럼-주요(또는 그 반대로)로 읽히는 배열은 행렬이 정사각형인 한 전치된 것처럼 보일 것이다.실제로 메모리에서 이러한 재배치를 수행하는 것은 일반적으로 비용이 많이 드는 작업이기 때문에, 일부 시스템은 개별 매트릭스를 전치 저장되는 것으로 지정하는 옵션을 제공한다.그런 다음 프로그래머는 실제 사용량(배열을 계산에 재사용하는 횟수 포함)을 기준으로 메모리의 요소 재배열 여부를 결정해야 한다.

예를 들어, 기본 선형 대수 하위 프로그램 함수는 어떤 배열이 전치되었는지 나타내는 플래그가 전달된다.^[23]

일반적으로 주소 계산

이 개념은 2차원 이상의 배열로 일반화된다.

한d-dimensional N1×을 위해 N2×⋯×Nd{\displaystyle N_{1}\times N_{2}\times \cdots \times N_{d}}배열과 치수여 감사(k=1...d), 주어진 이 요소 배열은 지정된에 의해 한 투플(n1, n2,…, nd){\displaystyle(n_{1},n_{2},\ldots ,n_{d})}의 d(0)지수 nk∈[0, N는 k${\displaystyle -}$ ${\displaystyle 1}$ ${\displaystyle ]}$ ${\displaystyle n_{k}\in [0,N_{k}-1$

행 주차 순서에서 마지막 치수는 연속적이므로 이 요소의 메모리 오프셋은 다음과 같이 주어진다.

열 주계열 순서에서 첫 번째 치수는 연속적이므로 이 요소의 메모리 오프셋은 다음과 같이 주어진다.

여기서 빈 제품은 곱셈 ID 요소, 즉 $\prod \underset{}{\overset{}{}}$= 1 $\underset{}{\overset{}{}}{}_{}$ $\underset{}{\overset{}{\mathrm{}}}$ $\underset{}{\overset{}{\ell }}{}_{}$= $\underset{}{\overset{}{}}$= $\underset{}{\overset{}{d}}$+ 1 $\underset{}{\overset{}{\mathrm{d}}}$ $\underset{}{\overset{}{}}{}_{}$ ${\ell }_{}$= $1$ ${\textstyle \prod _{\ell =1}^{0$$}{{\ell }=\prod _{\ell =d+1}^{d$$}{{\ell }=1$

주어진 순서의 경우, 위의 오른쪽 합계에서 색인 n보다_k 먼저 괄호 안의 곱셈 값으로 치수 k의 보폭을 구한다.

보다 일반적으로는 치수의 순열별로 d! 가능한 배열 순서가 있다(열-주문 및 열-주문만 2개). 비록 보폭 값 목록이 반드시 서로의 순열은 아니지만, 예를 들어, 위의 2대3 예에서 보폭은 열-주문인 경우 (3,1) 및 열-주문인 경우 (1,2)이다.

참고 항목

• 배열 데이터 구조
• 행렬 표현
• 벡터화(수학), 행렬을 해당 열 주 벡터로 변환하는 것과 동등한 값
• CSR 형식, 희소성 행렬을 메모리에 저장하는 기법
• 다차원 데이터를 1차원 인덱스에 매핑하는 또 다른 방법인 Morton 순서(트리 데이터 구조에서 유용함)

참조

원천

• 도널드 크누스, 컴퓨터 프로그래밍의 기술 제1권: 기본 알고리즘, 제3판, 제2.2.6절 (애디슨-웨슬리:1997년 뉴욕.