파이썬 딕셔너리와 세트의 시간 복잡도 오해와 실제 성능
Python sets and dictionaries can have quadratic-time performance
Hacker News파이썬의 `dict`와 `set`은 상수 시간($O(1)$)으로 작동한다고 알려져 있지만, 실제로는 데이터 크기 증가에 따라 성능 저하가 발생할 수 있습니다.
- 데이터 구조가 커지면서 메모리 재할당이나 충돌 문제 외에도 CPU 캐시를 벗어나는 하드웨어적 요인 때문에 성능이 선형 또는 2차 시간 복잡도로 떨어질 수 있습니다.
- 자료구조의 이론적인 시간 복잡도 모델에만 의존하기보다, 실제 데이터 크기와 메모리 사용 패턴을 고려하여 최적화된 자료구조를 선택하는 것이 중요합니다.
- 특히 키가 미리 알려진 경우, 일반 `dict` 대신 메모리 효율성이 높은 전용 라이브러리를 활용하면 캐시 적중률을 높여 성능을 크게 개선할 수 있습니다.
파이썬에서 `dict`나 `set` 같은 자료구조는 데이터 크기에 관계없이 삽입이나 조회 시간이 일정하다는 $O(1)$의 상수 시간 복잡도를 갖는 것으로 널리 알려져 있습니다. 하지만 이는 엄밀히 말해 공식적으로 참인 것은 아니며, 자료구조가 성장함에 따라 메모리 재할당이 필요하거나 충돌(collision) 문제가 발생할 수 있어 성능 저하를 겪을 수 있습니다.
실제 테스트 결과는 이러한 이론적 모델과 차이를 보입니다. 특정 패턴의 데이터를 사용할 경우 삽입 및 조회 시간이 선형 시간이나 상수 시간을 넘어 이차 시간 복잡도로 증가하는 것이 관찰되었습니다. 또한, 자료구조가 커지면서 CPU 캐시 영역을 벗어나 RAM이나 디스크에 저장될수록 메모리 접근 속도가 느려지는 하드웨어적 한계 때문에 $O(1)$이라는 모델 자체가 현실과 괴리가 생깁니다.
따라서 키가 미리 알려진 경우와 같이 특수한 상황에서는 일반 `dict` 대신 최적화된 라이브러리를 사용하는 것이 유리할 수 있습니다. 예를 들어, `fastconstmap` 같은 전용 맵은 메모리 효율성을 높여 캐시 적중률을 유지하는 데 도움을 주어, 표준 `dict`가 크기가 커지면서 발생하는 성능 저하(캐시 미스)를 개선하고 더 나은 성능을 보여줍니다.