CHAPTER
2
리스트와 딕셔너리
많은 프로그램이 사람보다 기계가 하기에 더 적합한 반복적인 작업을 자동화하고자 만들어졌다. 파이썬에서 이런 작업을 조직적으로 관리하는 가장 일반적인 방법은 리스트(타입 이름은 list) 타입을 쓰는 것이다. 리스트는 아주 간편하며 다양한 문제를 해결하는 데 사용할 수 있다.
리스트를 자연스럽게 보완할 수 있는 타입이 딕셔너리(타입 이름은 dict) 타입이다. 딕셔너리 타입은 검색에 사용할 키와 키에 연관된 값을 저장한다(일반적으로 해시 테이블(hash table)이나 연관 배열(associative array)이라고 부르는 데이터 구조 안에 값을 저장한다). 딕셔너리는 (분할상환 복잡도1로) 상수 시간에 원소를 삽입하고 찾을 수 있다. 따라서 동적인 정보를 관리하는 데는 딕셔너리가 가장 이상적이다.
파이썬은 리스트와 딕셔너리를 다룰 때 가독성을 좋게 하고 기능을 확장해주는 특별한 구문과 내장 모듈을 제공한다. 이로 인해 다른 언어가 제공하는 단순 배열, 벡터2, 해시 테이블 타입보다 훨씬 더 편리하게 딕셔너리와 해시 테이블을 쓸 수 있다.
1 역주 분할상환(armotization) 방식으로 계산한 복잡도는 각 연산이 발생하는 빈도와 시간을 함께 고려해 평균적으로 비용을 계산함으로써 산정한 복잡도를 말한다. 예를 들어, 해시 테이블의 경우 데이터 삽입은 중간중간 테이블을 재배치하기 위한 시간이 오래 걸릴 수 있다. 하지만 일반적으로 원소 읽기 연산이 원소 삽입보다 훨씬 더 많이 쓰이기 때문에 평균적으로는 원소 삽입 시 가끔 일어나는 재배치에 걸리는 시간을 읽기 연산에서 얻는 이득이 상쇄한다. 따라서 O(1)의 읽기 및 쓰기 시간이 걸린다고 볼 수 있다. 물론 계속 새로운 원소를 추가만 하고 검색을 하지 않는다면 분할상환 복잡도를 계산할 때 연산 빈도에 대해 가정한 내용이 깨지기 때문에 딕셔너리가 그리 효율적이지 못할 수 있다.
2 역주 필요에 따라 동적으로 크기를 늘리거나 줄일 수 있는 배열을 벡터(vector)라고 부른다. 일반적으로 연속된 배열을 쓰면서 동적으로 메모리를 할당/해제하는 방식으로 구현하거나 가지 수가 아주 많은(이를 가지뻗기 계수(branching factor)라고 부르며, 스칼라 벡터의 경우 매 노드마다 자식이 32개 있다) 트리를 사용해 벡터를 구현한다. 트리를 사용하는 경우 자식이 아주 많기 때문에 4~5단계만 내려가도 처리할 수 있는 원소 수가 기하급수적으로 증가하며, 이로 인해 실제 사용할 때는 거의 언제나 상수 시간에 가까운 복잡도를 얻을 수 있다.