lenguaje - python wikipedia
Python hashable dicts (9)
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é. ( EDITAR : una consecuencia de este uso de las colecciones 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 están bien)
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. 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. continuar 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''}
De acuerdo. 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 diferentes deberían ser las mismas:
>>> 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 obtengo los dict s que se pueden usar 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 a 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()
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())))
Es posible que también desee agregar estos dos métodos para que el protocolo de decapado v2 funcione con las instancias de 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),)
La respuesta aceptada por @Unknown, así como la respuesta de @AlexMartelli funcionan perfectamente bien, pero solo bajo las siguientes limitaciones:
- Los valores del diccionario deben ser hashable. Por ejemplo,
hash(hashabledict({''a'':[1,2]}))levantaráTypeError. - Las claves deben ser compatibles con la operación de comparación. Por ejemplo,
hash(hashabledict({''a'':''a'', 1:1}))levantaráTypeError. - El operador de comparación en las teclas impone el orden total. Por ejemplo, si las dos teclas en un diccionario son
frozenset((1,2,3))yfrozenset((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 fáciles de manejar).
La respuesta más rápida aún por @RaymondHettinger levanta las 3 restricciones porque no incluye .values() en el cálculo hash. Sin embargo, su rendimiento es bueno solo si:
- La mayoría de los diccionarios (no iguales) que deben ser hash no tienen
.keys()idénticos.keys().
Si no se cumple esta condición, la función hash 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) 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 probé esto 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))
Las Hashables deben ser inmutables, no aplicando esto, pero SI CONFÍAN en ti para no mutar un dict después de su primer uso como 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 DEBES mutar tus dictados y TODAVÍA quieres utilizarlos como claves, la complejidad explota cientos de veces, 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! -)
Las respuestas dadas están bien, pero podrían mejorarse usando frozenset(...) 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 de los casos que he probado, el hashing con frozenset es al menos 2 veces más rápido (principalmente porque no necesita ordenar).
Si no coloca números en el diccionario y nunca pierde las variables que contienen sus diccionarios, puede hacer esto:
cache[id(rule)] = "whatever"
desde id () es único para cada diccionario
EDITAR:
Oh, lo siento, sí, en ese caso lo que los demás dijeron sería mejor. Creo que también puedes serializar tus diccionarios como una cadena, como
cache[ ''foo:bar'' ] = ''baz''
Si necesita recuperar sus diccionarios de las teclas, entonces 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.
Sigo volviendo a este tema ... Aquí hay otra variación. Me incomoda la subclasificación de 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 la tuple es una elecció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 bloquea la clave, valora los pares en un frozenset ? ¿Qué requeriría eso? ¿Cómo funcionaría?
Parte 1, necesitas una forma de codificar el ''elemento 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))
Solo eso te pone a la distancia 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 de los dos termina en el valor de retorno no está definido , 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! Crearemos un par clave-valor ''falso'' para evitarlo:
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
Lo que resulta en el menos problemático:
>>> thief = Thief(2)
>>> thief in pairs
True
>>> thief.value
''c''
Esa es toda la magia profunda; el resto lo está envolviendo en algo que tiene una interfaz como un dict. Como estamos subclasificando desde frozenset , que tiene una interfaz muy diferente, hay muchos métodos; recibimos un poco de ayuda de las collections.Mapping . Asignación de mapas, pero la mayor parte del trabajo está anulando los métodos frozenset para las versiones que funcionan como dicts, 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)
que, en última instancia, responde 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
Todo lo que se necesita para hacer diccionarios utilizables para su propósito es agregar un método __hash__:
class Hashabledict(dict):
def __hash__(self):
return hash(frozenset(self))
Tenga en cuenta que la conversión de frozenset 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 claves 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. Primero, el paso frozenset(self) reutiliza los valores hash almacenados en el diccionario, guardando llamadas innecesarias a hash(key) . En segundo lugar, al utilizar itervalues accederá directamente a los valores y evitará las muchas llamadas al asignador de memoria que utilizan elementos para formar nuevas muchas tuplas de clave / valor en la memoria cada vez que realiza una búsqueda.
Una implementación razonablemente limpia y directa 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())))