Каким будет «замороженный дикт»?

158
  • Замороженный набор - это фрозенет.
  • Замороженный список может быть кортежем.
  • Каким будет замороженный дикт? Неизменный, бескомпромиссный диктат.

Я думаю, что это может быть что-то вроде collections.namedtuple, но это больше похоже на диктат замороженных ключей (полузамороженный диктат). Не так ли?

А «frozendict» должен быть заморожен словарем, он должен иметь keys, values, getи т.д., и поддержку in, forи т.д.

обновление:
* вот оно: https://www.python.org/dev/peps/pep-0603

dugres
источник

Ответы:

120

Python не имеет встроенного типа frozendict. Оказывается, это не будет полезно слишком часто (хотя, вероятно, это будет полезно чаще, чем frozensetесть).

Наиболее распространенная причина, по которой такой тип нужен, - это запоминание вызовов функций для функций с неизвестными аргументами. Наиболее распространенное решение для хранения хешируемого эквивалента dict (где значения могут быть хешируемыми) выглядит примерно так tuple(sorted(kwargs.iteritems())).

Это зависит от того, что сортировка не слишком сумасшедшая. Python не может положительно обещать, что сортировка приведет к чему-то разумному здесь. (Но это не может обещать многого другого, поэтому не переживайте слишком сильно.)


Вы могли бы довольно легко сделать какую-то обертку, которая работает очень похоже на диктовку. Это может выглядеть примерно так

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

Должно работать отлично:

>>> 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'
Майк Грэм
источник
7
Я не знаю, о каком уровне безопасности потоков беспокоятся такие люди, но в этом отношении ваш __hash__метод может быть немного улучшен. Просто используйте временную переменную при вычислении хеша, и устанавливайте ее только тогда, self._hashкогда вы получите окончательное значение. Таким образом, другой поток, получающий хэш во время вычисления первого, будет просто выполнять избыточный расчет, а не получать неправильное значение.
Джефф DQ
22
@Jeff Как правило, весь код везде не является потокобезопасным, и вы должны обернуть его вокруг некоторых структур синхронизации, чтобы безопасно использовать этот код. Кроме того, ваше особое представление о безопасности потоков опирается на атомарность назначения атрибутов объекта, что далеко не гарантировано.
Девин Жанпьер
9
@Anentropic, это совсем не так.
Майк Грэм
17
Имейте в виду: этот «FrozenDict» не обязательно заморожен. Ничто не мешает вам поместить изменяемый список в качестве значения, и в этом случае хеширование выдаст ошибку. В этом нет ничего плохого, но пользователи должны знать об этом. Другое дело: этот алгоритм хеширования выбран плохо, очень склонен к коллизиям хешей. Например, {'a': 'b'} хэширует так же, как {'b': 'a'}, а {'a': 1, 'b': 2} хэширует так же, как {'a': 2, ' б ': 1}. Лучшим выбором будет self._hash ^ = hash ((key, value))
Стив Бирнс
6
Если вы добавляете изменяемую запись в неизменяемый объект, два возможных варианта поведения - выдавать ошибку при создании объекта или выдавать ошибку при хешировании объекта. Кортежи делают последнее, Frozenset делает первое. Я определенно думаю, что вы приняли правильное решение принять последний подход, учитывая все обстоятельства. Тем не менее, я думаю, что люди могут увидеть, что FrozenDict и frozenset имеют схожие имена, и прийти к выводу, что они должны вести себя одинаково. Поэтому я думаю, что стоит предупредить людей об этой разнице. :-)
Стив Бирнс
63

Любопытно, что хотя frozensetв Python мы редко используем , все еще нет замороженных карт. Идея была отвергнута в PEP 416. - Добавить встроенный тип frozendict . Идея может быть пересмотрена в Python 3.9, см. PEP 603. Добавление типа замороженной карты в коллекции .

Итак, решение Python 2 для этого:

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

Все еще кажется несколько отстойным

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

В Python3 у вас есть возможность этого :

from types import MappingProxyType

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

def foo(config=DEFAULTS):
    ...

Теперь конфигурация по умолчанию может обновляться динамически, но оставаться неизменной там, где вы хотите, чтобы она была неизменной, передавая прокси вместо этого.

Таким образом, изменения в default_configобновлении будут обновлены, DEFAULTSкак и ожидалось, но вы не можете записать в сам прокси-объект сопоставления.

По общему признанию, это не совсем то же самое, что «неизменный, легко изменяемый диктат», - но это достойный заменитель, учитывая те же варианты использования, для которых мы могли бы хотеть заморозить.

Wim
источник
2
Есть ли конкретная причина для хранения прокси в переменной модуля? Почему не просто def foo(config=MappingProxyType({'a': 1})):? Ваш пример все еще позволяет глобальную модификацию через default_config.
jpmc26
Кроме того, я подозреваю, что двойное назначение config = default_config = {'a': 1}- это опечатка.
jpmc26
21

Если предположить, что ключи и значения словаря сами по себе неизменны (например, строки), то:

>>> 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
источник
Это хорошее, каноническое, неизменное представление диктата (исключая безумное поведение сравнения, которое портит вид).
Майк Грэм
6
@devin: согласен полностью, но я оставлю свой пост в качестве примера, что часто есть еще лучший способ.
MSW
14
Еще лучше было бы поместить его в морозилку, для которой не требуется, чтобы ключи или значения определяли согласованный порядок.
asmeurer
8
Только одна проблема с этим: у вас больше нет отображения. Это был бы весь смысл иметь замороженный диктат во-первых.
Безумный физик
2
Этот метод действительно хорош при возвращении к диктату. простоdict(t)
codythecoder
12

Нет fronzedict, но вы можете использовать MappingProxyTypeто, что было добавлено в стандартную библиотеку с 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})
Хулио Маринс
источник
с оговоркой:TypeError: can't pickle mappingproxy objects
Раду
Мне нравится идея этого. Я собираюсь дать ему попытку.
Даг
Проблема с этим MappingProxyTypeдо сих пор не решаема.
Джеб
10

Вот код, который я использовал. Я подкласс заморозил. Преимущества этого следующие.

  1. Это действительно неизменный объект. Не полагаясь на хорошее поведение будущих пользователей и разработчиков.
  2. Это легко конвертировать между обычным словарем и замороженным словарем. FrozenDict (orig_dict) -> замороженный словарь. dict (frozen_dict) -> обычный dict.

Обновление 21 января 2015: оригинальный фрагмент кода, который я разместил в 2014 году, использовал цикл for для поиска подходящего ключа. Это было невероятно медленно. Теперь я собрал реализацию, которая использует возможности хеширования frozenset. Пары ключ-значение хранятся в специальных контейнерах, где __hash__и__eq__ функции , основанные только на ключе. Этот код также был официально протестирован модульно, в отличие от того, что я разместил здесь в августе 2014 года.

Лицензия в стиле 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)
Стив Желязник
источник
1
Обратите внимание, что вы также лицензировали его в соответствии с CC BY-SA 3.0, разместив его здесь. По крайней мере, это распространенное мнение . Я полагаю, что юридическим основанием для этого является согласие с некоторыми условиями и положениями, когда вы впервые регистрируетесь.
Евгений Сергеев
1
Я сломал свой мозг, пытаясь придумать способ найти ключевой хэш без лишних слов. Переопределение хэша, Itemчтобы быть хэшем ключа - это аккуратный хак!
Клак
К сожалению, время выполнения diff(diff({key}))все еще линейно по размеру FrozenDict, в то время как обычное время доступа к dict постоянно в среднем случае.
Деннис
6

Я думаю о frozendict каждый раз, когда пишу такую ​​функцию:

def do_something(blah, optional_dict_parm=None):
    if optional_dict_parm is None:
        optional_dict_parm = {}
Марк Виссер
источник
6
Каждый раз, когда я вижу такой комментарий, я уверен, что я где-то облажался, и по умолчанию ставлю {}, а затем возвращаюсь и смотрю на мой недавно написанный код.
Райан Хиберт
1
Да, это неприятная ошибка, с которой все сталкиваются рано или поздно.
Марк Виссер
8
Более простая формулировка:optional_dict_parm = optional_dict_parm or {}
Эммануэль
2
В этом случае вы можете использовать значение по умолчанию для аргумента. types.MappingProxyType({})
GingerPlusPlus
@GingerPlusPlus Не могли бы вы написать это в качестве ответа?
Джоншарп
5

Вы можете использовать frozendictиз utilspieпакета как:

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

Согласно документу :

frozendict (dict_obj) : принимает obj типа dict и возвращает хешируемый и неизменный dict

Мойнуддин Квадри
источник
5

Установить Frozendict

pip install frozendict

Используй это!

from frozendict import frozendict

def smth(param = frozendict({})):
    pass
Андрей Корчак
источник
3

Да, это мой второй ответ, но это совершенно другой подход. Первая реализация была на чистом питоне. Этот в Cython. Если вы знаете, как использовать и компилировать модули Cython, это так же быстро, как обычный словарь. Примерно от 0,04 до 0,06 микросекунды для получения одного значения.

Это файл "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']

Вот файл "setup.py"

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

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

Если у вас установлен Cython, сохраните два вышеуказанных файла в одном каталоге. Перейдите в этот каталог в командной строке.

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

И ты должен быть готов.

Стив Желязник
источник
3

Основным недостатком namedtuple является то, что он должен быть указан перед использованием, поэтому он менее удобен для случаев одноразового использования.

Тем не менее, существует практический обходной путь, который можно использовать для обработки многих таких случаев. Допустим, вы хотите иметь неизменный эквивалент следующего слова:

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

Это можно подражать так:

from collections import namedtuple

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

Можно даже написать вспомогательную функцию для автоматизации этого:

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

Конечно, это работает только для плоских диктовок, но не должно быть слишком сложно реализовать рекурсивную версию.

Берислав Лопач
источник
1
Такая же проблема , как с другой кортежей ответ: вы должны сделать getattr(fa, x)вместо того fa[x], ни один keysметод на кончиках пальцев, и все другие причины , отображение может быть желательным.
Безумный физик
1

подклассов dict

Я вижу эту модель в дикой природе (GitHub) и хотел упомянуть об этом:

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

пример использования:

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

  • поддержка get(), keys(), items()( iteritems()на PY2) и все вкусности из dictиз коробки без явного их реализации
  • использует внутренне, dictчто означает производительность ( dictнаписано в c в CPython)
  • элегантный простой и без черной магии
  • isinstance(my_frozen_dict, dict)возвращает True - хотя python поощряет использование утилит во многих пакетах isinstance(), это может сэкономить множество настроек и настроек

Cons

  • любой подкласс может переопределить это или получить к нему внутренний доступ (вы не можете на 100% защитить что-либо в python, вы должны доверять своим пользователям и предоставлять хорошую документацию).
  • если вы заботитесь о скорости, вы можете сделать __hash__немного быстрее.
ShmulikA
источник
Я провел сравнение скорости в другом потоке, и оказалось, что переопределение __setitem__и наследование dictбезумно быстро по сравнению со многими альтернативами.
Торксед
0

Другим вариантом является MultiDictProxyкласс из multidictпакета.

Берислав Лопач
источник
1
К сожалению, это не хэш.
Роминф
0

Мне нужно было получить доступ к фиксированным ключам для чего-то, что-то вроде глобально-постоянного вида вещей, и я остановился на чем-то вроде этого:

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

Используйте это как

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

ПРЕДУПРЕЖДЕНИЕ: я не рекомендую это для большинства случаев использования, поскольку это делает некоторые довольно серьезные компромиссы.

Adverbly
источник
Следующее было бы равным по силе без недостатков производительности. Однако это просто упрощение принятого ответа ... `` `` класс FrozenDict: def __init __ (self, data): self._data = data def __getitem __ (self, key): вернуть self._data [key] `` `
Ювал
@ Юваль этот ответ не эквивалентен. Для начала API отличается, так как для инициализации нужны данные. Это также означает, что он больше не является глобально доступным. Кроме того, если _data мутировал, ваше возвращаемое значение изменяется. Я знаю, что есть существенные компромиссы - как я уже сказал, я не рекомендую это для большинства случаев использования.
Adverbly
-1

При отсутствии поддержки родного языка вы можете сделать это самостоятельно или использовать существующее решение. К счастью, Python значительно упрощает расширение их базовых реализаций.

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
efreezy
источник
Ваш класс frozen_dict не hashable
miracle173