자료구조 - 리스트와 튜플 (List, Tuple)

리스트와 튜플은 파이썬의 배열 자료구조로서 리스트는 아마 파이썬에서 가장 많이 사용되는 자료구조일 겁니다. 배열에서는 항목의 내용 자체만큼이나 항목이 배치된 순서가 굉장히 중요한데, 리스트는 저장하는 데이터나 배열 크기를 변경할 수 있는 동적 배열이고 튜플은 내용과 순서가 고정된 변경 불가능한 정적 배열입니다. 파이썬은 배열을 생성하기 위해 연속된 시스템 메모리 블록을 할당하고 각 메모리에는 실제 데이터를 가리키는 정수 타입 크기의 포인터가 담겨 모든 타입의 데이터를 저장할 수 있습니다. (이는 numpy array 와 다른 점인데, numpy 배열은 정적으로 타입이 정해져있어 다른 타입의 값을 저장할 수 없습니다) 따라서 연속적인 메모리에 정렬되어 저장된 데이터는 배열의 크기와 상관없이 배열이 시작되는 메모리 위치를 안다면 시간복잡도 $O(1)$ 으로 읽을 수 있습니다.

a = tuple(range(10))
b = tuple(range(100000))

>>> timeit a[5]
10000000 loops, best of 5: 46.6 ns per loop

>>> timeit b[1000]
10000000 loops, best of 5: 44.8 ns per loop

 

언제 어떻게 리스트나 튜플을 사용할까?

리스트와 튜플의 차이점은 다음과 같고, 튜플은 그 불변성 덕분에 자료구조가 아주 가볍고 메모리 오버헤드가 크지 않습니다. 반면, 리스트는 변경할 수 있다는 점 때문에 메모리를 더 많이 사용하며, 추가 연산도 필요합니다. 

• 리스트는 동적인 배열로 수정이 가능하며, 저장 용량을 늘리거나 줄일 수 있고,
• 튜플은 정적인 배열로 일단 생성되면 배열의 크기뿐 아니라 데이터도 변경할 수 없습니다. 대신, 파이썬 런타임에서 캐시하므로 사용할 때마다 운영체제 (커널)에 메모리를 요청하지 않아도 됩니다

따라서 다음과 경우에는 어떤 자료구조를 사용하는 것이 좋을까요?

1. 처음 20번째까지 소수 (prime number)
  - 변하지 않으므로 튜플
2. 프로그래밍 언어의 이름
  - 데이터가 계속 증가할 수 있으므로 리스트
3. 사람의 나이, 몸무게, 티
  - 데이터가 갱신되므로 리스트
4. 특정 야구 경기의 결과
  - 불변이므로 튜플
5. 잇단 야구 경기의 결과
  - 개별 경기의 결과는 변하지 않고 경기를 계속할 수록 데이터를 추가해야하니 튜플로 이루어진 리스트

 

리스트의 크기 변경

잘 알려진대로 파이썬의 리스트는 append/pop 등의 연산자로 내용을 추가하거나 삭제할 수 있습니다. 특히, 리스트는 동적 배열로 resize 연산을 지원하기에 크기가 $N$인 꽉 찬 리스트에 새로운 항목을 append로 추가하면 파이썬은 원래 항목 $N$개와 새로 추가한 항목까지 담은 만한 크기의 새로운 리스트를 생성합니다. 하지만 크기를 $N+1$로 할당하지 않고 나중을 위한 여유분으로 $N$보다 큰 $M$만큼 메모리를 할당합니다. 그리고 이전 리스트의 데이터를 모두 새로운 리스트로 복사하고 이전 리스트는 삭제합니다.

크기에 여유를 두는 이유는 리스트에 값을 추가하면 그 뒤로도 여러 번 더 추가할 확률이 높으니 비용이 많이 드는 메모리 할당과 복사 요청 횟수를 줄이기 위함입니다. 실제로 파이썬 3.7의 리스트 크기 할당 방정식은 다음과 같은데, $N$은 $M$과 같아질 때까지 증가하며, $M$에 다다르면 새로운 데이터를 추가할 여유 공간이 없어서 더 큰 크기의 새로운 리스트를 생성합니다. 물론, 이런 초과 할당은 꽉 찬 리스트에 항목을 처음 append 할 때 일어나며, 리스트를 직접 생성하면 필요한 크기만큼 할당됩니다.

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

추가로 할당되는 공간은 크지 않지만 개수가 많아지면 전체 개수가 더 커질 수 있습니다. 예를 들어 항목 십만  개를 한 번에 리스트로 생성할 때와 append로 십만 개를 추가할 때를 비교해보면, append를 사용할 떄가 요구되는 메모리 량이 더 높고 메모리 재할당 및 복사로 인해 실행 시간도 더 느려지게 됩니다. 예를 들어 항목이 10개인 리스트를 백만 개 저장하면 항목 천만 개에 해당하는 메모리를 사용한다고 가정하기 쉽지만, 이를 append를 사용해 구성한다면 항목 천육만 개에 해당하는 메모리를 할당하게 됩니다.

 

튜플에서는 ?

튜플은 리스트와 달리 크기를 변경할 수는 없지만 두 튜플을 새로운 하나의 튜플로 합칠 수는 있습니다. 단, 여유 공간이 부족할 때만 할당과 복사가 일어나는 리스트와 달리 튜플에서는 새로운 항목을 추가할 때마다 할당과 복사가 일어나므로 $O(n)$만큼 걸립니다. (리스트는 $O(1)$) 따라서 리스트와 달리 여유 공간을 할당하지 않고 자원을 더 적게 사용하는 장점이 있죠. 심지어 같은 데이터를 저장한다 하더라도 리스트는 크기 변경의 효율화를 위해 상태 정보를 관리하기 때문에 같은 크기의 리스트보다 메모리가 덜 사용됩니다.

또한, 정적 배열임으로부터 얻을 수 있는 장점은 파이썬이 내부적으로 수행하는 리소스 캐싱도 있습니다. 파이썬은 garbage collection 을 통해 더는 사용되지 않는 변수에 할당된 메모리를 반환하지만 크기가 20 이하인 튜플은 크기별로 최대 2만 개까지 즉시 회수하지 않고 나중을 위해 저장해둡니다. 이는 같은 크기의 튜플이 나중에 다시 필요해지면 운영체제로부터 메모리를 새로 할당받지 않고 기존에 할당해둔 메모리를 재사용한다는 뜻으로 운영체제를 거치지 않으므로 튜플을 쉽고 빠르게 생성할 수 있습니다. 밑의 예처럼 리스트가 튜플보다 인스턴스 생성이 5배 정도 더 느리다는 사실을 알 수 있습니다.

>>> timeit l = [0,1,2,3,4,5,6,7,8,9]
10000000 loops, best of 5: 110 ns per loop

>>> timeit l = (0,1,2,3,4,5,6,7,8,9)
10000000 loops, best of 5: 22.1 ns per loop