고성능 파이썬(2판)

111

4

장

사전과 셋

이 장에서 배울 내용

• 사전과 셋의 용도

• 사전과 셋의 유사점

• 사전의 오버헤드

• 사전의 성능을 최적화하는 방법

• 파이썬에서 사전을 사용해서 네임스페이스를 유지하는 방법

셋

set

과 사전은 (삽입 순서를 제외하면 ) 미리 정해진 순서로 정렬되지 않으나, 특정 데이터를

고유하게 참조할 수 있는 별도 객체가 있는 상황에 이상적인 자료구조다. 참조하는 객체는 일

반적으로 문자열이지만, 해시가 가능하다면

hashable

어떤 타입이라도 상관없다. 이때 참조 객체

를 ‘

키

’, 데이터를 ‘

값

’이라고 한다. 사전과 셋은 거의 같지만 셋에는 값이 없다는 점이 다르다.

쉽게 말해 셋은 유일한 키를 저장하는 자료구조다. 이름에서 알 수 있듯이 셋은 집합 연산을 수

행할 때 아주 유용하다.

NOTE

_ 해시가 가능한 타입은

__

hash

__

매직 함수, 그리고

__

eq

__

혹은

__

cmp

__

매직 함수를 구현한

타입이다. 파이썬의 내장 타입은 모두 이를 구현하며 사용자 클래스는 모두 기본값이 있다. 자세한 내용은

4

.

1

.

4

‘해시 함수와 엔트로피’를 참고하자.

사전과 셋

CHAPTER

4

112

고성능 파이썬(2판)

3

장에서 정렬되지 않은 리스트와 튜플은 최적의 경우

O

(

log

n

)

시간복잡도로 값을 찾을 수 있

음을 알아보았다. 반면 사전과 셋은 주어진 색인을

O