고성능 파이썬(2판)

115

4

장

사전과 셋

항목

1

만 개 중 유일한 이름이

7

,

412

개인

phonebook

을 각각의 알고리즘을 사용해 돌려보면

O

(

n

)

과

O

(

n

2

)

의 차이가 얼마나 큰지 확인할 수 있다.

>>>

%timeit list_unique_names(large_phonebook)

1.13 s ± 26.8 ms per loop (mean ± std. dev. of 7 runs, 1 loop each)

>>>

%timeit set_unique_names(large_phonebook)

4.48 ms ± 177 µs per loop (mean ± std. dev. of 7 runs, 100 loops each)

보다시피 셋을 이용한 알고리즘이

252

배나 빠르다!

phonebook

의 크기가 커질수록 이 차이는

더 벌어진다 (전화번호

10

만 개에 유일한 이름이

15

,

574

개일 때는

557

배 차이였다 ).

4.1

사전과 셋의 동작 원리

사전과 셋은 모두

해시 테이블

을 사용해서 시간복잡도가

O

(

1

)

이다. 이는 임의의 키 (문자열이나

객체 )를 리스트의 색인으로 변환하는 해시 함수를 효율적으로 사용한 결과다. 이 해시 함수와

리스트는 나중에 검색을 하지 않고도 특정 데이터가 제대로 들어있는지 확인하는 용도로 사용

한다. 데이터의 키를 리스트의 색인처럼 사용하도록 변환하는 작업을 하면 리스트와 ...