[Python] 어떻게 dict 키 rehashing 피하기 위해?


Answers

Question

아래의 스크립트는 setfrozenset 의 기능을 설명하고 있습니다. 가능한 경우 collections.MutableSet의 하위 클래스에서 복제하십시오. (BTW,이 기능은 setfrozenset 의 단지 괴상한 것이 아닙니다.이 유형에 대한 Python의 단위 테스트에서 활발히 검증됩니다.)

이 스크립트는 set-like 오브젝트의 여러 유형 / 클래스 각각에 대해 다음 단계를 수행합니다.

  1. n 키가 __hash__ 메쏘드가 호출 된 횟수를 추적하는 특별히 계측 된 정수인 dict d 를 만든다. ( d 값은 모두 None 이지만 이것은 부적절하다.);
  2. d 의 키의 __hash__ 메소드가 지금까지 호출 된 누적 횟수 (즉, d 생성하는 동안)를 계산하고 (나중에 저장하십시오.);
  3. 생성자에 대한 인수로 d 를 사용하여 현재 집합과 같은 유형 / 클래스의 객체 s 를 만듭니다 (따라서 d 의 키는 결과 객체의 내용이되지만 d 값은 무시됩니다).
  4. (2)에서 설명한 계산을 다시 실행하십시오.
  5. 위의 (2)와 (4)의 계산 결과를 출력하십시오.

다음은 모든 유형 / 클래스에 대해 n 을 10으로 설정 한 경우의 출력입니다 (이 게시물의 끝 부분에서 전체 코드를 제공합니다).

set: 10 10
frozenset: 10 10
Set: 10 20
myset: 10 20

결론은 분명합니다. d 에서 set 또는 frozenset__hash__ 하는 것은 d 키의 __hash__ 메소드를 호출 할 필요가 없으므로 호출자 수는이 생성자가 반환 된 후에도 변경되지 않습니다. 그러나 Set 또는 myset 인스턴스가 d 에서 만들어지는 경우에는 해당되지 않습니다. 이 각각의 경우에 d 의 각 키 ' __hash__ 가 한 번 호출됩니다.

어떻게 d '를 인수로 사용하여 생성자를 실행하면 d 키의 해시 메소드를 호출하지 않도록 myset (아래 참조)를 수정할 수 있습니까?

감사!

from sets import Set
from collections import MutableSet

class hash_counting_int(int):
    def __init__(self, *args):
        self.count = 0
    def __hash__(self):
        self.count += 1
        return int.__hash__(self)

class myset(MutableSet):
    def __init__(self, iterable=()):
        # The values of self.dictset matter!  See further notes below.
        self.dictset = dict((item, i) for i, item in enumerate(iterable))

    def __bomb(s, *a, **k): raise NotImplementedError
    add = discard = __contains__ = __iter__ = __len__ = __bomb

def test_do_not_rehash_dict_keys(thetype, n=1):
    d = dict.fromkeys(hash_counting_int(k) for k in xrange(n))
    before = sum(elem.count for elem in d)
    s = thetype(d)
    after = sum(elem.count for elem in d)
    return before, after

for t in set, frozenset, Set, myset:
    before, after = test_do_not_rehash_dict_keys(t, 10)
    print '%s: %d %d' % (t.__name__, before, after)

self.dictset 의 값은 정수이며, (무시 된) iterable.values()self.dictset않습니다 ( iterable.values 실제로있는 경우). 이는 iterable 이 dict (해당 될 필요는 없음)이고 해당 values 이 무시되는 경우 self.dictset 예제가 self.dictset 한 실제 코드에서 self.dictset 항상 중요합니다. 즉, self.dictset.update(iterable) 을 사용하는 모든 솔루션은 적절한 값을 키에 할당하는 문제를 해결해야하며 다시 한번 __hash__ 메서드를 호출하지 않고 이러한 키를 반복하는 문제에 직면합니다. (또한 self.dictset.update(iterable) 기반의 솔루션은 iterableself.dictset.update 적합한 인수가 아닌 경우이 문제를 극복 할 수없는 문제를 해결해야합니다.

편집 : 1) myset.dictset의 값의 중요성을 명확히했습니다. 2) myset.__bomb__myset.__bomb 개명 myset.__bomb__ .




Links