배열(Array)
먼저 배열에 대해 가볍게 알아본다.
배열은 동일한 크기의 메모리 공간을 연속적으로 나열한 구조다.
동일한 크기여야 하므로 하나의 통일된 타입의 요소들이, 연속적으로 인접해있는 형태를 보인다.
위처럼 "데이터가 연속으로 인접한 배열"을 밀집배열(dense array)라고 한다.
밀집배열의 경우, 인덱스를 이용해 한번의 연산으로 접근이 가능하다.
연산 횟수가 1회이므로, O(1)의 시간복잡도를 보인다.
배열의 단점
인덱스(찾으려는 데이터의 위치)를 모르면 선형탐색을 해야한다.
- 선형탐색은 O(n) 시간복잡도.
배열 마지막 요소가 아닌 위치에 추가/삭제 시 배열 요소들의 연속적인 이동이 필요하다.
- 삽입과 삭제에서 O(1) ~ O(N)의 시간복잡도.
tmi) 왜 장점과 단점들을 따지는가?
리스트를 만들 때 보통 2가지 자료구조를 생각한다.
1. 배열기반 리스트 (Array)
2. 연결 리스트 (Node, Vertex)
배열기반 리스트
인덱스 참조에 O(1)의 놀라운 성능을 보인다.
탐색에 O(1) ~ O(N), 삽입과 삭제에는 O(1) ~ O(N)이다.
탐색 + 삽입/삭제가 빈번하게 일어나야한다면 좋지 않은 선택이다.
데이터의 인덱스를 알고있는 상황이라면 좋은 선택일 수 있다.
연결 리스트
노드들을 포인터로 연결한 구조로, 인덱스 참조가 불가능하다.
다음 노드로의 포인터가 필요하므로, 추가 메모리가 필요하다.(데이터 + 다음 노드정보 2가지를 기억)
탐색에 O(N), 삽입과 삭제에는 O(1)이다.
탐색 속도는 배열기반과 같으나, 삽입과 삭제에서 강점을 보인다.
삽입/삭제가 빈번하게 일어나야 한다면 좋은 선택일 수 있다.
각 장단점을 먼저 파악하고, 해결해야 할 문제에 적합한 자료구조를 선택하는 것이 매우 중요하다고 할 수 있다.
자바스크립트의 배열 알아보기
사실 자바스크립트 배열은 위에서 알아본 배열과 꽤 다르다.
1. 우선, 동일한 크기일 필요가 없다. 그래서 다른 타입의 요소를 넣어도 된다.
2. 연속적으로 이어지 않아도 된다.
위에서 밀집배열(dense array)를 언급했는데,
자바스크립트의 배열은 sparse array(희소 배열)이 될 수 있다.
(ex. Array를 선언하고 0,1번을 건너뛰고 2번 인덱스에 바로 원소를 넣어줄 수 있다.)
자바스크립트에서의 배열은 일반적인 배열이 아니다.
배열의 동작을 흉내내는 특수 객체다.
모든 자료구조를 넣을 수 있으며, typeof의 결과로 object가 등장한다.
배열의 프로토타입이 Array.prototype이며,
Array.prototype의 상위 프로토타입이 Object.prototype이다.
심지어는 배열에 숫자 인덱스가 아닌 'hello'라는 프로퍼티도 만들 수 있다.
그렇다면 자바스크립트 배열에서
arr[1] = 2가 의미하는 것이,
"연속된 공간에서의 주소값 기준 인덱스만큼의 크기 뒤에 있는 주소값에 담긴 값"의 의미가 아니게 된다.
0,1,2번 인덱스는 객체에서 key에 해당한다.
0,1,2번 인덱스에 담긴 12, 'string', false 값은 객체에서 value에 해당한다.
대신, 아래의 Array.prototype으로 배열로서 필요한 기능들을 지원하고 있다.
물론 그렇다고 해서 Object로 만든 배열과 Array로 만든 배열의 성능이 동일하진 않다.
실제로 배열과 객체를 만든 뒤에, 프로퍼티에 삽입해주면
Object에 비해 Array가 약 2배정도 빠른 것을 볼 수 있다.
이는 자바스크립트 엔진에서, 배열을 좀 더 배열처럼 동작할 수 있게 인덱스 접근을 최적화한 결과라고 한다.
객체로 배열을 만들면 뭐가 다른데...?
우선, 일반 배열보다 인덱스접근의 성능이 떨어진다.
일반 배열의 인덱스 접근은 메모리주소 + 위치참조로 O(1)의 성능이 기대된다.
자바스크립트에서는 해시함수로 위치를 찾아야 하므로, 해시함수의 성능에 따라 달라진다.
그래서 일반적으로, 인덱스 접근보다 성능이 떨어질 수 밖에 없다.
대신 삽입/삭제에서는 더 성능이 좋다.
일반 배열에서는 중간에서 삽입/삭제가 일어나면 메모리에 데이터들을 직접 옮겨가야 한다.
물론 삽입/삭제에서 성능이 좋아졌다곤 해도, 노드기반 삽입/삭제에 비할바는 못된다.
삽입/삭제가 빈번하다면, 배열리스트보다는 연결 리스트가 유리하다.
객체이기 때문에 메모리, 자료구조의 유연함을 가진다.
배열은 배열 크기만큼 메모리공간을 미리 확보해둬야 한다.
"미리 확보"해야 하기 때문에, 동일한 원소크기 + 정해진 배열크기를 요구한다.
객체를 기반으로 한다면, 공간을 미리 확보할 필요가 없다.
덕분에 배열에 보관할 자료구조에 대한 제약이 없다.
(사실 원소를 넣기 전에는 크기를 알 수 없으니, 메모리를 미리 확보할 수도 없다.)
물론 그래서 자바스크립트의 Array를 객체처럼 써도 상관없는 것은 아니다.
이미 자바스크립트 엔진에서는 Array가 배열스러운 동작을 할 수 있도록 최적화되어있기 때문.
마치며
사실 배열을 다루면서 무조건적으로 알아야 하는 내용은 아닌 것 같지만, 알아둬도 나쁠 것은 없다.
배열 인스턴스의 length 프로퍼티를 항상 이상하게 생각해왔던 의문을 풀고자 공부하게 된 내용이다. ㅎㅎ..
실제 개발 or 코딩테스트시 좀 더 도움이 될 내용을 적어보면,
배열에서 push,pop이 아닌 unshift, shift, splice 메서드를 많이 사용해야 한다면?
- 시간복잡도를 먼저 생각하자. 배열리스트보다 연결리스트가 더 나을 수 있다.
- 위 상황에 대비하기 위해, 연결리스트정도는 스스로 만들어보는 것이 좋다.
typeof 배열이 'object'인데 그럼 어떻게 배열인지 타입검사하나요?
- 스태틱 메서드인 Array.isArray 활용하자.
일정한 크기의 0으로 초기화된 Array를 어떻게 선언하나요?
- 나는 Array.from({length: n}, () => 0); 의 방법을 선호한다.
- 좀 더 간단한 new Array(n).fill(0)도 있으나, 원시값이 아닌 참조값을 각 배열에 선언할 때 문제가 되기 쉽다.
- 2차원 배열을 만들고자 할 때
- Array.from({length: n}, () => new Array(m).fill(0)); 은 n행에 담긴 m크기의 배열이 각각 선언된다.
- new Array(n).fill(new Array(m).fill(0)); 로 선언하면, 동일한 new Array(m).fill(0)이 n행에 담기는 문제가 있다.
- 물론 원시값을 가지면 new Array(n).fill(0)이 제일 편하다.
- 각각의 스타일대로 선언하자. []로 만들고 for문으로 하나씩 넣어줘도 된다.
'JavaScript > theory' 카테고리의 다른 글
[자바스크립트] sort함수는 왜 숫자를 이상하게 정렬할까? (0) | 2023.01.25 |
---|---|
엄격모드. "use strict" (0) | 2022.07.20 |
이벤트 위임, 버블링, 캡쳐링 (Event Delegation, bubbling, capturing) (0) | 2022.07.11 |
[함수형] 커링 Currying을 배워보자. (0) | 2022.06.01 |
[자바스크립트] 마이크로 태스크 큐의 비동기 작업 처리와 렌더링 시점을 알아보자. (1) | 2022.04.14 |