고성능 파이썬(5)

CHAPTER 4. 사전과 셋

 

4.1.3 크기 변경

해시 테이블에 항목이 추가됨에 따라 해시 테이블의 크기도 그에 맞춰 변경되어야 한다. 테이블의 2/3 이하만 채워진다면 충돌 횟수와 공간 활용 측면 모두 적절하다고 볼 수 있다. 따라서 해시 테이블이 임계 크기에 다다를 때까지 계속 사용하면 된다. 해시 테이블은 데이터가 삽입 될 때에만 크기 변경이 일어난다.

 

4.1.4 해시 함수와 엔트로피

파이썬의 객체는 이미 __hash__ 와 __cmp__ 함수를 구현하고 있으므로 일반적으로 해시가 가능하다.

튜플과 문자열은 그 내용을 기반으로 해시값을 구한다. 반면 리스트는 그 값이 변경될 수 있으므로 해시를 지원하지 않는다.

 

사용자 정의 클래스도 기본으로 해시 함수와 비교 함수를 가지고 있다. 기본 __hash__ 함수는 단순히 내장 함수인 id 함수를 이용해서 그 객체의 메모리 위치를 반환한다. __cmp__ 연산자는 그 객체의 메모리 위치를 산술 비교한다.

하지만, 경우에 따라서는 셋이나 사전 객체가 원소 간의 id 차이를 인식하지 않았으면 하는 경우도 있다. 다음 클래스 정의를 보라.

 

class Point(Object):
  def __init__(self, x, y):
    self.x, self.y = x, y

 

만약 x, y 값이 동일한 Point 객체를 여러 개 생성하면 메모리 주소는 전부 독립적이므로 모두 다른 해시값을 가지게 된다. 이 객체들을 모두 하나의 셋에 추가한다면 각각의 항목이 모두 추가된다.

 

>>> p1 = Point(1,1)
>>> p2 = Point(1,1)
>>> set([p1, p2])
set([<_main_.Point at 0x...fc90>, <_main_.Point at 0x...fbd0>])
>>> Point(1,1) in set([p1, p2])
False

이 문제는 객체의 메모리 주소가 아니라 실제 내용을 기반으로 하는 사용자 정의 해시 함수를 작성해서 해결 할 수 있다.

class Point(object):
  def __init__(self, x, y):
    self.x, self.y = x, y
  
  def __hash__(self):
    return hash((self.x, self.y))
  
  def __eq__(self, other):
    return self.x == other.x and self.y == other.y

 

유한한 모든 사전에서 사용할 수 있는 완벽한 해시 함수는 없다. 하지만 저장할 값의 범위와 사전의 크기가 어느 정도인지 미리 알 수 있다면 좋은 선택을 하는 데 도움이 된다. 예를 들어 사전의 키로 두 소문자의 모든 조합('aa', 'ab', 'ac' 등 총 676개)을 사용한다면 바로 위의 코드에 나타난 해시 함수가 괜찮은 선택이 될 것이다.

 

4.2 사전과 네임스페이스

파이썬에서 변수, 함수, 또는 모듈이 사용될 때 그 객체를 어디서 찾을지 결정하는 계층이 있다. 가장 먼저 모든 지역 변수를 담고 있는 locals() 배열을 찾는다. 파이썬은 지역 변수 탐색을 빨리 끝낼 수 있도록 최선을 다하며, 이 과정은 사전 탐색을 하지 않는 유일한 부분이다. 만약 여기서 그 이름에 해당하는 객체를 찾을 수 없으면 globals() 사전에서 찾는다. globals()에서도 찾을 수 없다면 마지막으로 __builtin__ 객체에서 찾는다. 여기서 중요한 것은 locals()와 globals()는 명백한 사전이지만, __builtin__은 기술적으로는 모듈 객체다. __builtin__에서 그 모듈 내부의 locals() 사전(여기에 모듈 객체와 클래스 객체가 저장된다)을 탐색하여 특정 속성을 찾게된다.

 

루프 안에서 전역 변수를 참조하는 경우라면, 지역변수로 할당하는 것도 성능향상에 도움이 된다.