1. 배열

오버헤드가 작다

배열 경계 내에서는 단편화 위험도 없기 때문에 정적인 데이터에는 최적의 데이터 구조

동적 데이터에는 복잡해 지고, 데이터 복사를 할 필요가 있다. 이 때문에 필요한 footprint도 크게 된다.

 

 

2. 리스트

대단히 동적인 성질의 작은 데이터 셋을 저장하기에 적합한 데이터 구조

접근 오버헤드는 배열보다 크고 단편화 위험도 있다.

동적인 요소의 삭제, 추가는 빠르고 요소 저장에 필요한 메모리 이상의 footprint는 필요 없다.

검색은 리스트의 종류(쌍 방향, 단 방향)에 의해서 꽤 시간이 걸리는 경우가 있다.

 

 

3. 해시 테이블

대량의 데이터 셋에 적합한 데이터 구조로 하나의 키 ?또는 분산 키 함수(해시 함수)를 설계할 수 있다.

해시 테이블 구현에서는 필요한 만큼 이외의 데이터 구조를 사용할 수 있다. 이것에 의해서 오버헤드는 배열과 같은 정도로 된다면 다른 데이터 구조를 결합 시키고 싶을 정도로 된다.

 

 

4. 바이너리 트리

대단히 동적인 대량의 데이터 저장에 적합.

데이터는 정렬하지 않고 저장, 삭제할 필요가 있다.

접근 오버헤드는 리스트 보다 커서, 평형화 되어 있지 않으면 리스트와 같을 정도로 비효율적이다.

 

 

5. 레드 블랙 트리

대단히 동적인 대량의 데이터에 적합한 데이터 구조.

접근 오버헤드는 보통 바이너리 트리 보다 크지만 요소를 어떠한 순서로 추가, 삭제하여도 평형이 유지된다.

메모리 단편화 위험은 배열 이외의 다른 데이터 구조와 같이 높고 요소의 삽입과 삭제에는 보통의 바이너리 트리 보다 시간이 걸린다.

대량의 데이터가 있는 경우 주사(走査)(평형이 보증 되어 있기 때문에)와 검색이 빠르다




출처 : 서적 "C++ 퍼포먼스 전략" 에서...

신고
by 흥배 2009.03.21 20:52
| 1 |