고성능 파이썬 Chapter 03 - 리스트와 튜플

들어가며

앞으로 3,4,5 Chapter에서는 리스트, 튜플, 딕셔너리, 셋, 이터레이터, 제너레이터등 CS과목의 기조가 되는 자료구조에 대한 이야기를 다룬다. 각 상황에 맞는 적절한 자료구조를 사용하는 것이 최적화의 기본이기 때문에 파이썬에서 제공해주는 기본 자료형들에 대한 특성을 알아보는 뜻깊은 시간이 되길 바란다.

---

이 장에서 배울 내용

- 리스트와 튜플의 용도

- 리스트/튜플 탐색의 복잡도

- 리스트와 튜플의 차이점

- 리스트에 항목을 추가하는 과정

- 리스트와 튜플의 적용 시점

---

리스트와 튜플은 배열의 일종이다. 각 항목의 순서가 항목 자체만큼 중요한 자료구조이다.

리스트는 배열의 크기를 변경할 수 있는 동적 배열, 튜플은 내용이 고정된(변경 불가능한) 정적 배열이다.

배열은 메모리 상에서 연속적으로 할당 받기 때문에 시작 주소와 index(순서 정보)를 알고 있으면 O(1)만에 원하는 값을 탐색할 수 있다.

 

배열에서 값을 찾는 방법은 여러 방식이 있다.

 

1. 선형 탐색 

linear search

가장 기본적인 탐색 방법인 순차 탐색은 모든 항목을 순차적으로 탐색하기 때문에 O(n)의 시작 복잡도를 가진다. list.index()에서 해당 알고리즘을 사용한다고 한다.

 

2. 이분 탐색

binary search

이분 탐색은 배열의 항목이 정렬되어 있을때 가장 효율적으로 원하는 값을 찾는 방법이다. 배열의 길이의 중간 위치의 값과 탐색하려는 값을 비교하여 배열을 절반 크기의 배열로 만들면서 탐색하는 방법으로 O(log n)의 시간 복잡도는을 가진다.

 

3. bisect 모듈을 이용한 가장 가까운 값 찾기

bisect 를 이용한 탐색

bisect 모듈은 정렬된 리스트를 관리하는 파이썬 표준 라이브러리다. 값을 추가하더라도 리스트는 정렬된 형태를 가진다.

bisect.bisect_left(haystack, needle)라는 함수는 정렬된 haystack 리스트에서 적절한 위치에 needle을 삽입할 index를 반환한다고 한다. 즉 needle보다 크거나 같은 첫번째 값의 위치를 반환한다.

 

이러한 알고리즘을 사용하려면 리스트를 정렬해야 하는데, 파이썬에서는 Tim sort 알고리즘을 이용하여 정렬을 한다고 한다. 이 블로그에서 잘 설명하고 있다. 간단히 말하면 insertion sort와 merge sort를 적절히 사용하는 하이브리드 정렬 알고리즘이고 최적일때 O(n), 최악일 경우 O(n log n)의 시간복잡도를 가진다.

 

리스트: 동적 배열

리스트는 동적으로 크기를 조절한다. 리스트를 만들기 위해서 os를 통해 memory allocation을 해야 하는데, 이게 시간이 오래 걸리기 때문에 (나중에 추가될 것을 대비해서) 실제 사용하는 리스트의 크기보다 더 크게 할당을 한다. (메모리 오버헤드 발생)

M = (N>>>3) + (3 if N < 9 else 6 ) 의 수식을 사용해서 N개의 값이 리스트에 있을때 M 크기의 리스트 크기로 생성한다고 한다.

또한 메모리에서 연속적인 위치에 값들을 넣어두기 위하여 linked list와 같이 추가되는 부분만을 할당하는 것이 아니라, 전체 크기의 메모리를 새롭게 할당 받아서 기존 리스트의 값을 복사하는 형태로 동작한다.

 

튜플: 정적 배열

튜플은 한번 생성되면 그 내용을 변경할 수 없다. 값의 크기가 작은 튜플은 재사용 될 확률이 높아 런타임에서 캐싱되어 저장된다. 나중에 다시 필요해지면 운영체제에서 메모리를 새로 할당받지 않고 기존에 캐싱된 메모리를 재사용하여 빠르게 사용가능하다.

 

 

 

리스트와 튜플은 정렬된 데이터에 적합한 빠르고 오버헤드가 적은 자료구조이다. 

원하는 값의 index를 알면 O(1)의 속도로 원하는 값에 도달할 수 있다.

---