Хешируемые словари Python

В качестве упражнения и в основном для собственного развлечения я реализую анализатор packrat с возвратом. Вдохновением для этого является то, что я хотел бы получить лучшее представление о том, как гигиенические макросы будут работать на языке, подобном алгоритму (в отличие от диалектов лиспа без синтаксиса, в которых они обычно встречаются). Из-за этого разные проходы через входные данные могут видеть разные грамматики, поэтому кешированные результаты синтаксического анализа недействительны, если я также не сохраню текущую версию грамматики вместе с кешированными результатами синтаксического анализа. ( РЕДАКТИРОВАТЬ : следствием такого использования коллекций ключ-значение является то, что они должны быть неизменяемыми, но я не собираюсь открывать интерфейс, чтобы их можно было изменить, поэтому можно использовать изменяемые или неизменяемые коллекции)

Проблема в том, что диктовки Python не могут выступать в качестве ключей к другим диктовкам. Даже использование кортежа (как я бы все равно делал) не помогает.

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

Я думаю, это должны быть кортежи до самого конца. Теперь стандартная библиотека python предоставляет примерно то, что мне нужно, collections.namedtupleимеет совершенно другой синтаксис, но может использоваться как ключ. продолжение с сеанса выше:

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

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

Изменить: дополнительная проблема с namedtuples заключается в том, что они строго позиционны. Два кортежа, которые кажутся разными, на самом деле могут быть одинаковыми:

>>> 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: Как мне получить dicts, которые можно использовать как ключи к другим dicts?

Немного поработав над ответами, вот более полное решение, которое я использую. Обратите внимание, что это делает небольшую дополнительную работу, чтобы сделать итоговые диктовки неопределенно неизменными для практических целей. Конечно, все еще довольно легко обойти это, позвонив, dict.__setitem__(instance, key, value)но мы все здесь взрослые.

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

Вот простой способ сделать хешируемый словарь. Просто помните, что не следует изменять их после вложения в другой словарь по очевидным причинам.

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

Hashables должны быть неизменными - не принудительно, но ДОВЕРЕЯ вам не изменять диктант после его первого использования в качестве ключа, следующий подход будет работать:

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

Если вам ДЕЙСТВИТЕЛЬНО нужно видоизменить свои диктовки, а они ВСЕ ЕЩЕ хотите использовать их в качестве ключей, сложность взрывается стократно - не сказать, что это невозможно, но я подожду ОЧЕНЬ конкретного указания, прежде чем попаду в ЭТО невероятное болото! -)

Все, что нужно, чтобы словари можно было использовать в ваших целях, - это добавить метод __hash__:

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

Обратите внимание, что преобразование frozenset будет работать для всех словарей (т. Е. Не требует сортировки ключей). Точно так же нет ограничений на значения словаря.

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

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

Это быстрее, чем frozenset(self.iteritems())по двум причинам. Во-первых, на этом frozenset(self)этапе повторно используются хеш-значения, хранящиеся в словаре, сохраняя ненужные вызовы в hash(key). Во-вторых, использование itervalues обеспечивает прямой доступ к значениям и избегает множества вызовов распределителя памяти, используемых элементами для формирования новых множественных кортежей ключ / значение в памяти каждый раз, когда вы выполняете поиск.

Приведенные ответы нормальные, но их можно улучшить, используя frozenset(...)вместо tuple(sorted(...))генерации хэша:

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

Преимущество в производительности зависит от содержимого словаря, но в большинстве случаев, которые я тестировал, хеширование с помощью frozensetвыполняется как минимум в 2 раза быстрее (в основном потому, что сортировка не требуется).

Достаточно чистая и простая реализация:

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

Я все время возвращаюсь к этой теме ... Вот еще одна вариация. Мне непросто dictсоздать подкласс для добавления __hash__метода; Практически нет выхода из проблемы, что dict изменчивы, и вера в то, что они не изменятся, кажется слабой идеей. Вместо этого я рассмотрел создание сопоставления на основе встроенного типа, который сам по себе является неизменяемым. хотя tupleэто очевидный выбор, доступ к значениям в нем подразумевает сортировку и разделение пополам; не проблема, но похоже, что он не использует большую часть мощности того типа, на котором он построен.

Что, если вы вставите пары ключ-значение в frozenset? Что для этого потребуется, как это будет работать?

Часть 1, вам нужен способ кодирования элементов таким образом, чтобы Frozenset обрабатывал их в основном своими ключами; Я сделаю для этого небольшой подкласс.

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

Уже одно это ставит вас на грань неизменного отображения:

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

Ооо! К сожалению, когда вы используете операторы набора, элементы равны, но не являются одним и тем же объектом; которое заканчивается в возвращаемом значении, не определено , нам придется пройти еще несколько циклов.

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

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

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

Что приводит к менее проблемным:

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

В этом вся глубокая магия; остальное превращает все это во что-то, имеющее интерфейс, подобный dict. Поскольку мы являемся подклассом от frozenset, у которого совершенно другой интерфейс, существует довольно много методов; мы получаем небольшую помощь collections.Mapping, но большая часть работы заключается в замене frozensetметодов для версий, которые работают как dicts, а не:

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)

что, в конечном счете, действительно отвечает на мой собственный вопрос:

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

Принятый ответ @Unknown, а также ответ @AlexMartelli работают отлично, но только при следующих ограничениях:

1. Значения словаря должны быть хешируемыми. Например, hash(hashabledict({'a':[1,2]}))повысит TypeError.
2. Ключи должны поддерживать операцию сравнения. Например, hash(hashabledict({'a':'a', 1:1}))повысит TypeError.
3. Оператор сравнения ключей устанавливает полный порядок. Например, если два ключа в словаре - frozenset((1,2,3))и frozenset((4,5,6)), их сравнение неравно в обоих направлениях. Следовательно, сортировка элементов словаря с такими ключами может привести к произвольному порядку и, следовательно, нарушит правило, согласно которому одинаковые объекты должны иметь одинаковое хеш-значение.

Гораздо более быстрый ответ @ObenSonne снимает ограничения 2 и 3, но по-прежнему ограничивается ограничением 1 (значения должны быть хешируемыми).

Более быстрый, но ответ @RaymondHettinger снимает все 3 ограничения, потому что он не учитывается .values()при вычислении хэша. Однако его производительность хороша только в том случае, если:

4. Большинство (не равных) словарей, которые необходимо хешировать, не идентичны .keys().

Если это условие не выполняется, хеш-функция будет по-прежнему действительна, но может вызвать слишком много конфликтов. Например, в крайнем случае, когда все словари созданы из шаблона веб-сайта (имена полей как ключи, пользовательский ввод как значения), ключи всегда будут одинаковыми, а хеш-функция вернет одно и то же значение для всех входных данных. . В результате хеш-таблица, которая полагается на такую ​​хеш-функцию, будет работать медленнее, чем список, при получении элемента ( O(N)вместо O(1)).

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

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

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

Вы также можете добавить эти два метода, чтобы протокол травления v2 работал с экземплярами hashdict. В противном случае cPickle попытается использовать hashdict .____ setitem____, что приведет к ошибке TypeError. Интересно, что с двумя другими версиями протокола ваш код работает нормально.

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

Если вы не помещаете числа в словарь и никогда не теряете переменные, содержащие ваши словари, вы можете сделать это:

cache[id(rule)] = "whatever"

поскольку id () уникален для каждого словаря

РЕДАКТИРОВАТЬ:

Ой, извините, да, в таком случае то, что сказали другие парни, было бы лучше. Я думаю, вы также можете сериализовать свои словари в виде строки, например

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

Если вам нужно восстановить словари с ключей, тогда вам придется сделать что-то более уродливое, например

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

Думаю, преимущество этого в том, что вам не придется писать столько кода.