배열 선언을 x-y가 아니라 y-x순으로 작성하는 이유

 이전 마방진 포스트에서 배열 선언은 x-y가 아니라 y-x순으로 작성하는 것이 효율적이라고 말씀드린 적이 있습니다. 오늘은 어째서 y-x순이 더 효율적인지에 대해 포스트합니다.

홀수 마방진 풀기

---

메모리 구조

  먼저 이 문제를 알아보기 전에 메모리 구조를 알아볼 필요가 있습니다. 메모리 구조를 다루는 포스트가 아니니 이번엔 정말 단순하게만 설명합니다.

 

 컴퓨터에서 메모리라고 한다면 일반적으로는 RAM(주기억장치)을 지칭합니다. 이 메모리라는 것을 운영체제는 선형으로 관리합니다.

운영체제가 관리하는 스타일(?). 메모리를 선형으로 관리합니다.

 때문에 다차원 배열로 선언을 하더라도 결국 메모리는 선형으로 관리가 되는것이죠. 귀찮아서 그렇지 다차원 배열은 일차원 배열로 구현할 수 있습니다.

---

구현 방식

 아래 3X3의 char 이차원 배열을 만들었습니다. 공간 안의 숫자는 다음 설명을 위해 추가한 주석이라고 보시면 됩니다.

3X3 의 이차원 배열

 위 공간은 메모리에서 아래와 같이 관리됩니다.

이차원 구조가 아닌 일차원의 선형으로 관리가 되고 있습니다.

 여기까지는 x-y가 더 나은지 y-x가 더 나은지의 문제가 없습니다. 그러나 각 위치에 접근할 때 연산이 달라집니다.

 만일 x값을 1 증가하면 인덱스 1에서 인덱스 2로 넘어가고 그 위치의 메모리 주소는 100에서 1만큼 증가한 101이 되겠네요.

인덱스 1에서 인덱스 2로 이동

 그러나 y값이 1 증가하게 되면 인덱스는 1에서 4로 이동합니다. 그 결과 메모리 주소는 100에서 3만큼 증가한 103이 됩니다. 즉, 1만큼 증가하는 것이 아니라 3만큼 증가하게 되는 것이죠.

 이런 식으로 x-y로 진행이 되면 더해야하는 수가 더 늘어나게 됩니다. 어셈블리어로 변경되고 나면 거기서 거기일테지만, 이런식으로 계산이 이루어지면 CPU에서 제공하는 속도향상 기술을 사용하지 못할 수도 있으니 y-x순으로 작성하라고 권장하고 있습니다.

 굳이 x-y로 작성하고 싶다면 x가 이중 반복문에서 바깥의 반복문이 되도록 하는것이 좋습니다. 일반적으로 x를 우선해 변경하고 x가 끝에 다다르면 y의 값을 변경하기 때문에 y-x순으로 작성하라고 권고하는 것입니다.