O que seria um "ditado congelado"?

158
  • Um conjunto congelado é um frozenset.
  • Uma lista congelada pode ser uma tupla.
  • O que seria um ditado congelado? Um ditado imutável e lavável.

Eu acho que poderia ser algo assim collections.namedtuple, mas isso é mais como um ditado de chaves congeladas (um ditado meio congelado). Não é?

A "frozendict" deve ser um dicionário congelado, ele deve ter keys, values, get, etc., e de apoio in, foretc.

update:
* aqui está: https://www.python.org/dev/peps/pep-0603

dugres
fonte

Respostas:

120

O Python não possui um tipo frozendict interno. Acontece que isso não seria útil com muita frequência (embora provavelmente ainda seja útil com mais frequência do que frozenseté).

O motivo mais comum para querer esse tipo é quando a função de memorização solicita funções com argumentos desconhecidos. A solução mais comum para armazenar um equivalente lavável de um ditado (onde os valores são laváveis) é algo parecido tuple(sorted(kwargs.iteritems())).

Isso depende da classificação não ser um pouco insana. O Python não pode prometer positivamente que a classificação resultará em algo razoável aqui. (Mas não pode prometer muito mais, por isso não se preocupe muito.)


Você poderia facilmente criar algum tipo de invólucro que funciona como um ditado. Pode 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:
            hash_ = 0
            for pair in self.items():
                hash_ ^= hash(pair)
            self._hash = hash_
        return self._hash

Deve funcionar muito bem:

>>> 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'
Mike Graham
fonte
7
Não sei com que nível as pessoas se preocupam com esse tipo de coisa, mas nesse aspecto seu __hash__método pode ser ligeiramente aprimorado. Basta usar uma variável temporária ao calcular o hash e definir apenas self._hashquando você tiver o valor final. Dessa forma, outro encadeamento que obtém um hash enquanto o primeiro está calculando fará simplesmente um cálculo redundante, em vez de obter um valor incorreto.
perfil completo de Jeff DQ
22
@ Jeff Como regra, todo o código em todos os lugares não é seguro para threads, e você deve envolvê-lo em algumas estruturas de sincronização para usar esse código com segurança. Além disso, sua noção específica de segurança de encadeamento depende da atomicidade da atribuição de atributo do objeto, que está longe de ser garantida.
Devin Jeanpierre
9
@ Anentropic, isso não é verdade.
Mike Graham
17
Esteja avisado: Este "FrozenDict" não está necessariamente congelado. Não há nada para impedi-lo de colocar uma lista mutável como um valor; nesse caso, o hash emitirá um erro. Não há nada necessariamente errado nisso, mas os usuários devem estar cientes. Outra coisa: esse algoritmo de hash é mal escolhido, muito propenso a colisões de hash. Por exemplo, {'a': 'b'} faz o mesmo que {'b': 'a'} e {'a': 1, 'b': 2} faz o mesmo que {'a': 2 '' b ': 1}. Melhor escolha seria self._hash ^ = Hash ((chave, valor))
Steve Byrnes
6
Se você adicionar uma entrada mutável em um objeto imutável, os dois comportamentos possíveis são lançar um erro ao criar o objeto ou lançar um erro ao fazer o hash do objeto. Tuplas fazem o último, frozenset faz o primeiro. Definitivamente, acho que você tomou uma boa decisão de adotar a última abordagem, considerando todas as coisas. No entanto, acho que as pessoas podem ver que FrozenDict e frozenset têm nomes semelhantes e chegam à conclusão de que devem se comportar da mesma forma. Então eu acho que vale a pena alertar as pessoas sobre essa diferença. :-)
Steve Byrnes 11/11
63

Curiosamente, apesar de raramente termos utilidade frozensetem python, ainda não existe mapeamento congelado. A idéia foi rejeitada no PEP 416 - Adicione um tipo embutido no frozendict . A idéia pode ser revisitada no Python 3.9, consulte PEP 603 - Adicionando um tipo de mapa congelado às coleções .

Portanto, a solução python 2 para isso:

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

Ainda parece ser o pouco coxo:

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

Em python3 você tem a opção disso :

from types import MappingProxyType

default_config = {'a': 1}
DEFAULTS = MappingProxyType(default_config)

def foo(config=DEFAULTS):
    ...

Agora a configuração padrão pode ser atualizada dinamicamente, mas permanece imutável onde você deseja que seja imutável, passando pelo proxy.

Portanto, as alterações na default_configatualização serão DEFAULTSesperadas, mas você não pode gravar no próprio objeto de proxy de mapeamento.

É certo que não é a mesma coisa que um "ditado imutável e lavável" - mas é um substituto decente, dado o mesmo tipo de casos de uso para os quais podemos querer um frozendict.

wim
fonte
2
Existe algum motivo específico para armazenar o proxy em uma variável de módulo? Por que não apenas def foo(config=MappingProxyType({'a': 1})):? Seu exemplo ainda permite modificações globais default_configtambém.
Jpmc26
Além disso, suspeito que a dupla atribuição config = default_config = {'a': 1}seja um erro de digitação.
Jpmc26 26/05
21

Supondo que as chaves e os valores do dicionário sejam imutáveis ​​(por exemplo, strings), então:

>>> 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
msw
fonte
Essa é uma representação boa, canônica e imutável de um ditado (exceto o comportamento de comparação insano que atrapalha a classificação).
Mike Graham
6
@ Kevin: concordou na íntegra, mas vou deixar meu post como um exemplo de que muitas vezes há uma maneira ainda melhor.
Msw
14
Melhor ainda seria colocá-lo em um frozenset, que não requer que as chaves ou valores tenham uma ordem consistente definida.
asmeurer 22/05
7
Apenas um problema com isso: você não tem mais um mapeamento. Esse seria o objetivo de ter o ditado congelado em primeiro lugar.
May Physicist
2
Este método é muito bom quando se volta para um ditado. simplesmentedict(t)
codythecoder
12

Não existe fronzedict, mas você pode usar o MappingProxyTypeque foi adicionado à biblioteca padrão com o Python 3.3:

>>> from types import MappingProxyType
>>> foo = MappingProxyType({'a': 1})
>>> foo
mappingproxy({'a': 1})
>>> foo['a'] = 2
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
TypeError: 'mappingproxy' object does not support item assignment
>>> foo
mappingproxy({'a': 1})
Julio Marins
fonte
com a ressalva:TypeError: can't pickle mappingproxy objects
Radu
Eu gosto da ideia disso. Vou experimentar.
Doug
10

Aqui está o código que eu tenho usado. Eu subclassifiquei frozenset. As vantagens disso são as seguintes.

  1. Este é um objeto verdadeiramente imutável. Não é possível confiar no bom comportamento de futuros usuários e desenvolvedores.
  2. É fácil converter entre um dicionário comum e um dicionário congelado. FrozenDict (orig_dict) -> dicionário congelado. dict (frozen_dict) -> dict regular.

Atualização em 21 de janeiro de 2015: o código original que publiquei em 2014 usou um loop for para encontrar uma chave que correspondesse. Isso foi incrivelmente lento. Agora eu montei uma implementação que tira proveito dos recursos de hash do frozenset. Os pares de valores-chave são armazenados em contêineres especiais, onde as funções __hash__e __eq__são baseadas apenas na chave. Este código também foi formalmente testado em unidade, ao contrário do que publiquei aqui em agosto de 2014.

Licença 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)
Steve Zelaznik
fonte
1
Observe que você também o licenciou sob o CC BY-SA 3.0, publicando-o aqui. Pelo menos essa é a visão predominante . Eu acho que a base legal disso é concordar com alguns T&Cs quando você se inscreveu.
Evgeni Sergeev
1
Eu quebrei meu cérebro tentando pensar em uma maneira de procurar o hash chave sem um ditado. Redefinir o hash da chave Itempara ser o hash da chave é um puro truque!
Clacke
Infelizmente, o tempo de execução de diff(diff({key}))ainda é linear no tamanho do FrozenDict, enquanto o tempo de acesso regular ao dict é constante no caso médio.
Dennis
6

Penso em frozendict toda vez que escrevo uma função como esta:

def do_something(blah, optional_dict_parm=None):
    if optional_dict_parm is None:
        optional_dict_parm = {}
Mark Visser
fonte
6
Toda vez que vejo um comentário como esse, tenho certeza de que estraguei tudo em algum lugar e coloquei {} como padrão, e volte e veja meu código recentemente escrito.
Ryan Hiebert
1
Sim, é uma pegadinha desagradável que todo mundo encontra, mais cedo ou mais tarde.
Mark Visser
8
Formulação mais fácil: optional_dict_parm = optional_dict_parm or {}
Emmanuel
2
Nesse caso, você pode usar como valor padrão para argumento. types.MappingProxyType({})
GingerPlusPlus
@GingerPlusPlus você poderia escrever isso como uma resposta?
jonrsharpe
5

Você pode usar frozendictdo utilspiepacote 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 "<stdin>", line 1, in <module>
  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

Conforme o documento :

frozendict (dict_obj) : Aceita obj do tipo dict e retorna um dict lavável e imutável

Moinuddin Quadri
fonte
5

Instale o frozendict

pip install frozendict

Use-o!

from frozendict import frozendict

def smth(param = frozendict({})):
    pass
Andrey Korchak
fonte
3

Sim, esta é a minha segunda resposta, mas é uma abordagem completamente diferente. A primeira implementação foi em python puro. Este está em Cython. Se você sabe como usar e compilar módulos Cython, isso é tão rápido quanto um dicionário comum. Aproximadamente 0,04 a 0,06 microsseg para recuperar um único valor.

Este é o arquivo "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']

Aqui está o arquivo "setup.py"

from distutils.core import setup
from Cython.Build import cythonize

setup(
    ext_modules = cythonize('frozen_dict.pyx')
)

Se você tiver o Cython instalado, salve os dois arquivos acima no mesmo diretório. Mover para esse diretório na linha de comando.

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

E você deveria terminar.

Steve Zelaznik
fonte
3

A principal desvantagem namedtupleé que ele precisa ser especificado antes de ser usado, portanto, é menos conveniente para casos de uso único.

No entanto, existe uma solução prática que pode ser usada para lidar com muitos desses casos. Digamos que você queira ter um equivalente imutável do seguinte ditado:

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

Isso pode ser emulado assim:

from collections import namedtuple

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

É até possível escrever uma função auxiliar para automatizar isso:

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

É claro que isso funciona apenas para ditados planos, mas não deve ser muito difícil implementar uma versão recursiva.

Berislav Lopac
fonte
1
O mesmo problema da outra resposta da tupla: você precisa fazer, em getattr(fa, x)vez de fa[x], nenhum keysmétodo na ponta dos dedos e todos os outros motivos pelos quais um mapeamento pode ser desejável.
Mad Physicist
1

Subclassificação dict

Eu vejo esse padrão em estado selvagem (github) e queria mencioná-lo:

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

exemplo 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

Prós

  • suporte para get(), keys(), items()( iteritems()em PY2) e todas as guloseimas de dictfora da caixa, sem implementá-las explicitamente
  • usa internamente, o dictque significa desempenho ( dicté escrito em c no CPython)
  • elegante simples e sem magia negra
  • isinstance(my_frozen_dict, dict)retorna True - embora o python incentive a digitação por patos de muitos pacotes isinstance(), isso pode salvar muitos ajustes e personalizações

Contras

  • qualquer subclasse pode substituir isso ou acessá-lo internamente (você não pode realmente proteger 100% de algo em python, deve confiar em seus usuários e fornecer uma boa documentação).
  • se você gosta de velocidade, pode querer __hash__acelerar um pouco.
ShmulikA
fonte
Fiz uma comparação de velocidade em outro segmento e, ao contrário, substituir __setitem__e herdar dicté incrivelmente rápido em comparação com muitas alternativas.
Torxed 10/06
0

Outra opção é a MultiDictProxyclasse do multidictpacote.

Berislav Lopac
fonte
1
Infelizmente, não é lavável.
rominf 24/03
0

Eu precisava acessar chaves fixas para algo em um ponto para algo que era um tipo de coisa globalmente constante e decidi algo assim:

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

Use-o como

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

AVISO: Eu não recomendo isso para a maioria dos casos de uso, pois isso gera algumas trocas bastante graves.

Adverbly
fonte
O seguinte seria igual em poder sem os escassos de desempenho. No entanto, isso é apenas uma simplificação da resposta aceita ... `` `classe FrozenDict: def __init __ (self, data): self._data = data def __getitem __ (self, key): return self._data [key]` ` `
Yuval
@Yuval essa resposta não é equivalente. Para iniciantes, a API é diferente, pois precisa de dados para iniciar. Isso também implica que não é mais acessível globalmente. Além disso, se _data estiver mutado, seu valor de retorno será alterado. Estou ciente de que existem trocas significativas - como eu disse, não recomendo isso na maioria dos casos de uso.
Adverbly
-1

Na ausência de suporte ao idioma nativo, você pode fazer isso sozinho ou usar uma solução existente. Felizmente, o Python simplifica bastante a extensão de suas implementações básicas.

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
efervescente
fonte
Sua classe frozen_dict não é lavável
miracle173 7/06