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

배열의 성능분석

같은 배열이라도 값이 모여있을 수 있고 흩어져 있을 수 있다. 또 값들이 순서대로 정렬되어 있을 수 있고 그렇지 않을 수 있다. 이런 특성은 배열의 성능을 결정짓는데에 크게 기여한다. 이를

 

• Packed vs UnPacked (빈 자리를 한 쪽으로 모으느냐? 흩어져 있을 수 있느냐?)
• Sorted vs UnSorted (아이템들이 정렬된 상태를 유지하느냐? 그렇지 않느냐?)

라고 말할 수 있는데, 이를 기반으로 배열을 총 네가지 분류로 나누고 성능을 분석해보겠다.

Packed, UnSorted

• 가장 간단한 방법
• 아이템의 개수를 표시하는 변수가 따로 필요하다
• Search : O(N)
• Insert : [Search, O(N)], O(1) (넣기만 하면됨)
• Delete : [Search, O(N)], O(1) (지우고 아무 값이나 가져오면됨)

cf. Insert, Delete는 보통 Search를 먼저 수행
Search 자체가 느려 n이 작은 자료구조에 용이 (구현이 쉬우므로)

Packed, Sorted

• Binary Search 가능
• 아이템의 개수를 표시하는 변수가 따로 필요하다
• Search : O(logN)
• Insert : [Search, O(logN)], O(N) (넣고 모든 값을 하나씩 밀어줘야함)
• Delete : [Search, O(logN)], O(N) (지우고 모든 값을 하나씩 당겨줘야함)

Search는 빠르지만 Insert와 Delete가 느리다. 따라서 Insert, Delete는 자주하지 않고 Search만 자주하는 자료구조에 용이 (Search는 빠르므로) Sorted가 기본 조건인 이상 사용하기 까다로울 수도 있다.

UnPacked, UnSorted

• 빈 자리들이 흩어져 있다.
• 아이템별로 사용여부를 구분해야한다.
• Search : O(N) (같은 O(N)이어도 packed보다 조금 더 안좋은 성능을 보여줄 수 있다)
• Insert : [Search, O(N)], O(1) (Free List Head를 활용해서 O(N)으로 빈자리를 찾아야하는 일이 O(1)으로 가능해짐)
• Delete : [Search, O(N)], O(1) (지우고 마크만 바꿔주면 됨)

Free List Head? 빈 자리들의 첫번 째 빈자리로 head가 되는 인덱스. 이를 기점으로 각 빈자리에 다음 빈자리의 인덱스가 적혀있다. 마지막에는 -1이 적혀있어 빈자리가 끝났음을 표시. 만약 해당 head를 활용하면 first list head가 바뀐다. File System에서 Free Block List를 만들 때 실제로 사용한다.

UnPacked, Sorted

• 애초에 Mark가 X인 공간에도 값은 존재하므로 이를 포함하면 Binary Search가 가능하다. 물론 Mark가 X인 공간의 값도 Sorted되도록 유지하는 기술이 필요하다.
• 아이템별로 사용여부를 구분해야한다.
• Search : O(logN) (Packed되어있을 때보다는 N이 커지겠지만 log기 때문에 이 차이는 매우 작아진다.)
• Insert : [Search, O(logN)], O(N) (지우고 모든 값들을 하나씩 밀어줘야함, 빈자리를 만날 때까지만 수행하면 된다. 빈자리를 메꿔도 Sort여부는 유지되기 때문이다. 따라서 Packed보다 조금 빠를 수 있다.)
• Delete : [Search, O(logN)], O(1) (지우고 마크만 바꿔주면 됨)