Python hasts intercambiables

Question

Como ejercicio, y sobre todo para mi propia diversión, estoy implementando un analizador packrat de retroceso. La inspiración para esto es que me gustaría tener una mejor idea acerca de cómo funcionarían las macros higiénicas en un lenguaje similar a algol (como en el dialecto de lisp libre de sintaxis en el que normalmente las encuentras). Debido a esto, las diferentes pasadas a través de la entrada pueden ver diferentes gramáticas, por lo que los resultados de análisis en caché no son válidos, a menos que también almacene la versión actual de la gramática junto con los resultados de análisis en caché. (EDIT: una consecuencia de este uso de colecciones de clave-valor es que deben ser inmutables, pero no pretendo exponer la interfaz para permitir su modificación, por lo que las colecciones mutables o inmutables son correctas)

El problema es que los dictados de python no pueden aparecer como claves para otros dicts. Incluso usar una tupla (como lo estaría haciendo de todos modos) no ayuda.

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

Supongo que tiene que ser tuplas todo el camino hacia abajo. Ahora la biblioteca estándar de Python proporciona aproximadamente lo que necesitaría, collections.namedtuple tiene una sintaxis muy diferente, pero puede usarse como clave. continuando desde la sesión anterior:

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

Ok. Pero tengo que hacer una clase para cada posible combinación de claves en la regla que quisiera usar, lo cual no es tan malo, ya que cada regla de análisis sabe exactamente qué parámetros usa, por lo que la clase se puede definir al mismo tiempo como la función que analiza la regla.

Editar: Un problema adicional con namedtuple s es que son estrictamente posicionales. Dos tuplas que parecen que deben ser diferentes de hecho, puede ser el mismo:

>>> 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: ¿Cómo llego dict s que pueden ser utilizados como claves para otros dict s?

Habiendo hackeado un poco las respuestas, esta es la solución más completa que estoy usando. Tenga en cuenta que esto hace un poco más de trabajo para que los dictados resultantes sean vagamente inmutables con fines prácticos. Por supuesto, todavía es bastante fácil hackearlo llamando al dict.__setitem__(instance, key, value), pero todos somos adultos aquí.

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() 

Answer 1

Aquí está la manera fácil de hacer un diccionario manejable. Solo recuerde no mutarlos después de incrustarlos en otro diccionario por razones obvias.

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

Answer 2

Hashables debe ser inmutable - no hacer cumplir esto, pero no confiar en ti para mutar un diccionario después de su primer uso como una clave, el siguiente enfoque funcionaría:

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() 

Si usted no necesita mute sus dictados y TODAVÍA quiera usarlos como claves, la complejidad explota cientos de pliegues, por no decir que no se puede hacer, pero esperaré hasta una indicación MUY específica antes de entrar en ESE increíble pantano! -)

Answer 3

A, implementación directa razonablemente limpia es

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()))) 

Answer 4

Usted también puede añadir estos dos métodos para obtener el decapado v2 protocolo de trabajo con instancias hashdict. De lo contrario, cPickle intentará usar hashdict .____ setitem____ dando como resultado un TypeError.Curiosamente, con las otras dos versiones del protocolo tu código funciona bien.

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

Answer 5

Las respuestas están bien, pero podrían mejorarse mediante el uso de frozenset(...) en lugar de tuple(sorted(...)) para generar el hash:

>>> 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 

La ventaja de rendimiento depende del contenido del diccionario, pero en la mayoría En los casos que he probado, el hash con frozenset es al menos 2 veces más rápido (principalmente porque no es necesario ordenarlo).

Answer 6

Si usted no pone números en el diccionario y que nunca pierda las variables que contienen los diccionarios, se puede hacer esto:

cache[id(rule)] = "whatever"

desde id() es único para todos los diccionarios

EDITAR:

Oh, lo siento, sí, en ese caso lo que los otros chicos dijeron sería mejor. Creo que también se puede serializar los diccionarios como una cadena, como

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

Si necesita recuperar sus diccionarios de las teclas sin embargo, entonces usted tendría que hacer algo más feo como

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

Supongo que la ventaja de esto es que no tendrías que escribir tanto código.

Answer 7

Sigo volviendo a este tema ... Aquí hay otra variación. Estoy incómodo con la subclasificación dict para agregar un método __hash__; Prácticamente no hay escapatoria del problema de que los dict son mutables, y confiar en que no cambiarán parece una idea débil. Así que, en cambio, he buscado construir una asignación basada en un tipo integrado que sea inmutable. aunque tuple es una opción obvia, acceder a los valores en ella implica una clasificación y una bisección; no es un problema, pero no parece estar aprovechando gran parte del poder del tipo en el que está basado.

¿Qué pasa si se atasca la clave, pares de valores en un frozenset? ¿Qué requeriría eso? ¿Cómo funcionaría?

Parte 1, necesita una forma de codificar los 'elementos de tal manera que un frozenset los trate principalmente por sus claves; Haré una pequeña subclase para eso.

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)) 

Eso por sí solo le pone en un tiro de piedra de un mapeo inmutable:

>>> 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)]) 

D'oh! Desafortunadamente, cuando usa los operadores establecidos y los elementos son iguales pero no el mismo objeto; cuál termina en el valor de retorno es undefined, tendremos que pasar por más giros.

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

Sin embargo, buscar valores de esta manera es engorroso, y lo que es peor, crea muchos conjuntos intermedios; eso no va a hacer!Vamos a crear un par 'falso' valor clave para conseguir alrededor de él:

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 

que da lugar a la menos problemática:

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

Esa es toda la magia profunda; el resto lo está envolviendo todo en algo que tiene una interfaz como un dict. Como estamos creando subclases desde frozenset, que tiene una interfaz muy diferente, hay muchos métodos; conseguimos un poco de ayuda de collections.Mapping, pero la mayor parte del trabajo es reemplazar los métodos frozenset para las versiones que funcionan como predice, en su lugar:

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) 

la que, en última instancia, no responder a mi propia pregunta:

>>> 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 

Answer 8

Todo lo que se necesita para hacer los diccionarios utilizable para su propósito es añadir un método __hash__:

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

Nota, la congeló nset la conversión funcionará para todos los diccionarios (es decir no requiere que las claves sean ordenables). Del mismo modo, no hay restricciones en los valores del diccionario.

Si hay muchos diccionarios con teclas idénticas pero con valores distintos, es necesario que el hash tenga en cuenta los valores. La forma más rápida de hacerlo es:

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

Esto es más rápido que frozenset(self.iteritems()) por dos razones. En primer lugar, el paso frozenset(self) reutiliza los valores hash almacenados en el diccionario, guardando llamadas innecesarias al hash(key). En segundo lugar, al utilizar , el archivo accederá directamente a los valores y evitará las llamadas a muchos asignadores de memoria utilizando elementos para formar nuevas muchas tuplas de clave/valor en la memoria cada vez que realice una búsqueda.

Answer 9

La respuesta aceptada por @Unknown, así como la respuesta por @AlexMartelli funciona perfectamente bien, pero sólo bajo las siguientes restricciones: los valores

1. del diccionario debe ser hashable. Por ejemplo, hash(hashabledict({'a':[1,2]})) aumentará TypeError.
2. Las claves deben admitir la operación de comparación. Por ejemplo, hash(hashabledict({'a':'a', 1:1})) aumentará TypeError.
3. El operador de comparación en las teclas impone el orden total. Por ejemplo, si las dos claves en un diccionario son frozenset((1,2,3)) y frozenset((4,5,6)), se compararán desiguales en ambas direcciones. Por lo tanto, clasificar los elementos de un diccionario con dichas claves puede dar como resultado un orden arbitrario, y por lo tanto violará la regla de que los objetos iguales deben tener el mismo valor hash.

La respuesta mucho más rápida de @ObenSonne levanta las restricciones 2 y 3, pero sigue estando unida por la restricción 1 (los valores deben ser manejables).

La respuesta aún más rápida por @RaymondHettinger levanta las 3 restricciones porque no incluye .values() en el cálculo hash.Sin embargo, su rendimiento es bueno solo si:

4. La mayoría de los diccionarios (no iguales) que deben ser hash no tienen el mismo .keys().

Si no se cumple esta condición, la función de almohadillado seguirá siendo válida, pero puede causar demasiadas colisiones. Por ejemplo, en el caso extremo en que todos los diccionarios se generan a partir de una plantilla de sitio web (nombres de campo como claves, entrada de usuario como valores), las claves siempre serán las mismas, y la función hash devolverá el mismo valor para todas las entradas . Como resultado, una tabla hash que se basa en dicha función hash será tan lenta como una lista al recuperar un elemento (O(N) en lugar de O(1)).

Creo que la siguiente solución funcionará razonablemente bien incluso si se violan las 4 restricciones que enumeré anteriormente. Tiene la ventaja adicional de que no solo puede utilizar diccionarios, sino también contenedores, incluso si tienen contenedores anidados anidados.

Agradecería cualquier comentario sobre esto, ya que solo lo probé hasta ahora.

# 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))