wjdghks0316   1년 전

const visited = Array.from({ length: K + 1 }, () =>
    Array.from({ length: N }, () => new Array(M).fill(false))
);

- 문제를 해결하기 위해서 3차원 배열을 선언했다. 벽을 부순 회수 K 와 x,y 이렇게 유지를 해 문제를 해결하고자 했다. (낮과 밤은 거리를 % 처리해서 처리함)

- 그런데 위 코드는 17% 에서 메모리 초과가 발생했다…. 다음 코드를 봐보자.

const visited = Array.from({ length: N }, () =>
    Array.from({ length: M }, () => new Array(K + 1).fill(false))
  );

- 위 코드와 다른 부분은 K 를 가장 먼저 접근하는 인덱스에서 가장 나중에 접근하도록 바꾸었다.

- 놀랍게도 이번에는 25%에서 메모리 초과가 발생했다…!!

const visited = Array.from(new Array(N), () =>
    Array.from(new Array(M), () => new Array(K + 1).fill(false))
);

- 대망의 마지막 코드이다. 정답 코드랑 아무리 살펴봐도 다른 점이 없었음에도 계속 틀려서 혹시나 하고 선언 방식을 { length : N } 과 같은 유사 배열 객체를 넘겨주는 방식에서 저렇게 바꾸어 보았다….

- 놀랍게도 메모리 초과가 발생하지 않고 문제를 해결했다…

왜 자바스크립트에서 이런 차이가 발생하는지 궁금해서 찾아본 결과

JavaScript에서 내부적으로 배열의 바깥쪽부터 연속된 주소 공간에 메모리를 배치하려는 최적화가 이뤄지기 때문에, 자주 순회하는 방향에 대해 연속된 메모리 접근이 가능하도록 구성하는 게 유리하다고 합니다.

또한, Array.from({ length: N }) 과 같은 방식은 희소 배열이 될 가능성이 존재하여 Array.from(new Array(N), () => ...) 와 같이 명시적으로 모든 슬롯이 채워진 배열을 생성하고 채워 넣음으로서 메모리 최적화를 할 수 있다고 합니다.

정답 코드랑 로직이 똑같은데 왜 자꾸 메모리 초과가 발생하지 하고 몇 시간동안 비교해 본 결과 알게되었네요....
혹시나 자바스크립트로 풀다가 막히면 한 번 적용해봐도 좋을 것 같습니다..

댓글을 작성하려면 로그인해야 합니다.