동적 배열
동적 배열은 크기를 변화시킬 수 있으면서도 O(1)의 접근 시간을 유지한다. 통상적으로
배열이 가득 차는 순간, 배열의 크기를 두 배로 늘린다. 크기를 두 배 늘리는 시간은 O(N)이지만, 자주 발생하는 일이 아니라서 상환 입력 시간으로 계산 했을 때 여전히 O(1)이 된다.
JavaScript에서 배열은 해시 테이블 기반 객체입니다. JavaScript에서 배열은 특별한 형태의 객체입니다. 내부적으로는 키가 문자열인 해시 테이블과 유사하게 구현되어 있으며, 배열의 인덱스는 문자열 키로 변환이 됩니다.
- 밀집 배열(Dense Arrays): 인덱스가 연속적이고 동일한 타입의 요소를 가진 배열은 C언어와 비슷한 연속적인 메모리 블록에 저장됩니다. 이것이 ArrayList와 가장 유사한 구현 방식입니다.
// 배열 생성
const arr = [];
// 요소 추가 - 내부적으로 크기가 자동으로 조정됨
for (let i = 0; i < 1000; i++) {
arr.push(i);
}
// 중간에 요소 삽입 - 모든 후속 요소가 이동해야 함
arr.splice(1, 0, 'new item');
// 임의의 인덱스에 값 할당 - 필요하면 배열 크기가 자동으로 확장됨
arr[5000] = 'far away'; // 인덱스 1000~4999는 비어있는 희소 배열이 됨
희소 배열(Sparse Arrays) 은 일부 인덱스 위치에만 값이 있고 많은 위치가 비어 있는 배열입니다. 인덱스가 불연속적이거나 큰 간격이 있는 배열은 해시 테이블과 유사한 구조로 구현됩니다.
실제 값이 있는 요소만 메모리에 저장됩니다. 비어 있는 인덱스는 메모리를 차지하지 않습니다. 하지만 희소 배열의 경우 밀집 배열에 비해 접근 시간이 더 오래 걸릴 수 있습니다. 일반적인 배열은 O(1) 시간 복잡도로 요소에 접근할 수 있지만, 희소 배열은 해시 테이블 조회가 필요하므로 최악의 경우 O(logn) 또는 그 이상이 될 수 있습니다.
반면 밀집 배열(Dense Array) 는 연속된 메모리 블록에 데이터를 저장합니다. 이 메모리 주소는 다음과 같은 간단한 공식으로 계산이 됩니다.
요소의 메모리 주소 = 배열의 시작 주소 + (인덱스 * 요소 크기)
이 계산은 단순한 산술 연산이기 때문에 O(1)의 시간 복잡도를 가집니다. 이와 반대되는 희소 배열의 접근 방식에 대해서 이야기 해보겠습니다.
희소 배열은 해시 테이블과 유사한 방식으로 구현이 된다고 하였던 이유는 인덱스에 대한 접근 방식 또한 유사하기 때문입니다.
- 인덱스를 해시 함수를 이용하여 해시 값으로 변환합니다.
- 해시 테이블에서 해시 값에 해당하는 버킷 위치를 결정합니다.
- 버킷에서 키(인덱스)와 일치하는 항목을 검색합니다.
- 출동리 있는 경우 추가 검색을 수행합니다.
이 과정은 단순 산술 연산보다 훨씬 복잡하며, 최악의 경우 O(n), n은 전체 배열의 길이 시간이 걸릴 수 있습니다.(실제로는 대부분의 경우 O(1)에 가깝지만, 해시 충돌이 많을 경우 성능이 저하됩니다) 밀집배열과 희소배열의 성능 차이는 아래의 결과와 같습니다.
성능 테스트 시작...
===== 밀집 배열 테스트 =====
밀집 배열 생성: 0.011ms
밀집 배열 랜덤 접근: 14.28ms
밀집 배열 순차 접근: 0.019ms
===== 희소 배열 테스트 =====
희소 배열 생성: 67.088ms
희소 배열 존재 요소 접근: 78.018ms
희소 배열 무작위 접근: 24.5ms
희소 배열 순차 접근 (처음 1000개): 0.028ms
===== 객체(해시 테이블) 테스트 =====
객체 생성: 33.315ms
객체 존재 키 접근: 103.308ms
객체 무작위 키 접근: 93.199ms
===== 메모리 사용량 분석 =====
밀집 배열 (1000개 요소) 메모리: ~8000 bytes
희소 배열 (10000000개 인덱스, 100000개 실제 요소) 메모리: ~800000 bytes
객체 (100000개 키) 메모리: ~800000 bytes
성능 테스트 완료!
밀집 배열의 경우 접근하는 인덱스에 대한 값에 대한 계산이 단순한 산술 연산이기 때문에 O(1)을 보장하지만 희소 배열의 경우 그렇지 않습니다. 희소배열의 경우 해시 값을 계산하는 과정에서 오버헤드, 어떤 처리를 하기 위해 안정성들을 고려하고 크기가 조정될 때 마다 재해싱 하는 과정으로 인해 부가적인 시간이 발생할 가능성이 높습니다.
배열의 크기를 늘리는 상환 입력 시간은 왜 O(1)이 되는가
상환 입력 시간(Amortized Time Complexity) 은 자료구조나 알고리즘의 연산이 최악의 경우 가끔 비효율적으로 동작하더라도, 전체 연산들의 평균적인 시간 복잡도를 분석하는 방식입니다.
이 배열의 크기를 늘릴 때 마다 얼마나 많은 원소를 복사해야 하는지 역으로 계산해 볼 수 있습니다. 배열의 크기를 K로 늘리면 그 전체 배열의 크기는 K의 절반이었을 것이므로 K/2 만큼의 원소를 복사해야 합니다.
따라서 N개의 원소를 삽입하기 위해서 복사해야 하는 원소의 총 개수는 N/2 + N/4 + N/8 + ... + 2 + 1 이 되므로 N 보다 작은 경우가 보장이 됩니다.
문자열
많은 프로그래밍 언어에서 문자열(String)은 불변(immutable) 객체 입니다. 이는 문자열이 한 번 생성되면 그 내용을 변경할 수 없다는 것을 의미합니다. 따라서 문자열을 조작하는 모든 작업(결합, 삽입, 삭제 등)은 새로운 문자열 객체를 생성하게 됩니다.
JavaScript에서도 문자열도 불변 객체입니다. 문자열을 변경하는 어떤 연산도 실제로는 새 문자열을 반환합니다.
let str = "Hello";
str += " World"; // 새로운 문자열 "Hello World"가 생성됨
이 코드는 "Hello"와 " World"를 결합한 새 문자열을 생성하고, 변수 str이 이 새 문자열을 참조하도록 합니다. 원래 "Hello" 문자열은 변경되지 않습니다. 이러한 방법의 단점을 자세한 예시를 이용해 설명해보겠습니다.
function joinWords(words: string) {
let sentence = '';
for (const w of words) {
sentence = sentence + w;
}
return sentence;
}
문자열의 길이가 x라고 하고 같은 n 개의 문자열이 주어졌다고 가정 해보겠습니다. 두 개의 문자열을 이어붙일 때마다 두 개의 문자열을 읽어 들인 뒤 문자를 하나하나 새로운 문자열에 복사해야 합니다.
이 경우 처음에는 x개, 2x개, 3x개 ... nx개의 문자를 복사해야 합니다. 따라서 총 수행 시간은 O(x+2x+...+nx) 이므로 O(xn^2) 가 되므로 굉장히 비효율적이기 때문에 StringBulider를 사용하여 이 문제를 해결하고자 하는 것입니다.
JavaScript에서는 StringBulider 클래스가 없지만 비슷한 패턴을 구현하는 여러 방법이 있습니다.
const parts = [];
for (let i = 0; i < 1000; i++) {
parts.push(`Item ${i}`);
}
const result = parts.join(""); // 모든 부분을 하나의 문자열로 결합
이 방법은 많은 문자열을 결합할 때 가장 효율적인 방법 중 하나입니다. 배열에 추가하는 작업은 O(1)에 가까운 시간 복잡도를 가지며, join() 연산은 모든 문자열을 한 번에 결합합니다.
let result = "";
for (let i = 0; i < 10; i++) {
result += `Item ${i}`;
}
이 방법은 반복 횟수가 많아지면 성능이 크게 저하되기 때문에, 이유는 앞서 설명 했습니다. 길이가 짧을 경우에만 사용해야 합니다.