¿Qué sería un “dict congelado”?

  • Un conjunto congelado es un frozenset.
  • Una lista congelada podría ser una tupla.
  • ¿Qué sería un dictado congelado? Un dictado inmutable, hashable.

Supongo que podría ser algo así como collections.namedtuple . Se llamaron dos veces, pero eso es más como un dict de teclas congeladas (un dict medio congelado). ¿No es así?

Un “frozendict” debe ser un diccionario congelado, debe tener keys , values , get , etc., y soporte in , for , etc.

Python no tiene un tipo de frozendict incorporado. Resulta que esto no sería útil con demasiada frecuencia (aunque aún así probablemente sería útil más a menudo que frozenset ).

La razón más común para desear ese tipo es cuando la función de memorización requiere funciones con argumentos desconocidos. La solución más común para almacenar un hashable equivalente a un dict (donde los valores son hashable) es algo así como tuple(sorted(kwargs.iteritems())) .

Esto depende de que la clasificación no sea un poco insana. Python no puede prometer positivamente que la clasificación resultará en algo razonable aquí. (Pero no puede prometer mucho más, así que no te preocupes demasiado).


Podrías fácilmente hacer algún tipo de envoltura que funcione como un dict. Podría parecer algo como

 import collections class FrozenDict(collections.Mapping): """Don't forget the docstrings!!""" def __init__(self, *args, **kwargs): self._d = dict(*args, **kwargs) self._hash = None 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): # It would have been simpler and maybe more obvious to # use hash(tuple(sorted(self._d.iteritems()))) from this discussion # so far, but this solution is O(n). I don't know what kind of # n we are going to run into, but sometimes it's hard to resist the # urge to optimize when it will gain improved algorithmic performance. if self._hash is None: self._hash = 0 for pair in self.iteritems(): self._hash ^= hash(pair) return self._hash 

Debería funcionar muy bien:

 >>> x = FrozenDict(a=1, b=2) >>> y = FrozenDict(a=1, b=2) >>> x is y False >>> x == y True >>> x == {'a': 1, 'b': 2} True >>> d = {x: 'foo'} >>> d[y] 'foo' 

Curiosamente, aunque tenemos el raramente útil frozenset en python, todavía no hay mapas congelados. La idea fue rechazada en PEP 416 .

Así que la solución de python 2 para esto:

 def foo(config={'a': 1}): ... 

Todavía parece ser un poco cojo:

 def foo(config=None): if config is None: config = default_config = {'a': 1} ... 

En python3 tienes la opción de esto :

 from types import MappingProxyType default_config = {'a': 1} DEFAULTS = MappingProxyType(default_config) def foo(config=DEFAULTS): ... 

Ahora la configuración predeterminada se puede actualizar dinámicamente, pero permanece inmutable donde quieres que sea inmutable pasando el proxy en su lugar.

Por lo tanto, los cambios en el default_config actualizarán DEFAULTS como se esperaba, pero no se puede escribir en el objeto proxy de mapeo en sí.

Es cierto que no es exactamente lo mismo que un “dict de hashable e inmutable”, pero es un sustituto decente dado el mismo tipo de casos de uso para los que podríamos querer un frozendict.

Asumiendo que las claves y los valores del diccionario son en sí mismos inmutables (por ejemplo, cadenas), entonces:

 >>> d {'forever': 'atones', 'minks': 'cards', 'overhands': 'warranted', 'hardhearted': 'tartly', 'gradations': 'snorkeled'} >>> t = tuple((k, d[k]) for k in sorted(d.keys())) >>> hash(t) 1524953596 

Aquí está el código que he estado usando. Subclasifico el frozenset. Las ventajas de esto son las siguientes.

  1. Este es un objeto verdaderamente inmutable. No confiar en el buen comportamiento de futuros usuarios y desarrolladores.
  2. Es fácil convertir una y otra vez entre un diccionario regular y un diccionario congelado. FrozenDict (orig_dict) -> diccionario congelado. dict (frozen_dict) -> dict regular.

Actualización del 21 de enero de 2015: el código original que publiqué en 2014 usaba un bucle for para encontrar una clave que coincidiera. Eso fue increíblemente lento. Ahora he reunido una implementación que aprovecha las características de hashing de frozenset. Los pares clave-valor se almacenan en contenedores especiales donde las funciones __hash__ y __eq__ se basan únicamente en la clave. Este código también ha sido probado formalmente por unidades, a diferencia de lo que publiqué aquí en agosto de 2014.

Licencia de estilo MIT.

 if 3 / 2 == 1: version = 2 elif 3 / 2 == 1.5: version = 3 def col(i): ''' For binding named attributes to spots inside subclasses of tuple.''' g = tuple.__getitem__ @property def _col(self): return g(self,i) return _col class Item(tuple): ''' Designed for storing key-value pairs inside a FrozenDict, which itself is a subclass of frozenset. The __hash__ is overloaded to return the hash of only the key. __eq__ is overloaded so that normally it only checks whether the Item's key is equal to the other object, HOWEVER, if the other object itself is an instance of Item, it checks BOTH the key and value for equality. WARNING: Do not use this class for any purpose other than to contain key value pairs inside FrozenDict!!!! The __eq__ operator is overloaded in such a way that it violates a fundamental property of mathematics. That property, which says that a == b and b == c implies a == c, does not hold for this object. Here's a demonstration: [in] >>> x = Item(('a',4)) [in] >>> y = Item(('a',5)) [in] >>> hash('a') [out] >>> 194817700 [in] >>> hash(x) [out] >>> 194817700 [in] >>> hash(y) [out] >>> 194817700 [in] >>> 'a' == x [out] >>> True [in] >>> 'a' == y [out] >>> True [in] >>> x == y [out] >>> False ''' __slots__ = () key, value = col(0), col(1) def __hash__(self): return hash(self.key) def __eq__(self, other): if isinstance(other, Item): return tuple.__eq__(self, other) return self.key == other def __ne__(self, other): return not self.__eq__(other) def __str__(self): return '%r: %r' % self def __repr__(self): return 'Item((%r, %r))' % self class FrozenDict(frozenset): ''' Behaves in most ways like a regular dictionary, except that it's immutable. It differs from other implementations because it doesn't subclass "dict". Instead it subclasses "frozenset" which guarantees immutability. FrozenDict instances are created with the same arguments used to initialize regular dictionaries, and has all the same methods. [in] >>> f = FrozenDict(x=3,y=4,z=5) [in] >>> f['x'] [out] >>> 3 [in] >>> f['a'] = 0 [out] >>> TypeError: 'FrozenDict' object does not support item assignment FrozenDict can accept un-hashable values, but FrozenDict is only hashable if its values are hashable. [in] >>> f = FrozenDict(x=3,y=4,z=5) [in] >>> hash(f) [out] >>> 646626455 [in] >>> g = FrozenDict(x=3,y=4,z=[]) [in] >>> hash(g) [out] >>> TypeError: unhashable type: 'list' FrozenDict interacts with dictionary objects as though it were a dict itself. [in] >>> original = dict(x=3,y=4,z=5) [in] >>> frozen = FrozenDict(x=3,y=4,z=5) [in] >>> original == frozen [out] >>> True FrozenDict supports bi-directional conversions with regular dictionaries. [in] >>> original = {'x': 3, 'y': 4, 'z': 5} [in] >>> FrozenDict(original) [out] >>> FrozenDict({'x': 3, 'y': 4, 'z': 5}) [in] >>> dict(FrozenDict(original)) [out] >>> {'x': 3, 'y': 4, 'z': 5} ''' __slots__ = () def __new__(cls, orig={}, **kw): if kw: d = dict(orig, **kw) items = map(Item, d.items()) else: try: items = map(Item, orig.items()) except AttributeError: items = map(Item, orig) return frozenset.__new__(cls, items) def __repr__(self): cls = self.__class__.__name__ items = frozenset.__iter__(self) _repr = ', '.join(map(str,items)) return '%s({%s})' % (cls, _repr) def __getitem__(self, key): if key not in self: raise KeyError(key) diff = self.difference item = diff(diff({key})) key, value = set(item).pop() return value def get(self, key, default=None): if key not in self: return default return self[key] def __iter__(self): items = frozenset.__iter__(self) return map(lambda i: i.key, items) def keys(self): items = frozenset.__iter__(self) return map(lambda i: i.key, items) def values(self): items = frozenset.__iter__(self) return map(lambda i: i.value, items) def items(self): items = frozenset.__iter__(self) return map(tuple, items) def copy(self): cls = self.__class__ items = frozenset.copy(self) dupl = frozenset.__new__(cls, items) return dupl @classmethod def fromkeys(cls, keys, value): d = dict.fromkeys(keys,value) return cls(d) def __hash__(self): kv = tuple.__hash__ items = frozenset.__iter__(self) return hash(frozenset(map(kv, items))) def __eq__(self, other): if not isinstance(other, FrozenDict): try: other = FrozenDict(other) except Exception: return False return frozenset.__eq__(self, other) def __ne__(self, other): return not self.__eq__(other) if version == 2: #Here are the Python2 modifications class Python2(FrozenDict): def __iter__(self): items = frozenset.__iter__(self) for i in items: yield i.key def iterkeys(self): items = frozenset.__iter__(self) for i in items: yield i.key def itervalues(self): items = frozenset.__iter__(self) for i in items: yield i.value def iteritems(self): items = frozenset.__iter__(self) for i in items: yield (i.key, i.value) def has_key(self, key): return key in self def viewkeys(self): return dict(self).viewkeys() def viewvalues(self): return dict(self).viewvalues() def viewitems(self): return dict(self).viewitems() #If this is Python2, rebuild the class #from scratch rather than use a subclass py3 = FrozenDict.__dict__ py3 = {k: py3[k] for k in py3} py2 = {} py2.update(py3) dct = Python2.__dict__ py2.update({k: dct[k] for k in dct}) FrozenDict = type('FrozenDict', (frozenset,), py2) 

Pienso en frozendict cada vez que escribo una función como esta:

 def do_something(blah, optional_dict_parm=None): if optional_dict_parm is None: optional_dict_parm = {} 

No hay ningún fronzedict pero puedes usar MappingProxyType :

 >>> from types import MappingProxyType >>> foo = MappingProxyType({'a': 1}) >>> foo mappingproxy({'a': 1}) >>> foo['a'] = 2 Traceback (most recent call last): File "", line 1, in  TypeError: 'mappingproxy' object does not support item assignment >>> foo mappingproxy({'a': 1}) 

Puede usar frozendict del paquete utilspie como:

 >>> from utilspie.collectionsutils import frozendict >>> my_dict = frozendict({1: 3, 4: 5}) >>> my_dict # object of `frozendict` type frozendict({1: 3, 4: 5}) # Hashable >>> {my_dict: 4} {frozendict({1: 3, 4: 5}): 4} # Immutable >>> my_dict[1] = 5 Traceback (most recent call last): File "", line 1, in  File "/Users/mquadri/workspace/utilspie/utilspie/collectionsutils/collections_utils.py", line 44, in __setitem__ self.__setitem__.__name__, type(self).__name__)) AttributeError: You can not call '__setitem__()' for 'frozendict' object 

Según el documento :

frozendict (dict_obj) : Acepta obj de tipo dict y devuelve un dictado hashable e inmutable

Sí, esta es mi segunda respuesta, pero es un enfoque completamente diferente. La primera implementación fue en python puro. Este está en Cython. Si sabe cómo usar y comstackr módulos de Cython, esto es tan rápido como un diccionario regular. Aproximadamente .04 a .06 microsegundos para recuperar un solo valor.

Este es el archivo “frozen_dict.pyx”

 import cython from collections import Mapping cdef class dict_wrapper: cdef object d cdef int h def __init__(self, *args, **kw): self.d = dict(*args, **kw) self.h = -1 def __len__(self): return len(self.d) def __iter__(self): return iter(self.d) def __getitem__(self, key): return self.d[key] def __hash__(self): if self.h == -1: self.h = hash(frozenset(self.d.iteritems())) return self.h class FrozenDict(dict_wrapper, Mapping): def __repr__(self): c = type(self).__name__ r = ', '.join('%r: %r' % (k,self[k]) for k in self) return '%s({%s})' % (c, r) __all__ = ['FrozenDict'] 

Aquí está el archivo “setup.py”

 from distutils.core import setup from Cython.Build import cythonize setup( ext_modules = cythonize('frozen_dict.pyx') ) 

Si tiene Cython instalado, guarde los dos archivos de arriba en el mismo directorio. Mover a ese directorio en la línea de comandos.

 python setup.py build_ext --inplace python setup.py install 

Y deberías estar hecho.

La principal desventaja de namedtuple es que debe especificarse antes de su uso, por lo que es menos conveniente para los casos de un solo uso.

Sin embargo, existe una solución práctica que se puede utilizar para manejar muchos de estos casos. Digamos que desea tener un equivalente inmutable del siguiente dictado:

 MY_CONSTANT = { 'something': 123, 'something_else': 456 } 

Esto se puede emular así:

 from collections import namedtuple MY_CONSTANT = namedtuple('MyConstant', 'something something_else')(123, 456) 

Incluso es posible escribir una función auxiliar para automatizar esto:

 def freeze_dict(data): from collections import namedtuple keys = sorted(data.keys()) frozen_type = namedtuple(''.join(keys), keys) return frozen_type(**data) a = {'foo':'bar', 'x':'y'} fa = freeze_dict(data) assert a['foo'] == fa.foo 

Por supuesto, esto solo funciona para los dictados sin formato, pero no debería ser demasiado difícil implementar una versión recursiva.

Instalar frozendict

 pip install frozendict 

¡Úsalo!

 from frozendict import frozendict def smth(param = frozendict({})): pass 

Otra opción es la clase MultiDictProxy del paquete multidict .

dict subclases

Veo este patrón en la naturaleza (github) y quería mencionarlo:

 class FrozenDict(dict): def __init__(self, *args, **kwargs): self._hash = None super(FrozenDict, self).__init__(*args, **kwargs) def __hash__(self): if self._hash is None: self._hash = hash(tuple(sorted(self.items()))) # iteritems() on py2 return self._hash def _immutable(self, *args, **kws): raise TypeError('cannot change object - object is immutable') __setitem__ = _immutable __delitem__ = _immutable pop = _immutable popitem = _immutable clear = _immutable update = _immutable setdefault = _immutable 

ejemplo de uso:

 d1 = FrozenDict({'a': 1, 'b': 2}) d2 = FrozenDict({'a': 1, 'b': 2}) d1.keys() assert isinstance(d1, dict) assert len(set([d1, d2])) == 1 # hashable 

Pros

  • soporte para get() , keys() , items() ( iteritems() en py2) y todos los extras de dict out del cuadro sin implementarlos explícitamente
  • usa dict internamente que significa rendimiento ( dict está escrito en c en CPython)
  • Elegante simple y sin magia negra.
  • isinstance(my_frozen_dict, dict) devuelve True – aunque python recomienda que muchos paquetes isinstance() , esto puede ahorrar muchos ajustes y personalizaciones

Contras

  • cualquier subclase puede anular esto o acceder a él internamente (no puede realmente proteger al 100% algo en Python, debe confiar en sus usuarios y proporcionar una buena documentación).
  • Si te importa la velocidad, es posible que desees __hash__ un poco más rápido.

En ausencia de soporte de idioma nativo, puede hacerlo usted mismo o usar una solución existente. Afortunadamente, Python hace que sea muy sencillo extender sus implementaciones base.

 class frozen_dict(dict): def __setitem__(self, key, value): raise Exception('Frozen dictionaries cannot be mutated') frozen_dict = frozen_dict({'foo': 'FOO' }) print(frozen['foo']) # FOO frozen['foo'] = 'NEWFOO' # Exception: Frozen dictionaries cannot be mutated # OR from types import MappingProxyType frozen_dict = MappingProxyType({'foo': 'FOO'}) print(frozen_dict['foo']) # FOO frozen_dict['foo'] = 'NEWFOO' # TypeError: 'mappingproxy' object does not support item assignment 

Necesitaba acceder a claves fijas para algo en un punto para algo que era una especie de tipo de constante global y me decidí por algo como esto:

 class MyFrozenDict: def __getitem__(self, key): if key == 'mykey1': return 0 if key == 'mykey2': return "another value" raise KeyError(key) 

Utilízalo como

 a = MyFrozenDict() print(a['mykey1']) 

ADVERTENCIA: no lo recomiendo para la mayoría de los casos de uso, ya que hace algunas concesiones bastante severas.