[Data Structure] Linear - (1) Array

---

 파이썬 리스트는 c의 배열을 이용해 만들어졌다. 두 자료구조의 큰 차이점은 정적 배열(Static Array)이냐 동적 배열(Dynamic Array)이냐다. c의 배열은 정적배열로서, 처음에 메모리에 배열의 크기를 정해놓고 시작한다. 즉, 크기가 고정되어 있다. 반대로 파이썬의 리스트는 동적배열로, append()메소드를 이용해 데이터를 추가할 때마다 배열의 크기가 가변적으로 늘어날 수 있고 반대로 del 예약어 등으로 크기가 자동적으로 줄어들 수도 있다.

 

 

---

01. 정적 배열 vs 동적 배열 (Static Array versus Dynamic Array)

 위에 언급한 것처럼 c의 배열은 정적 배열이고, c의 배열을 이용해 만든 파이썬의 리스트는 동적 배열이다.

 

---

정적 배열

c언어의 배열

 

 우선 c의 배열은 int newArray[8]; 와 같은 코드를 이용해 임의의 메모리 공간 내에 크기만큼의 연속된 공간을 마련해 놓고 시작한다. newArray배열은 최대 8개의 int형 자료를 채워넣을 수 있다. 만약 8개를 초과하는 자료를 담아야 할 경우에는, 넉넉한 공간을 가진 새로운 배열을 임의의 메모리 공간에 할당하고 기존의 데이터를 똑같이 복사한 후 새로운 자료를 담아주어야 한다. 이제 몇가지 의문점이 생긴다.

 

 

첫째, newArray배열의 크기가 부족하다면 newArray배열 뒤의 메모리 공간에 이어서 채워넣으면 안되는가

 

의문점 1

 

 하지만 임의로 할당한 메모리 공간 뒤에 어떤 중요한 데이터가 있을지 모르기 때문에 새로운 배열을 할당해 채워넣는 것이 안전하다.

 

 

둘째, 처음 배열을 만들 때 새로 만들 필요없이 넉넉하게 만들면 되지 않은가

 

하지만 500000개의 자료를 넣을 수 있는 배열을 만들어 놓고 5개의 자료만 들어간다면 자원 낭비가 심해진다.

 

 

---

동적 배열

 

 반대로 파이썬의 리스트는 앞서 c의 배열에서 값을 추가하는 과정을 자동으로 수행해준다. new_array = []처럼 처음에 빈 리스트를 할당하고 append() 메소드를 이용해 값들을 추가할 때, 만약 new_array안에 빈 공간이 남아있다면 그대로 값을 추가하고 이미 꽉 차있다면 공간을 두 배로 늘려서 새로 저장한다.

 

import sys

new_array = []
print(new_array, sys.getsizeof(new_array))
for i in range(20):
    new_array.append(i)
    print(new_array, f"크기: {sys.getsizeof(new_array)}", f"주소: {id(new_array)}")

[] 56
[0] 크기: 88 주소: 2459131794048
[0, 1] 크기: 88 주소: 2459131794048
[0, 1, 2] 크기: 88 주소: 2459131794048
[0, 1, 2, 3] 크기: 88 주소: 2459131794048
[0, 1, 2, 3, 4]크기: 120 주소: 2459131794048

(생략)

[0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14] 크기: 184 주소: 2459131794048
[0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15] 크기: 184 주소: 2459131794048
[0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16] 크기: 248 주소: 2459131794048
[0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17] 크기: 248 주소: 2459131794048
[0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18] 크기: 248 주소: 2459131794048
[0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19] 크기: 248 주소: 2459131794048

 

 빈 리스트에 하나씩 값을 추가하면서 변화하는 크기와 주소를 확인하는 코드다. 위 결과를 보면 빈 리스트에는 56바이트가 할당되어 있다. 이는 64비트 시스템에서 리스트의 메타 데이터들이 차지하는 값이다. 그리고 0이란 값이 리스트에 처음 추가될 때, 32바이트가 추가로 할당되고 값들을 저장할 수 있다.

 

 보면 4가 추가되는 시점에, 크기가 120으로 32바이트가 추가되는 것을 알 수 있는데, 여기서 의문점이 생긴다. 기본적으로 c언어의 int형은 크기가 4바이트이며 총 4개가 추가되면 16바이트를 차지하고, 파이썬의 int는 크기가 28바이트이며 4개가 추가되면 112바이트이다. 두 가지 경우 다 32바이트 안에서 저장되는 것이 설명되지 않는다.

 

 결론적으로 이유는 파이썬 리스트는 값 자체를 저장하는 것이 아니라 데이터의 주소를 저장하기 때문이다. 4가 추가되는 시점, 즉 32바이트가 추가될 때 파이썬 리스트는 각 int 객체의 메모리 주소를 가리키는 포인터를 저장하며 64비트 시스템에서 각 포인트의 크기는 8바이트이다. 따라서 4개의 값을 저장할 수 있는 공간이 추가되는 것이다.

 

new_array.append([1, 2, 3, 4, 5])
print(new_array, f"크기: {sys.getsizeof(new_array)}", f"주소: {id(new_array)}")

[0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, [1, 2, 3, 4, 5]] 크기: 248 주소: 1528879862400

 

 따라서 위와 같이 리스트에 int형이 아니라 리스트를 저장한다고 하더라도 포인터의 크기는 고정적이기 때문에 메모리의 크기가 바뀌지 않는 것을 알 수 있다.

 

 마찬가지로 메모리의 주소를 저장하기 때문에 id(new_array) 함수로 출력한 주소값이 1528879862400로 고정적인 것을 확인할 수 있다. 즉, new_array 리스트 객체의 주소는 고정적이고, 그 안의 배열 포인터들만 c언어의 배열과 같이 새로운 메모리 영역에 업데이트된다.

 

---

02. 시간 복잡도 (Time Complexity)

정적 배열, 동적 배열 모두 추가 연산할 경우 시간복잡도는 두 가지 경우의 수가 있다. 배열에 남는 공간이 있을 경우와 배열이 꽉 찼을 경우다.

 

배열에 남는 공간이 있을 경우

배열에 남는 공간이 있을 경우

 이 경우에는 빈 공간에 그냥 값을 추가해주면 된다. 따라서 시간 복잡도는 O(1)이다.

 

 

배열이 꽉 찼을 경우

배열이 꽉 찼을 경우

 배열이 꽉 찼을 경우에는 새로운 배열에 기존 요소들을 복사하고 나서 새로운 값을 추가해야 한다. 이때 기존의 n개의 요소를 복사하는 데 O(n)의 시간복잡도와 새로운 요소를 추가하는 데 O(1)의 시간복잡도가 소요되어 총 O(n + 1)의 시간복잡도가 소요된다. 시간복잡도 정의에 따라 최종적으로 시간복잡도는 O(n)이 걸린다

 

 

분할 상환 분석 (Amortized Analysis)

 분할 상환 분석은 최악의 경우를 산정하는 시간 복잡도와는 달리 어떤 시퀀스의 최악과 최선의 경우의 빈도까지 모두 고려해 평균 비용을 산출하는 기법이다.

 

 위의 시간 복잡도를 산정할 때 배열이 꽉 차 있는 경우는 사실 배열이 남는 공간이 있을 경우에 비해서 매우 가끔 발생한다. 이러한 경우 시간 복잡도를 단순히 O(n)으로 산정하는 것은 비합리적이므로, 결론적으로 추가 연산을 분할 상환 분석을 했을 때는 O(1)이다.