행 우선 방식(Row-major Order) vs. 열 우선 방식(Column-major Order)
2차원 배열은 메모리에 1차원적으로 저장되므로, 특정한 규칙을 따라야 합니다.
이때, 배열을 메모리에 저장하는 방식에는 **행 우선 방식(Row-major Order)**과 **열 우선 방식(Column-major Order)**이 있습니다.
1. 행 우선 방식(Row-major Order)
행 우선 방식은 행을 기준으로 데이터를 연속적으로 저장하는 방식입니다.
즉, 같은 행의 원소들이 연속적으로 메모리에 저장된 후 다음 행으로 넘어갑니다.
예제
배열 A[3][4] (3행 4열)가 주어졌을 때,
다음과 같이 메모리에 저장됩니다.
배열 구조
| A[0][0] | A[0][1] | A[0][2] | A[0][3] |
|---|---|---|---|
| A[1][0] | A[1][1] | A[1][2] | A[1][3] |
| A[2][0] | A[2][1] | A[2][2] | A[2][3] |
메모리 배치 (행 우선)
메모리에 저장되는 순서:
A[0][0], A[0][1], A[0][2], A[0][3], A[1][0], A[1][1], A[1][2], A[1][3], A[2][0], A[2][1], A[2][2], A[2][3]
메모리 주소 공식 (행 우선)
주소=Base Address+(행 인덱스×열 개수+열 인덱스)×데이터 크기\text{주소} = \text{Base Address} + (\text{행 인덱스} × \text{열 개수} + \text{열 인덱스}) × \text{데이터 크기}
✅ Base Address: 배열의 시작 주소
✅ 행 인덱스(Row Index): 찾고자 하는 원소의 행 번호
✅ 열 인덱스(Column Index): 찾고자 하는 원소의 열 번호
✅ 열 개수(Columns): 한 행에 있는 원소의 개수
✅ 데이터 크기: 한 원소의 바이트 크기
예제 1: 행 우선 방식에서 A[2][3]의 메모리 주소 구하기
가정
- Base Address = 1000
- 데이터 크기 = 4바이트
- 배열 크기 = A[3][4]
계산 주소=1000+(2×4+3)×4\text{주소} = 1000 + (2 × 4 + 3) × 4 =1000+(8+3)×4= 1000 + (8 + 3) × 4 =1000+44=1044= 1000 + 44 = 1044
💡 정답: A[2][3]의 주소는 1044
2. 열 우선 방식(Column-major Order)
열 우선 방식은 열을 기준으로 데이터를 연속적으로 저장하는 방식입니다.
즉, 같은 열의 원소들이 연속적으로 메모리에 저장된 후 다음 열로 넘어갑니다.
예제
배열 A[3][4] (3행 4열)가 주어졌을 때,
다음과 같이 메모리에 저장됩니다.
배열 구조
| A[0][0] | A[0][1] | A[0][2] | A[0][3] |
|---|---|---|---|
| A[1][0] | A[1][1] | A[1][2] | A[1][3] |
| A[2][0] | A[2][1] | A[2][2] | A[2][3] |
메모리 배치 (열 우선)
메모리에 저장되는 순서:
A[0][0], A[1][0], A[2][0], A[0][1], A[1][1], A[2][1], A[0][2], A[1][2], A[2][2], A[0][3], A[1][3], A[2][3]
메모리 주소 공식 (열 우선)
주소=Base Address+(열 인덱스×행 개수+행 인덱스)×데이터 크기\text{주소} = \text{Base Address} + (\text{열 인덱스} × \text{행 개수} + \text{행 인덱스}) × \text{데이터 크기}
✅ Base Address: 배열의 시작 주소
✅ 열 인덱스(Column Index): 찾고자 하는 원소의 열 번호
✅ 행 인덱스(Row Index): 찾고자 하는 원소의 행 번호
✅ 행 개수(Rows): 한 열에 있는 원소의 개수
✅ 데이터 크기: 한 원소의 바이트 크기
예제 2: 열 우선 방식에서 A[2][3]의 메모리 주소 구하기
가정
- Base Address = 1000
- 데이터 크기 = 4바이트
- 배열 크기 = A[3][4]
계산 주소=1000+(3×3+2)×4\text{주소} = 1000 + (3 × 3 + 2) × 4 =1000+(9+2)×4= 1000 + (9 + 2) × 4 =1000+44=1044= 1000 + 44 = 1044
💡 정답: A[2][3]의 주소는 1044
3. 행 우선 vs. 열 우선의 차이점
| 구분 | 행 우선(Row-major) | 열 우선(Column-major) |
|---|---|---|
| 저장 방식 | 행을 기준으로 연속 저장 | 열을 기준으로 연속 저장 |
| 주소 공식 | Base + (Row * Columns + Col) * DataSize | Base + (Col * Rows + Row) * DataSize |
| 사용 언어 | C, C++, Java 등 | Fortran, MATLAB 등 |
| 캐시 효율성 | 2D 배열을 순차적으로 접근할 때 더 효율적 | 특정 열을 연속적으로 접근할 때 더 효율적 |
4. 캐시 효율성 차이
✅ 행 우선 방식이 유리한 경우
- 대부분의 프로그래밍 언어(C, C++, Java 등)가 행 우선 방식을 사용합니다.
for문을 사용할 때, 행 단위로 순차적으로 접근하면 캐시 적중률(Cache Hit)이 높아 성능이 향상됩니다.
// 행 우선 방식 (더 빠름)
for (int i = 0; i < rows; i++) {
for (int j = 0; j < cols; j++) {
sum += A[i][j]; // 메모리 캐시 친화적
}
}
❌ 열 우선 방식이 불리한 경우
- 행 우선 방식에서 열을 순회하면 캐시 미스(Cache Miss)가 자주 발생합니다.
// 열 우선 방식 (더 느림)
for (int j = 0; j < cols; j++) {
for (int i = 0; i < rows; i++) {
sum += A[i][j]; // 캐시 미스 증가
}
}
결론
- C, C++, Java는 행 우선 방식(Row-major Order)을 사용하며, 일반적으로 더 효율적입니다.
- Fortran, MATLAB은 열 우선 방식(Column-major Order)을 사용합니다.
- 캐시 효율성을 고려하면 행 우선 방식이 대부분의 경우 더 빠릅니다.
궁금한 점 있으면 질문 주세요! 😊