고성능 파이썬(4)

시간복잡도 정렬되지 않은 리스트, 튜플 최적화 모델 : 0(log n) 사전, 셋 : 0(1) - 해시 테이블 사전과 셋은 메모리를 많이 사용하기 때문에 실제 속도는 해시 함수에 전적으로 의존하여, 만일 해시 함수가 느리다면 사전과 셋의 모든 연산도 마찬가지로 느릴것이다. 리스트 vs 셋 유일한 이름찾기 항목 1만 개 중 유일한 이름이 7412 개인 phonebook 리스트를 사용하면 셋과 리스트의 차이가 252배정도 차이가 난다. 사전과 셋의 동작원리 해시 테이블을 처음 생성하면 배열을 사용할때처럼 메모리부터 할당한다. 배열은 데이터를 추가하려면 사용하지 않은 메모리 블록을 찾아 데이터를 추가하고, 필요할때 크기를 조정한다 그러나 해시 테이블에서는 먼저 이 연속적인 메모리에 데이터를 나열할 방법을 생각..