2차원 배열의 행우선과 열우선
개요 1
행렬 혹은 2차원 배열의 행우선row-major, 열우선column-major에 대해 설명한다. 행우선이냐 열우선이냐는 쉽게 말해 배열을 참조하면서 어떤 반향으로 읽느냐를 선호하는지를 말한다.
차이점
위키피디아에 따르면 어떤 프로그래밍 언어와 라이브러리들은 다음과 같이 네이티브native한 행/렬우선이 정해져있다고 한다.
행우선: 행렬에서 행을 먼저 잡고 왼쪽에서 오른쪽으로 읽어가는 방식이다.
- C/C++/Objective-C
- PL/I
- Pascal
- Speakeasy
- SAS
- Rasdaman
열우선: 행렬에서 열을 먼저 잡고 위에서 아래로 읽어가는 방식이다.
왜 이런 차이가 일어나는가
우선 컴퓨터공학적인 설명2보다는 직관적으로 이해해보자. 컴퓨터든 인간이든 행렬을 읽을 때 선호하는 방식이 아니면 어떤 애로사항이 있는지를 상상해 보려고 한다. 가령 우리가 열우선으로 행렬을 읽는 사람이라고 생각해보자.
$$ \begin{bmatrix} 1 & 4 & 7 \\ 2 & 5 & 8 \\ 3 & 6 & 9 \end{bmatrix} $$
위의 행렬을 읽어들일 때 우리는 열우선이므로 $1,2,3,4,5,\cdots$ 와 같이 편하게 읽으면 된다. 그러나 억지로 행우선으로 읽게 한다면 $1,4,7,2,5,\cdots$ 와 같이 부자연스러운 순서로 읽게 된다.
컴퓨터의 입장에서 보면 물리적인 메모리에 논리적인 배열이 할당되어있고, 우리의 명령에 따라 행렬을 읽게 되는데 프로그래밍 언어의 설계대로 그냥 읽어들이는 것과 행/열을 뒤섞어가며 읽는 방식엔 큰 차이가 있을 수밖에 없다.
왜 행우선인가
주어진 행렬을 화면에 출력하는 프로그램을 짠다고 상상해보자. 상식적으로 윗줄부터 오른쪽으로 끝까지 쓰고 개행한 뒤 다음줄을 써내려가는 방식이 되어야할텐데, 그렇다면 대부분의 프로그래밍 언어들도 콘솔창에서 위에서 아래로 내려가기 때문에 행우선을 선택하는 편이 자연스럽다.
왜 열우선인가
포트란, 매트랩, R, 줄리아…
라인업이 기가 막힌다. 한 눈에 보아도 과학, 계산쪽의 언어들이 열우선을 채택한 것을 알 수 있다. 애초에 행렬이라는 것의 기원이 연립방정식의 축약임을 생각해보면 당연한 일이다. 세상에 행렬을 가로 방향으로 읽는 수학자는 없다. 당연히 행을 따라 위에서 아래로, 다시 말해 열우선으로 읽는게 정상이다.
퍼포먼스 비교
julia> size = 10^4
10000
julia> M = rand(size, size);
줄리아 언어를 기준으로 벤치마크를 해보았다. 아래의 두 코드 펜스를 보면 정확히 같은 코드에서 행/렬의 순서만 바꾸고 실행시간을 측정했는데 행을 먼저 읽었을 때 36초, 열우선인 줄리아는 열을 먼저 읽어들였을 때 20초가 걸려 거의 2배 수준의 극적인 성능 차이가 있음을 확인했다.
julia> X = zeros(size, size);
julia> @time for i in 1:size
for j in 1:size
X[i,j] = (M[i,j] + 1)
end
end
36.088533 seconds (489.82 M allocations: 8.789 GiB, 4.64% gc Time)
julia> X = zeros(size, size);
julia> @time for j in 1:size
for i in 1:size
X[i,j] = (M[i,j] + 1)
end
end
19.936053 seconds (489.82 M allocations: 8.789 GiB, 7.59% gc Time)