Python 딕셔너리·세트, 특정 입력에서 이차 시간 성능 보임
Key Point
Python 개발자가 흔히 가정하는 '딕셔너리는 항상 빠르다'는 믿음이 특정 상황에서 깨질 수 있으며, 데이터 규모에 따른 메모리 성능 특성을 이해해야 한다.
핵심 요약
- Python의 dict와 set은 이론상 O(1) 상수 시간이지만, 특정 입력값에선 이차 시간 성능을 보인다.
- 명의적으로 선택한 해시 충돌 유발 값들로 n=16000일 때 약 1초가 걸리며, 크기 2배 증가마다 시간이 4배씩 늘어났다.
- 실전에선 메모리 캐시 미스로 인해 성능 저하가 발생한다: 백만 개 문자열 조회 시 dict는 크기 증가에 따라 22나노초에서 202나노초로 9배 느려진다.
- 해시테이블이 CPU 캐시에서 RAM으로, RAM에서 디스크로 옮겨가면서 메모리 접근 속도가 기하급수적으로 느려진다.
- Python의 해시테이블은 크기가 커질수록 필연적으로 느려지므로, O(1) 모델은 교육용 단순화일 뿐 실제 성능을 반영하지 않는다.