Python의 set과 dict는 이차 시간 성능을 보일 수 있다
Python sets and dictionaries can have quadratic-time performance
Python의 set과 dict는 해시 테이블로, 흔히 O(1) 상수 시간이라고 알려져 있다. 하지만 Daniel Lemire는 해시 충돌을 유도하는 입력을 통해 삽입과 조회가 이차 시간으로 느려지는 현상을 실측했다. 또한 백만 개의 문자열 키를 조회할 때 dict는 키당 22ns에서 202ns로 느려지지만, fastconstmap은 4ns에서 12ns로 증가에 그쳤다. 이는 해시 테이블의 O(1) 모델이 현실과 다를 수 있음을 보여준다.
해시 테이블이 O(1) 또는 상수 시간이라고 말하는 것은 하나의 모델이다. 그것은 사실일 수 있고, 어쩌면 자주 그럴 수도 있지만, 현실은 아니다.
HN 토론
22- northisup
Raymond Hettinger가 파이썬의 dict가 수년간 얼마나 개선되었는지에 대해 훌륭한 강연을 했습니다. 그래서 이건 정말 흥미롭고 아마 결국 builtin dict를 더 나아지게 만들 겁니다.
그 강연의 교훈은, 관용적으로 코드를 작성하면 언어가 발전함에 따라 혜택을 받는다는 것입니다.
- juancn
그건 보통 모든 일반적인 해시 테이블 구현에 해당하는 얘기입니다(객체에 정의된 순서가 없을 때 그렇고, 순서가 있으면 평균 O(1), 최악 O(log N)을 얻을 수 있습니다). 언어와 무관하게요.
O(1)은 기대 평균 케이스이고, 보통 그게 성립합니다.
네, O(N^2)이 이론적으로는 가능하지만, 일종의 서비스 거부 공격을 방어하는 상황이 아니라면 실제로는 거의 문제가 되지 않습니다.
그래도 해시 테이블에 적절한 초기 크기를 추측할 수 있다면 리해싱 오버헤드의 상당 부분을 피할 수 있습니다.
- aadyachinubhai
그래서 저는 클래스를 정의할 때 __slots__를 사용하는 걸 좋아합니다. dict와 달리 __slots__를 사용하면 튜플이라서 클래스 속성을 저장하는 데 훨씬 빠릅니다.