파이썬의 리스트와 튜플

파이썬 리스트와 튜플

컴퓨터의 시스템 메모리는 일련번호를 붙인 바구니의 집합으로, 각 바구니에는 수를 담을 수 있다. 파이썬은 참조를 사용해 바구니에 데이터를 저장한다. 즉 바구니에 담긴 수는 단순히 데이터를 가리키거나 참조하는 번호일 뿐이다. 그 결과 이 바구니는 모든 타입의 데이터를 저장할 수 있다.

배열을 생성하려면 먼저 시스템 메모리 블록을 할당해야 한다. 리스트와 튜플도 마찬가지다. 이때 블록의 각 구역에는 실제 데이터를 가리키는 포인터가 저장되며, 포인터의 크기는 정수 타입의 크기다. 메모리 블록 할당 과정은 커널까지 내려가 연속된 바구니 N개를 요청한다.

리스트에서 특정 항목을 찾으려면 그 항목이 무엇인지, 또 데이터가 어느 바구니에 저장되는지만 알면 된다. 모든 데이터는 같은 크기를 점유하므로 데이터의 종류는 알 필요가 없다.

예를 들어 배열의 0번째 항목을 찾으려면 배열이 시작하는 위치에서 첫번째 바구니의 값(M)을 읽으면 된다. i번째 항목을 읽으려면 M + i 위치를 읽으면 된다. 따라서 연속적엔 메모리에 정렬되어 저장된 데이터는 배열의 크기와 상관없이 한 번에 읽을 수 있다. 따라서 시간복잡도는 O(1) 이다.

리스트는 동적인 배열이다. 수정이 가능하며, 저장 용량을 늘리거나 줄일 수도 있다

튜플은 정적인 배열이다. 일단 생성되면 배열의 크기뿐 아니라 그 안의 데이터도 변경할 수 없다. 튜플은 파이썬 런타임에서 캐시하므로 사용할 때마다 커널에 메모리를 요청하지 않아도 된다.

리스트와 튜플은 다른 데이터 타입을 섞어 쓸 수 있다.

리스트

리스트에 새로운 데이터를 추가하면 크기가 커진다. 이는 동적 배열이 배열의 크기를 변경하는 resize 연산을 지원하기에 가능하다. 크기가 N인 꽉 찬 리스트에 새로운 항목을 추가하면 파이썬은 원래 항목 N개와 새로 추가한 항목까지 모두 담을 만한 크기의 새로운 리스트를 생성한다. 하지만 크기를 N + 1 할당하지 않고 나중을 위한 여유분으로 N보다 큰 M만큼 메모리를 할당한다. 그리고 이전 리스트의 데이터를 모두 새로운 리스트로 복사하고 이전 리스트는 삭제된다.

파이썬 3.7의 리스트 크기 할당 방정식은 아래와 같다

 M = (N >> 3) + (3 if N < 9 else 6)

N, 0, 1-4, 5-8, 9-16, 17-25, 26-35, 36-46, ... , 991-1120
M, 0,   4,   8,   16,    25,    35,    46, ... ,     1120

리스트에 데이터를 추가하면 여분의 공간을 하나 차지하며 리스트의 유효 크기 N이 증가한다. N은 M과 같아질 때까지 증가하며, M에 다다르면 새로운 데이터를 추가할 여유 공간이 없어서 더 큰 크기의 새로운 리스트를 생성한다.

항목이 10개인 리스트를 1백만개 저장하면 항목 1천막 개에 해당하는 메모리를 사용한다고 가정하기 쉽다. 하지만 실제로 append를 사용해 리스트를 만들면 항목 1천6백만 개에 해당하는 메모리를 사용한다.

튜플

리스트와 달리 튜플은 한번 생성되면 내용을 바꾸거나 크기를 변경할 수 없다. 크기를 변경할 순 없어도 두 튜플을 하나의 새로운 튜플로 합칠 수는 있다. 리스트의 resize 연산과 비슷하지만 리스트와 달리 여유 공간을 더 할당하지는 않는다.

t1 = (1, 2, 3, 4)
t2 = (5, 6, 7, 8)
t1 + t2
(1, 2, 3, 4, 5, 6, 7, 8)

리스트의 append에서는 이 과정이 O(1)만에 이루어지지만 튜플에서는 O(n)만큼 걸린다. 여유 공간이 부족할 때만 할당과 복사가 일어나는 리스트와 달리 튜플에서는 새로운 항목을 추가할 때마다 할당과 복사가 일어나기 때문이다.

튜플이 정적이기에 얻을 수 있는 장점은 파이썬이 내부적으로 수행하는 리소스 캐싱이다. 파이썬은 GC를 통해 더는 사용되지 않는 변수에 할당된 메모리를 반환한다. 하지만 크기가 20 이하인 튜플은 크기별로 최대 2만 개까지 즉시 회수하지 않고 나중을 위해 저장해둔다. 이는 같은 크기의 튜플이 나중에 다시 필요해지면 운영 체제에서 메모리를 새로 할당받지 않고 기존에 할당해둔 메모리를 재사용한다는 뜻이다.

마치며

리스트를 사용할 때는 크기 변경으로 발생한 초과 할당까지 고려해서 메모리에 데이터를 저장할 수 있을지 신경써야 한다. 반면 튜플은 빠르게 생성할 수있고 리스트보다 메모리 부담이 적은 대신에 내용을 변경할 수 없다.