'Basic Knowledge'에 해당되는 글 1건
- 2012.07.01 :: 배열
1. 배열은 가장 간단한 자료구조이다.
2. 배열의 임의 항목에 접근할 때 알고리즘의 복잡도는 O(c) 이다. (상수)
3. 배열과 포인터는 접근 방식이 동일한다. 배열의 한 항목에 접근할 때, 컴파일러는 배열의 시작 위치를 가리키는 포인터를 취하고 그에 기반해서 해당 항목이 있는 위치를 계산한다. 이때문에 배열의 크기와 상관없이 항상 한번의 곱셈과 한번의 덧셈으로 일어난다.
4. 배열의 삭제
- 중간에 있는 배열의 값을 삭제하면 하나씩 땡겨야되서 속도 저하가 크다.
- 순서가 중요하지 않는 데이터일 경우 배열의 마지막 값을 제가하고자 하는 값에 덮어씌우고 마지막 값을 없애면 하나만 이동하게 된다.
- 예제 : 몬스터 제거 알고리즘
var RemoveMonster = function(idx){
g_monsters.length--;
g_monsterArray[idx] = g_monsterArray[g_monsters.length];
}
- 제거 판단 알고리즘
var CheckMonsters = function(){
var idx = 0;
while( idx < g_monsters.length ){
if( g_monsterArray[idx].m_hitPoints <= 0 )
RemoveMonsters( idx ); // 마지막 배열요소로 덮어씌운 후
다시 while 문으로 돌아가 덮어씌운 요소를 검사한다.
else
idx++; // 인덱스는 덮어씌우지 않은 경우만 증가
}
}
5. 배열의 장점
- 생성하기 쉽다.
- 접근하기가 빠르다.
- 관리하기 쉽고 필요할 때 파괴하기도 쉽다.
- 프로세스는 배열을 처리하는 데 최적화되어 있다.
6. 배열의 단점
- 캐시 문제 : 하나의 루프를 통해서 배열을 흝어나갈 때에는 별 문제가 없지만 배열의 칸들에 임의로 접근할 때에는 메모리의 상당 부분을 이리 저리 옮겨야 하는 상황이 벌어진다.
- 배열의 크기 변경 문제 : 배열의 크기 변경은 O(n) 알고리즘이다. 배열이 클수록 변경에 걸리는 시간도 길어진다.
- 항목의 삽입, 제거 : 배열 항목들의 순서를 유지하면서 항목을 삽입하거나 제거하는 것이 어렵다. 이 알고리즘 역시 O(n) 이며 배열이 클수록 수행 시간이 길어진다. 항목들의 순서를 유지할 필요가 없다면 빠른 제거 알고리즘을 사용할 수 있겠지만, 순서를 유지해야 한다면 느린 선형 알고리즘을 사용할 수밖에 없다.
7. 1차원 배열의 크기 Resize 알고리즘
var Resize = function(re_size, original_size){
var newArray = new Array[re_size];
if(new Array === 0)
return;
var min;
if(re_size < original_size)
min = re_size;
else
min = original_size;
var index;
for(index = 0; index < min; index++){
newArray[index] = original_array[index];
}
original_size = re_size;
if(original_array !== null)
original_array = null;
original_array = newArray;
}
8. 배열과 루프
- 다차원 배열에서 신경을 써야 하는 부분은 배열을 흝어나가는 방식이다. 가장 안쪽 루프에서 거쳐가는 차원이 어떤 것인가 하는 점인데 예를 들어 2차원 배열을 흝을 때 안쪽 루프가 수평 x 좌표를 증가시키는 방식인 경우 각 행을 왼쪽에서 오른쪽으로 차례로 흝는 것이지만 안쪽 루프가 수직 y 좌표를 증가시키는 방식인 경우 순차적인 색인이 아닌 띄엄띄엄 흝게 된다. 이렇게 되면 캐시의 효율이 크게 떨어진다.