ps 문제를 풀고 난 뒤 해당 문제의 남의 코드를 구경하는 곳이 있다. 고수들이 작성한 마치 예술과도 같은 숏코드와 거기에 달린 평가 덧글도 구경할 수 있는데, 그것을 보던 중 새로운 사실을 알게 되었다.
배열하나가 입력으로 들어오고 이상한 조건들을 풀어낸 뒤 다시 배열을 return하는 함수 작성이 필요한 문제였다.
const solution = array => {
...
(어떤 과정)
...
const array2 = 중간array.sort((a,b) => a - b);
return array.map((x) => 복잡한 조건 ? array2.shift() : x);
}정리해보면 위와 같다. 이 예술작품을 눈과 머리로 즐기다가 이상한 덧글을 발견했다.
덧글에서 어떤 기본 프로필 사진의 은둔고수 외국인이 sort의 순서를 바꾸고 shift 대신 pop을 쓰는 것이 더 빠르다고 훈수를 둔다.
그리고 그 덧글에 달린 덧글에서는 이 훈수를 찬양하는 덧글도 함께 있다.
보자마자 든 생각은 배열의 앞에서 빼나 뒤에서 빼나 한 개의 원소를 제거하고 해당 원소를 반환하는 것은 똑같은 것 같은데 왜 속도가 다른거지? 생각을 했다.
그러다가 갑자기 이런 생각이 들었다. 자바스크립트 내의 배열 구현이 메모리 최적화를 위해 배열 속 원소가 다음 인덱스의 원소를 가리킬 때 주소값을 따로 메모리에 저장하지 않고 무조건 다음 주소값의 원소를 가르키는 그런 방식을 사용해서, 맨 앞의 원소를 빼기 위해서는 두 번째 원소부터 앞으로 한 칸씩 다 당겨주기 위해 그런 것인가?
검색을 했다.
그나마 공식문서 같은 MDN에서 보니 시간복잡도 이야기는 없고, 사용법만 나온다.
다른 여러 검색 결과들을 확인했다.
different time complexity between array methods in js
위의 링크에서 말하기를 Array.prototype.pop()의 시간복잡도는 O(1), Array.prototype.shift()의 시간복잡도는 O(n)이라고한다.
O(n)을 보니 모든 원소를 다 만져줘야 하는 듯한 느낌이 들었다.
실제로 검색을 해보니 위와같은 현상이 나타나는 이유는 array 구조상 내부 모든 원소들이 참조하고 있는 주소들을 변경해줘야 하기 때문이라고 한다. push은 맨 끝에 새로운 주소와 함께 데이터를 넣으면 그만이지만, shift는 0번 주소부터 맨 끝에 있는 원소들의 주소까지 전부 한 칸씩 밀어줘야 한다. 처음에 생각했던 것과 비슷한 느낌인가보다.
unshift도 마찬가지라고 한다. 얘네는 앞으로 한 칸씩 당겨야 하나 보다. push, pop 사용이 가능하면 shift친구들은 사용하지 말아야겠다.
그런데 자바스크립트 인터프리터마다 배열 구현 방식은 모두 다르지 않을까? 대장 엔진인 V8기준으로 말한 것일까? 아니면, 만고불변의 진리마냥 저런 구조로 배열을 만들어야 하는 것이 정답이라 저렇게 말할 수 있는 것일까? 잘 모르지만, 이정도의 로우 레벨의 것은 새로 만드는 인터프리터마다 새롭게 구현하는 것이 아닌가? 잘 모르겠다.
이런 것을 하나 보니, 이것 말고도 수많은 best practice가 존재할 것이라는 것이 느껴졌다. 이런 것들을 하나씩 찾아가며 cpu 사용량을 줄여 에너지를 절감할 수 있지 않을까? 아, 내가 지구를 구했다.
코드 레벨에서 커버 가능한 수준에서는 위와같은 극한의 효율을 통해 cpu연산을 감소하여 탄소 배출량을 줄여주는 친환경 에코 코더가 되어야겠다고 느낀다.