[자료구조] 배열의 성능 분석

해당 본문은 학교수업시간에 배운 강의내용을 기반으로 정리하는 요약글 입니다. 정확하지 않은 점이 있으면 지적해주시면 감사하겠습니다.

배열의 성능 분석

우선 배열의 정의부터 살펴보고 시작하자.

Array: 동일한 type이 연속된 주소에 저장된다.

 

같은 배열이라도 값이 한쪽에 모여있을 수 도 있고, 산발적으로 흩어져 있을 수 도 있다.

또 값들이 순서대로 정렬되어 있을 수도 있고 그렇지 않을 수도 있다.

 

이러한 특성들이 배열의 성능에 큰 영향을 미친다고 한다. 또한 값을 Array에 넣는 방식에 따라서 Search, Insert, Delete의 성능이 달라진다.

 

● Packed vs Unpacked

원소들이 저장될때 배열의 한쪽으로 몰아서 저장할 것인가? 아니면 산발적으로 흩어지게 저장할 것 인가?

 

● Sorted vs Unsorted

원소들이 저장될때 정렬된 상태를 유지할 것 인가? 아니면 정렬하지 않을 것 인가?

 

각 케이스 별로 2 x 2 총 4가지 경우를 공부하여보자.

 

Packed, Unsorted

 

▶ 가장 간단한 방법이다.

▶ 원소(아이템)의 개수를 표시하는 변수가 따로 필요하다. 개수를 표시하는 변수는 왜 따로 필요한 것 일까?

우선 Packed 배열에서는 사용 하는 자리가 한쪽으로 몰려있다. 그렇다면 값이 없는 부분을 어떻게 알까?

이를 위해서 array에 몇개의 원소가 저장되어있는지를 표시하는 count 변수가 따로 필요한 것 이다.

 

Search : O(N) , Linear Search

 

Insert : [Search, O(N)], O(1)

insert를 하기 전에도 search를 먼저 한번 실행해야 한다. 같은 값을 2번 삽입하는 중복은 막기 위해서 이다.

 

Delete : [Search, O(N)], O(1)

위의 배열에서 value 3을 삭제한다고 해보자. 지워진 3의 자리에 value 4를 이동시킨다. unsorted 이기 때문에 굳이 삭제한 원소 뒤의 모든 원소들을 한칸씩 앞당길 필요는 없다.

 

이 배열은 insert와 delete가 빠르기는 한데 search가 느리다. 문제는! insert, delete를 하기전에도 search를 선행해야한다는 점 이다. 따라서 n이 작은 자료구조에 용이하다.

 

Packed, Sorted

▶ sorting이 이미 되어있다. 따라서 Binary Search 를 이용하면 탐색의 성능이 좋아진다.

▶ 위의 배열은 값이 있는 원소들이 왼쪽에 한쪽으로 몰려서 Packed 되어있으며, sorting까지 되어있는 상태이다.

▶ 아직도 원소(아이템)의 개수를 표시해준 count 변수가 따로 필요하다.

 

Search : O(logN), 이진탐색을 사용해서 성능이 좋다.

 

Insert : [Search, O(logN)], O(N)

insert 하기전에 search를 먼저 진행하는데, 해당 값이 이미 있으면 있다고 or 없으면 어느 두 수 사이에 삽입해야 되는지 나온다. 어느 두 수 사이에 삽입해야하는 지를 알면 원래의 값들을 뒤로 한칸씩 밀고 그 자리에 삽입해 준다.

 

Delete : [Search, O(logN)], O(N)

탐색을 진행하여 해당 값을 찾고, 삭제하고, 삭제된 원소의 뒤이은 원소들을 앞으로 한칸씩 앞당긴다.

 

Search는 빠르지만 Insert와 Delete가 느리다. 따라서 Insert, Delete는 자주하지 않고 Search만 자주하는 자료구조에 용이 (Search는 빠르므로) 하다. 예로는 사전과, 네비게이션이 있다. 이들의 자료는 거의 바뀌지 않는다.

 

 

Unpacked, Unsorted

▶ 빈 자리들이 흩어져 있다.

▶ count 변수는 있을수도 있고 없을수도 있다.

▶ 원소(아이템)별로 사용중인지를 따로 표시해줘야 한다. 예를 들어 bit map 이 있다.

 

Search : O(N)

같은 O(N)이어도 packed보다 조금 더 안좋은 성능을 보여줄 수 있다. packed되있는 배열은 count 변수가 있어 이부분만 에서 찾으면 되지만, unpacked는 배열 끝까지 항상 다 확인해야하기 때문이다.

 

Insert : [Search, O(N)], O(n) --- Free List Head 활용 ---> O(1) 으로 개선 가능

위의 배열에서 7을 삽입한다고 해보자.

1) 우선 배열에 7이 있는지 search를 선행해야 한다. -> 없음을 확인

2) 안쓰는 자리를 search 해서 삽입해야 한다. 이렇게 되면 삽입연산도 복잡도가 O(n)이 되어버린다.

 

하지만 위에써있듯 Free List Head를 사용하면 O(1)로 성능을 향상시킬 수 있다. 그도 그런것이 이미 처음 7이 배열에 있는지 확인하는 과정에서 search를 진행하지 않았는가? 이때 빈 자리도 확인이 가능하단 말이다.

 

Free List Head: 줄여서 우선 h라고 하자. h변수에는 배열의 빈 자리의 index가 담겨 있다. 그럼 그자리에 가서 값을 삽입하면 되는데, 중요한 점은 그 index에 가보니 다음 빈 자리의 index가 저장되어 있다는 점 이다. 꼬리를 물고 다음 빈 index의 위치를 알려주고 있다.

 

Delete : [Search, O(N)], O(1)

값이 있는지 탐색후, Mark만 바꿔주면 된다.

 

Unpacked, Sorted

위의 배열을 보면 value가 없는 곳들에 ?로 되어있다. 이 상황에서 Binary Search가 가능할까? sorting 되이있지 않은가?

만약 이진탐색을 하다 index 4를 보게 된다면 우리가 찾으려는 값은 index 4의 value인 ?보다 클까? 작을가? 알수가 없다.

 

이를 해결하는 방법이 있다.

 

1) 초기에 insert를 할때는 Packed 로 진행한다.

 

2) 만약 값 8을 지우고자 하면 O, X만 변경하고 값은 유지시킨다.

 

3) 지우더라도 값들이 sorting 되어 정렬상태를 유지한다. => 이진탐색이 여전히 가능하다.

 

Search : O(logN)

Packed되어있을 때보다는 N이 커지겠지만 log기 때문에 이 차이는 매우 작다.

 

Insert : [Search, O(logN)], O(N)

만약 위의 배열에서 6을 삽입 한다고 해보자. 그럼 search를 진행하면 삽입할 위치로 index 1 과 2사이가 나온다.

하지만 양쪽에 5와 7이라는 값이 이미 있다. 이때 양쪽 모두를 확인해서 빈곳이 을 찾아야 한다. 예를 들어 위에서는 7쪽 방향으로 빈칸인 index 3이 발견된다. 따라서 index 3으로 index2의 정보를 한칸 민다. 이후 공백이 된 index2에 우리가 삽입하려 했던 6을 삽입한다.

 

이렇게 되면 8을 없어졌지만, 여전히 sorting된 상태를 유지한다.

 

또한 이전의 packed처럼 삽입후 끝까지 한칸씩 미는것 이 아니라, 빈자리까지만 밀면 되기때문에 조금더 개선된 O(n)이다.

 

Delete : [Search, O(logN)], O(1)

위에서 그림으로 보였듯 지우고 마크만 변경