2차원 배열의 행우선과 열우선 📂프로그래밍

2차원 배열의 행우선과 열우선

Row-major and column-major

개요 1

행렬 혹은 2차원 배열의 행우선row-major, 열우선column-major에 대해 설명한다. 행우선이냐 열우선이냐는 쉽게 말해 배열을 참조하면서 어떤 반향으로 읽느냐를 선호하는지를 말한다.

차이점

위키피디아에 따르면 어떤 프로그래밍 언어와 라이브러리들은 다음과 같이 네이티브Native한 행/렬우선이 정해져있다고 한다.

  • 행우선: 행렬에서 행을 먼저 잡고 왼쪽에서 오른쪽으로 읽어가는 방식이다.

    • C/C++/Objective-C
    • PL/I
    • Pascal
    • Speakeasy
    • SAS
    • Rasdaman
  • 열우선: 행렬에서 열을 먼저 잡고 위에서 아래로 읽어가는 방식이다.

1

왜 이런 차이가 일어나는가

우선 컴퓨터공학적인 설명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)

  1. https://en.wikipedia.org/wiki/Row-_and_column-major_order ↩︎

  2. https://velog.io/@kjh107704/row-major-%ED%96%89-%EC%9A%B0%EC%84%A0-column-major%EC%97%B4-%EC%9A%B0%EC%84%A0%EA%B0%80-%EC%99%9C-%EC%A4%91%EC%9A%94%ED%95%9C%EA%B0%80 ↩︎

댓글