Array란
Array는 길이가 정해진 연속된 아이템 배열이라고 할 수 있다. 이 문장에서의 핵심은 '길이가 정해진' 과 '연속된'이다. 이 두가지 특징을 생각하며 아래 내용을 읽어보자.
우선 Array object를 생성하면 sequence of memory boxes, 즉 연속된 memory 공간을 할당받게된다. 여기에 더해 memory가 주소를 갖고 있기에 index를 가지고 Array에 순차적으로 접근할 수 있다.
그러나, Array는 결국 그 size가 정해져 있기 때문에 자신의 size를 넘어서는 아이템을 저장할 수 없게 된다.
Array에서는 이러한 size의 한계를 극복하기 위해 Dynamic Array라는 개념을 도입하기도 하였고, Python의 List가 이러한 Dynamic Array를 통해 구현되었다.
Dynamic Array / Python List
Array에 존재하는 size와 관련된 단점을 극복하고자 도입된 것이 Dynamic Array이고 우리가 python을 사용하면서 일반적으로 사용하는 'List' DataStructure가 바로 Dynamic Array라고 볼 수 있다.
앞선 언급했듯 Array의 size와 관련해서는 두가지 issue가 있을 수 있다.
-
memory shortage
Array의 초기 size를 N으로 설정한 경우, N개보다 더 많은 아이템을 넣으려고 하면, 모든 memory가 꽉차 memory shortage현상이 일어난다. -
memory wastage
Array의 초기 size를 넘어서는 양의 아이템(데이터)를 저장할 수 없다면, 처음부터 그 size를 엄청나게 크게 설정해버리는 경우 1차원적으로 문제를 해결할 수는 있다. 그러나 이 경우 해당 size만큼 memory는 잡혀있지만 원소가 들어있지 않은 memory가 대다수가 되어 memory wastage가 일어난다.
--> 따라서 array resizing은 필수적이게 되고, 이러한 resizing을 하는 Array를 Dynamic Array라고 한다!.
Dynamic Array가 resizing 하는 방법은 다음과 같다.
- size가 N인 Array가 꽉 찬 상태에서 append 가 실행되면 다른 공간에 size가 N+1인 Array를 새로 만든다.
- 기존의 Array에 있던 아이템들을 모두 새로만든 Array로 copy 시킨다.
- 새로운 Array의 N+1번째 index에 새로운 값을 append 해준다.
이것이 실제 Dynamic Array resizing 과정이다. 이 과정은 결국 새로운 memory를 만들고, 기존 값의 copy도 일어나기 때문에 cost가 굉장히 큰 task이다.
이러한 resizing cost를 줄이기 위해서 Python list size는 특이한 방식으로 커진다. 단순 N size의 array가 꽉 찼다 해서 N+1 size로 resizing 하는 것이 아니라 좀 더 여유를 두고 하는 것이다.
0, 4, 8, 16, 25, 35, 46, 58 ...
이런식으로 단순 1 증가가 아닌 좀 더 여유가 있는 size로 resizing을 진행한다.
이를 통해 resizing 되는 횟수를 줄이면서도, dynamic한 크기의 array를 사용하는 것이다.
또한 애초에 resizing에 구애를 받지 않기 위해 Linked List라는 DataStructure를 사용하기도 한다.
Amortization
이 Amortization은 resizing size와 연관지을 수 있는 개념이다. 단순히 얘기하면 일정한 size(1,2,4, 8, ... 2^n)를 확정해두고 resizing을 진행하면 array의 element를 추가하는 작업의 time complexity가 평균적으로 O(1)이 되게 할 수 있다. 물론 '평균'적이라는 의미가 항상 그러하다는 것은 아니나, 대부분의 경우 O(1)이 될 것이라는 의미이다.
자세한 설명은 다음 글을 참고하면 된다.
