Python 해시 가능한 명령어

Python 해시 가능한 명령어

운동으로, 그리고 주로 나만의 즐거움을 위해, 나는 백트랙킹 팩 쥐 파서를 실행하고 있습니다.이것에 대한 영감은 (일반적으로 발견되는 구문 프리 리스프 방언과 비교할 때) 위생 매크로가 알골과 같은 언어에서 어떻게 작동하는지에 대한 더 나은 아이디어를 얻고 싶습니다.이 때문에 입력을 통과하는 패스가 서로 다른 문법을 볼 수 있으므로 현재 버전의 문법을 캐시된 구문 분석 결과와 함께 저장하지 않는 한 캐시된 구문 분석 결과는 유효하지 않습니다. (EDIT: 키 값 컬렉션을 사용한 결과는 키 값이 불변해야 한다는 것이지만 인터페이스를 에 노출할 의도는 없습니다.변경할 수 있도록 허용하므로 변경 가능한 컬렉션이나 불변 컬렉션 중 하나라도 좋습니다.)

문제는 python dicts가 다른 dicts의 키로 나타날 수 없다는 것입니다.튜플을 사용하는 것조차 도움이 되지 않습니다.

>>> cache = {}
>>> rule = {"foo":"bar"}
>>> cache[(rule, "baz")] = "quux"
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
TypeError: unhashable type: 'dict'
>>> 

끝까지 튜플이 있어야 할 것 같습니다.파이썬 표준 라이브러리가 제게 필요한 것들을 대략 제공하고 있습니다.collections.namedtuple는 매우 다른 구문을 가지고 있지만 키로 사용할 수 있습니다. 위의 세션부터 계속해서:

>>> from collections import namedtuple
>>> Rule = namedtuple("Rule",rule.keys())
>>> cache[(Rule(**rule), "baz")] = "quux"
>>> cache
{(Rule(foo='bar'), 'baz'): 'quux'}

좋아요. 하지만 저는 사용할 규칙의 가능한 키 조합에 대해 클래스를 만들어야 하는데, 나쁘지 않습니다. 왜냐하면 각 구문 분석 규칙은 자신이 사용하는 파라미터를 정확하게 알고 있기 때문에 클래스는 규칙을 구문 분석하는 함수와 동시에 정의될 수 있기 때문입니다.

편집: 에 대한 추가적인namedtuple그들이 엄밀한 위치에 있기 때문입니다.서로 달라야 할 것처럼 보이는 두 개의 튜플은 사실 동일할 수 있습니다.

>>> you = namedtuple("foo",["bar","baz"])
>>> me = namedtuple("foo",["bar","quux"])
>>> you(bar=1,baz=2) == me(bar=1,quux=2)
True
>>> bob = namedtuple("foo",["baz","bar"])
>>> you(bar=1,baz=2) == bob(bar=1,baz=2)
False

TL'dr: 어떻게 해야 하나요?dict다른 사람들의 열쇠로 사용될 수 있는 sdicts?

답을 조금 해킹한 후, 제가 사용하고 있는 더 완벽한 솔루션은 다음과 같습니다.이것은 실용적인 목적을 위해 결과적인 명령어를 모호하게 불변하게 만드는 데 약간의 추가적인 작업을 수행한다는 점에 유의하십시오.물론 전화를 걸어 해킹하는 것은 꽤 쉬운 일입니다.dict.__setitem__(instance, key, value)하지만 우리는 여기서 모두 어른입니다.

class hashdict(dict):
    """
    hashable dict implementation, suitable for use as a key into
    other dicts.

        >>> h1 = hashdict({"apples": 1, "bananas":2})
        >>> h2 = hashdict({"bananas": 3, "mangoes": 5})
        >>> h1+h2
        hashdict(apples=1, bananas=3, mangoes=5)
        >>> d1 = {}
        >>> d1[h1] = "salad"
        >>> d1[h1]
        'salad'
        >>> d1[h2]
        Traceback (most recent call last):
        ...
        KeyError: hashdict(bananas=3, mangoes=5)

    based on answers from
       http://stackoverflow.com/questions/1151658/python-hashable-dicts

    """
    def __key(self):
        return tuple(sorted(self.items()))
    def __repr__(self):
        return "{0}({1})".format(self.__class__.__name__,
            ", ".join("{0}={1}".format(
                    str(i[0]),repr(i[1])) for i in self.__key()))

    def __hash__(self):
        return hash(self.__key())
    def __setitem__(self, key, value):
        raise TypeError("{0} does not support item assignment"
                         .format(self.__class__.__name__))
    def __delitem__(self, key):
        raise TypeError("{0} does not support item assignment"
                         .format(self.__class__.__name__))
    def clear(self):
        raise TypeError("{0} does not support item assignment"
                         .format(self.__class__.__name__))
    def pop(self, *args, **kwargs):
        raise TypeError("{0} does not support item assignment"
                         .format(self.__class__.__name__))
    def popitem(self, *args, **kwargs):
        raise TypeError("{0} does not support item assignment"
                         .format(self.__class__.__name__))
    def setdefault(self, *args, **kwargs):
        raise TypeError("{0} does not support item assignment"
                         .format(self.__class__.__name__))
    def update(self, *args, **kwargs):
        raise TypeError("{0} does not support item assignment"
                         .format(self.__class__.__name__))
    # update is not ok because it mutates the object
    # __add__ is ok because it creates a new object
    # while the new object is under construction, it's ok to mutate it
    def __add__(self, right):
        result = hashdict(self)
        dict.update(result, right)
        return result

if __name__ == "__main__":
    import doctest
    doctest.testmod()

해시 가능한 사전을 만드는 쉬운 방법이 여기 있습니다.명백한 이유로 다른 사전에 포함시킨 후에는 그들을 변형시키지 말아야 한다는 것만 기억하세요.

class hashabledict(dict):
    def __hash__(self):
        return hash(tuple(sorted(self.items())))

해시는 불변해야 합니다. 이것을 강제하는 것이 아니라 키로 처음 사용된 후에 명령어가 변형되지 않도록 신뢰하는 것입니다. 다음과 같은 접근 방식이 효과적입니다.

class hashabledict(dict):
  def __key(self):
    return tuple((k,self[k]) for k in sorted(self))
  def __hash__(self):
    return hash(self.__key())
  def __eq__(self, other):
    return self.__key() == other.__key()

만약 독자 분이 독자 분의 명령을 변형시켜야 하고도 그것들을 열쇠로 사용하고 싶다면, 복잡성은 백 배로 폭발할 것입니다. 불가능하다는 것은 말할 것도 없지만, 저는 그 엄청난 혼란에 빠지기 전에 아주 구체적인 징후가 나타날 때까지 기다릴 것입니다.

사용자의 목적에 맞게 사전을 사용할 수 있도록 하는 데 필요한 것은 __hash__ 메서드를 추가하는 것입니다.

class Hashabledict(dict):
    def __hash__(self):
        return hash(frozenset(self))

참고로 동결 집합 변환은 모든 사전에 대해 작동합니다(즉, 키를 정렬할 필요가 없습니다).마찬가지로 사전 값에 대한 제한은 없습니다.

키는 같지만 값은 다른 사전이 많은 경우 해시에 값을 반영해야 합니다.가장 빠른 방법은 다음과 같습니다.

class Hashabledict(dict):
    def __hash__(self):
        return hash((frozenset(self), frozenset(self.itervalues())))

이것은 보다 빠릅니다.frozenset(self.iteritems())두 가지 이유 때문에.일단은.frozenset(self)단계는 사전에 저장된 해시 값을 재사용하여 불필요한 호출을 저장합니다.hash(key). 둘째, 인터벌 값을 사용하면 값에 직접 액세스할 수 있고 검색할 때마다 메모리에서 새로운 많은 키/값 튜플을 형성하기 위해 항목별로 사용하는 많은 메모리 할당자 호출을 피할 수 있습니다.

제시된 답변은 괜찮지만, 를 사용하면 개선될 수 있습니다.frozenset(...)대신에tuple(sorted(...))해시를 생성하는 방법:

>>> import timeit
>>> timeit.timeit('hash(tuple(sorted(d.iteritems())))', "d = dict(a=3, b='4', c=2345, asdfsdkjfew=0.23424, x='sadfsadfadfsaf')")
4.7758948802947998
>>> timeit.timeit('hash(frozenset(d.iteritems()))', "d = dict(a=3, b='4', c=2345, asdfsdkjfew=0.23424, x='sadfsadfadfsaf')")
1.8153600692749023

성능의 이점은 사전의 내용에 따라 다르지만, 대부분의 경우 테스트를 통해 해싱 작업을 수행했습니다.frozenset최소 2배 이상 빠릅니다(소트할 필요가 없으므로 mainly).

합리적으로 깨끗하고 간단한 구현은

import collections

class FrozenDict(collections.Mapping):
    """Don't forget the docstrings!!"""

    def __init__(self, *args, **kwargs):
        self._d = dict(*args, **kwargs)

    def __iter__(self):
        return iter(self._d)

    def __len__(self):
        return len(self._d)

    def __getitem__(self, key):
        return self._d[key]

    def __hash__(self):
        return hash(tuple(sorted(self._d.iteritems())))

이 주제로 계속 돌아오게 되네요...여기 또 다른 변형이 있습니다.서브클래싱이 불편합니다.dict가 추가되다__hash__방법;명령어가 변형될 수 있다는 문제에서 사실상 벗어날 수 없고, 그들이 변하지 않을 것이라고 믿는 것은 약한 생각처럼 보입니다.그래서 저는 그 자체로 불변인 내장형을 기반으로 맵을 구축하는 것을 검토했습니다.비록 ~일지라도tuple그 안에서 가치에 접근하는 것은 일종의 종류와 이분법을 의미하며, 문제는 아니지만, 그것이 구축된 유형의 힘을 크게 활용하지 않는 것 같습니다.

만약 당신이 키를 잠근다면, 값 쌍들을 a로 만들 수 있습니다.frozenset? 그게 뭐가 필요하겠습니까, 어떻게 작동하겠습니까?

1부, '아이템'을 냉동 세트가 주로 키를 사용하여 처리하도록 인코딩하는 방법이 필요합니다. 이를 위해 하위 클래스를 약간 만들겠습니다.

import collections
class pair(collections.namedtuple('pair_base', 'key value')):
    def __hash__(self):
        return hash((self.key, None))
    def __eq__(self, other):
        if type(self) != type(other):
            return NotImplemented
        return self.key == other.key
    def __repr__(self):
        return repr((self.key, self.value))

그것만으로도 당신은 불변의 지도를 알 수 있는 거리에 놓이게 됩니다.

>>> frozenset(pair(k, v) for k, v in enumerate('abcd'))
frozenset([(0, 'a'), (2, 'c'), (1, 'b'), (3, 'd')])
>>> pairs = frozenset(pair(k, v) for k, v in enumerate('abcd'))
>>> pair(2, None) in pairs
True
>>> pair(5, None) in pairs
False
>>> goal = frozenset((pair(2, None),))
>>> pairs & goal
frozenset([(2, None)])

도! 유감스럽게도 집합 연산자를 사용할 때 원소들은 같으나 같은 물체는 아닙니다. 어떤 것이 반환 값이 되는지 정의되지 않으면 우리는 더 많은 회전을 거쳐야 할 것입니다.

>>> pairs - (pairs - goal)
frozenset([(2, 'c')])
>>> iter(pairs - (pairs - goal)).next().value
'c'

그러나 이런 식으로 가치를 찾는 것은 번거롭고, 더 나쁜 것은 많은 중간 집합을 만들어 내지만, 그렇게는 안 됩니다!이 문제를 해결하기 위해 '가짜' 키 값 쌍을 만듭니다.

class Thief(object):
    def __init__(self, key):
        self.key = key
    def __hash__(self):
        return hash(pair(self.key, None))
    def __eq__(self, other):
        self.value = other.value
        return pair(self.key, None) == other

그러면 문제가 덜 발생합니다.

>>> thief = Thief(2)
>>> thief in pairs
True
>>> thief.value
'c'

이것이 바로 깊은 마법의 전부입니다. 나머지는 명령어와 같은 인터페이스를 가진 것으로 모든 것을 포장하는 것입니다.지금부터 서브클래스를 하고 있으니까.frozenset 다른 있고 꽤 , 에서 . 우리는 약간의 도움을 받습니다.collections.Mapping이 .frozenset대신 명령어와 같이 작동하는 버전의 메소드:

class FrozenDict(frozenset, collections.Mapping):
    def __new__(cls, seq=()):
        return frozenset.__new__(cls, (pair(k, v) for k, v in seq))
    def __getitem__(self, key):
        thief = Thief(key)
        if frozenset.__contains__(self, thief):
            return thief.value
        raise KeyError(key)
    def __eq__(self, other):
        if not isinstance(other, FrozenDict):
            return dict(self.iteritems()) == other
        if len(self) != len(other):
            return False
        for key, value in self.iteritems():
            try:
                if value != other[key]:
                    return False
            except KeyError:
                return False
        return True
    def __hash__(self):
        return hash(frozenset(self.iteritems()))
    def get(self, key, default=None):
        thief = Thief(key)
        if frozenset.__contains__(self, thief):
            return thief.value
        return default
    def __iter__(self):
        for item in frozenset.__iter__(self):
            yield item.key
    def iteritems(self):
        for item in frozenset.__iter__(self):
            yield (item.key, item.value)
    def iterkeys(self):
        for item in frozenset.__iter__(self):
            yield item.key
    def itervalues(self):
        for item in frozenset.__iter__(self):
            yield item.value
    def __contains__(self, key):
        return frozenset.__contains__(self, pair(key, None))
    has_key = __contains__
    def __repr__(self):
        return type(self).__name__ + (', '.join(repr(item) for item in self.iteritems())).join('()')
    @classmethod
    def fromkeys(cls, keys, value=None):
        return cls((key, value) for key in keys)

궁극적으로, 제 질문에 대답할 수 있습니다.

>>> myDict = {}
>>> myDict[FrozenDict(enumerate('ab'))] = 5
>>> FrozenDict(enumerate('ab')) in myDict
True
>>> FrozenDict(enumerate('bc')) in myDict
False
>>> FrozenDict(enumerate('ab', 3)) in myDict
False
>>> myDict[FrozenDict(enumerate('ab'))]
5

@Unknown에서 허용된 답변과 @AlexMartelli에서 허용된 답변은 완벽하게 잘 작동하지만 다음과 같은 제약 조건 하에서만 작동합니다.

1. 사전의 값은 해시 가능해야 합니다.를 들면,면,hash(hashabledict({'a':[1,2]}))입니다.TypeError.
2. 키는 비교 작업을 지원해야 합니다.를 들면,면,hash(hashabledict({'a':'a', 1:1}))입니다.TypeError.
3. 키의 비교 연산자는 총 순서를 부과합니다.를 들어,두어인 ,frozenset((1,2,3))그리고.frozenset((4,5,6))은 두 방향 을 비교합니다 합니다.따라서 이러한 키를 사용하여 사전의 항목을 정렬하면 임의의 순서가 발생할 수 있으므로 동일한 개체의 해시 값이 동일해야 한다는 규칙을 위반하게 됩니다.

@ObenSonne의 훨씬 빠른 답변은 제약 조건 2와 3을 해제하지만 여전히 제약 조건 1에 의해 구속됩니다(값은 해시 가능해야 함).

@Raymond 의의 더 은 합니다를 에 세 조건을 합니다..values()해시 계산에 있어서 과 같은 경우에만합니다.그러나 성능은 다음과 같은 경우에만 양호합니다.

4. 하지 않은)한 의() 가 ..keys().

이 조건이 충족되지 않으면 해시 함수는 여전히 유효하지만 너무 많은 충돌이 발생할 수 있습니다.예를 들어, 모든 사전이 웹 사이트 템플릿(필드 이름은 키, 사용자 입력은 값)에서 생성되는 극단적인 경우 키는 항상 동일하고 해시 함수는 모든 입력에 대해 동일한 값을 반환합니다.따라서 해시 으로를 들어다(O(N)O(1)).

위에 기재한 4가지 제약조건을 모두 위반하더라도 아래의 해결책이 합리적으로 잘 작동할 것으로 생각합니다.중첩된 가변 컨테이너가 있더라도 사전뿐만 아니라 모든 컨테이너를 해시할 수 있다는 추가적인 이점이 있습니다.

제가 지금까지 가볍게 테스트를 해본 것뿐이니 이에 대한 피드백을 주시면 감사하겠습니다.

# python 3.4
import collections
import operator
import sys
import itertools
import reprlib

# a wrapper to make an object hashable, while preserving equality
class AutoHash:
    # for each known container type, we can optionally provide a tuple
    # specifying: type, transform, aggregator
    # even immutable types need to be included, since their items
    # may make them unhashable

    # transformation may be used to enforce the desired iteration
    # the result of a transformation must be an iterable
    # default: no change; for dictionaries, we use .items() to see values

    # usually transformation choice only affects efficiency, not correctness

    # aggregator is the function that combines all items into one object
    # default: frozenset; for ordered containers, we can use tuple

    # aggregator choice affects both efficiency and correctness
    # e.g., using a tuple aggregator for a set is incorrect,
    # since identical sets may end up with different hash values
    # frozenset is safe since at worst it just causes more collisions
    # unfortunately, no collections.ABC class is available that helps
    # distinguish ordered from unordered containers
    # so we need to just list them out manually as needed

    type_info = collections.namedtuple(
        'type_info',
        'type transformation aggregator')

    ident = lambda x: x
    # order matters; first match is used to handle a datatype
    known_types = (
        # dict also handles defaultdict
        type_info(dict, lambda d: d.items(), frozenset), 
        # no need to include set and frozenset, since they are fine with defaults
        type_info(collections.OrderedDict, ident, tuple),
        type_info(list, ident, tuple),
        type_info(tuple, ident, tuple),
        type_info(collections.deque, ident, tuple),
        type_info(collections.Iterable, ident, frozenset) # other iterables
    )

    # hash_func can be set to replace the built-in hash function
    # cache can be turned on; if it is, cycles will be detected,
    # otherwise cycles in a data structure will cause failure
    def __init__(self, data, hash_func=hash, cache=False, verbose=False):
        self._data=data
        self.hash_func=hash_func
        self.verbose=verbose
        self.cache=cache
        # cache objects' hashes for performance and to deal with cycles
        if self.cache:
            self.seen={}

    def hash_ex(self, o):
        # note: isinstance(o, Hashable) won't check inner types
        try:
            if self.verbose:
                print(type(o),
                    reprlib.repr(o),
                    self.hash_func(o),
                    file=sys.stderr)
            return self.hash_func(o)
        except TypeError:
            pass

        # we let built-in hash decide if the hash value is worth caching
        # so we don't cache the built-in hash results
        if self.cache and id(o) in self.seen:
            return self.seen[id(o)][0] # found in cache

        # check if o can be handled by decomposing it into components
        for typ, transformation, aggregator in AutoHash.known_types:
            if isinstance(o, typ):
                # another option is:
                # result = reduce(operator.xor, map(_hash_ex, handler(o)))
                # but collisions are more likely with xor than with frozenset
                # e.g. hash_ex([1,2,3,4])==0 with xor

                try:
                    # try to frozenset the actual components, it's faster
                    h = self.hash_func(aggregator(transformation(o)))
                except TypeError:
                    # components not hashable with built-in;
                    # apply our extended hash function to them
                    h = self.hash_func(aggregator(map(self.hash_ex, transformation(o))))
                if self.cache:
                    # storing the object too, otherwise memory location will be reused
                    self.seen[id(o)] = (h, o)
                if self.verbose:
                    print(type(o), reprlib.repr(o), h, file=sys.stderr)
                return h

        raise TypeError('Object {} of type {} not hashable'.format(repr(o), type(o)))

    def __hash__(self):
        return self.hash_ex(self._data)

    def __eq__(self, other):
        # short circuit to save time
        if self is other:
            return True

        # 1) type(self) a proper subclass of type(other) => self.__eq__ will be called first
        # 2) any other situation => lhs.__eq__ will be called first

        # case 1. one side is a subclass of the other, and AutoHash.__eq__ is not overridden in either
        # => the subclass instance's __eq__ is called first, and we should compare self._data and other._data
        # case 2. neither side is a subclass of the other; self is lhs
        # => we can't compare to another type; we should let the other side decide what to do, return NotImplemented
        # case 3. neither side is a subclass of the other; self is rhs
        # => we can't compare to another type, and the other side already tried and failed;
        # we should return False, but NotImplemented will have the same effect
        # any other case: we won't reach the __eq__ code in this class, no need to worry about it

        if isinstance(self, type(other)): # identifies case 1
            return self._data == other._data
        else: # identifies cases 2 and 3
            return NotImplemented

d1 = {'a':[1,2], 2:{3:4}}
print(hash(AutoHash(d1, cache=True, verbose=True)))

d = AutoHash(dict(a=1, b=2, c=3, d=[4,5,6,7], e='a string of chars'),cache=True, verbose=True)
print(hash(d))

v2 피클링 프로토콜이 hassdict 인스턴스와 함께 작동하도록 하려면 이 두 가지 방법을 추가해야 합니다.그렇지 않으면 cPickle이 hassdict를 사용하려고 합니다.____setitem____으로 인해 TypeError가 발생합니다.흥미롭게도 다른 두 버전의 프로토콜에서는 코드가 잘 작동합니다.

def __setstate__(self, objstate):
    for k,v in objstate.items():
        dict.__setitem__(self,k,v)
def __reduce__(self):
    return (hashdict, (), dict(self),)

python3의 올바른 방법입니다.

    class KeyDict(dict):
        def __hash__(self):
            return hash(frozenset(self.items()))

합니다를 합니다.frozenset(self)틀립니다(두 개의 다른 dict가 해시에 대해 동일한 입력을 가질 수 있음).실제로는 과도한 충돌이 발생하여 특정한 경우에 대한 조회가 O(n)로 줄어들 수 있습니다.

위의 해결책은 댓글로 언급되어 있지만, 주된 답이 되어야 합니다.

json 패키지를 사용하여 dictas 문자열을 직렬화합니다.

d = {'a': 1, 'b': 2}
s = json.dumps(d)

필요할 때 dict를 복원합니다.

d2 = json.loads(s)

사전에 숫자를 넣지 않고 사전을 포함하는 변수를 잃지 않는 경우 다음을 수행할 수 있습니다.

cache[id(rule)] = "whatever"

id ()는 모든 사전마다 고유하기 때문입니다.

편집:

아, 미안해요, 그럼 다른 남자들이 한 말이 더 낫겠네요.내 생각에는 당신이 당신의 사전을 문자열로 연속화할 수도 있을 것 같아요.

cache[ 'foo:bar' ] = 'baz'

키에서 사전을 복구해야 한다면 다음과 같은 추한 작업을 수행해야 합니다.

cache[ 'foo:bar' ] = ( {'foo':'bar'}, 'baz' )

이것의 장점은 코드를 그렇게 많이 쓰지 않아도 된다는 것입니다.

언급URL : https://stackoverflow.com/questions/1151658/python-hashable-dicts