Dicts hachables en Python

En tant qu'exercice, et surtout pour mon propre amusement, j'implémente un analyseur de paquets de retour en arrière. L'inspiration pour cela est que j'aimerais avoir une meilleure idée de la façon dont les macros hygiéniques fonctionneraient dans un langage de type algol (comme associé aux dialectes lisp sans syntaxe dans lesquels vous les trouvez normalement). Pour cette raison, différentes passes dans l'entrée peuvent voir des grammaires différentes, donc les résultats d'analyse mis en cache ne sont pas valides, sauf si je stocke également la version actuelle de la grammaire avec les résultats d'analyse mis en cache. ( EDIT : une conséquence de cette utilisation des collections clé-valeur est qu'elles devraient être immuables, mais je n'ai pas l'intention d'exposer l'interface pour leur permettre d'être modifiées, donc les collections mutables ou immuables conviennent)

Le problème est que les dictionnaires python ne peuvent pas apparaître comme des clés d'autres dictionnaires. Même utiliser un tuple (comme je le ferais de toute façon) n'aide pas.

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

Je suppose que ce doit être des tuples tout en bas. Maintenant, la bibliothèque standard python fournit approximativement ce dont j'aurais besoin, collections.namedtuplea une syntaxe très différente, mais peut être utilisée comme clé. suite de la session ci-dessus:

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

D'accord. Mais je dois créer une classe pour chaque combinaison possible de clés dans la règle que je voudrais utiliser, ce qui n'est pas si mal, car chaque règle d'analyse sait exactement quels paramètres elle utilise, afin que cette classe puisse être définie en même temps comme fonction qui analyse la règle.

Edit: Un problème supplémentaire avec les namedtuples est qu'ils sont strictement positionnels. Deux tuples qui semblent devoir être différents peuvent en fait être identiques:

>>> 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: Comment obtenir des dicts qui peuvent être utilisés comme clés pour d'autres dicts?

Après avoir piraté un peu les réponses, voici la solution la plus complète que j'utilise. Notez que cela fait un peu plus de travail pour rendre les dictats résultants vaguement immuables à des fins pratiques. Bien sûr, il est toujours assez facile de pirater en appelant, dict.__setitem__(instance, key, value)mais nous sommes tous des adultes ici.

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

Voici le moyen le plus simple de créer un dictionnaire hachable. N'oubliez pas de ne pas les muter après les avoir intégrés dans un autre dictionnaire pour des raisons évidentes.

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

Les hashables doivent être immuables - ne pas appliquer cela mais VOUS CONFIANT de ne pas muter un dict après sa première utilisation comme clé, l'approche suivante fonctionnerait:

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 vous avez besoin de muter vos dictés et que vous voulez TOUJOURS les utiliser comme clés, la complexité explose au centuple - pour ne pas dire que cela ne peut pas être fait, mais j'attendrai une indication TRÈS spécifique avant de me lancer dans CET incroyable marais! -)

Tout ce qui est nécessaire pour rendre les dictionnaires utilisables pour votre objectif est d'ajouter une méthode __hash__:

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

Noter la conversion de frozenset fonctionnera pour tous les dictionnaires (c'est-à-dire qu'elle ne nécessite pas que les clés soient triables). De même, il n'y a aucune restriction sur les valeurs du dictionnaire.

S'il existe de nombreux dictionnaires avec des clés identiques mais avec des valeurs distinctes, il est nécessaire que le hachage prenne en compte les valeurs. Le moyen le plus rapide d'y parvenir est:

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

C'est plus rapide que frozenset(self.iteritems())pour deux raisons. Tout d'abord, l' frozenset(self)étape réutilise les valeurs de hachage stockées dans le dictionnaire, en économisant les appels inutiles à hash(key). Deuxièmement, l'utilisation d' itervalues ​​accédera directement aux valeurs et évitera les nombreux appels d'allocateur de mémoire utilisant by items pour former de nouveaux nombreux tuples clé / valeur en mémoire chaque fois que vous effectuez une recherche.

Les réponses données sont correctes, mais elles pourraient être améliorées en utilisant frozenset(...)au lieu de tuple(sorted(...))pour générer le hachage:

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

L'avantage en termes de performances dépend du contenu du dictionnaire, mais dans la plupart des cas que j'ai testés, le hachage avec frozensetest au moins 2 fois plus rapide (principalement parce qu'il n'a pas besoin de trier).

Une implémentation raisonnablement propre et simple est

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

Je reviens sans cesse sur ce sujet ... Voici une autre variante. Je ne suis pas à l'aise avec le sous-classement dictpour ajouter une __hash__méthode; Il n'y a pratiquement pas d'échappatoire au problème que les dict sont mutables, et espérer qu'ils ne changeront pas semble être une idée faible. J'ai donc plutôt cherché à créer un mappage basé sur un type intégré qui est lui-même immuable. bien que ce tuplesoit un choix évident, y accéder aux valeurs implique un tri et une bissectrice; ce n'est pas un problème, mais il ne semble pas exploiter une grande partie de la puissance du type sur lequel il est construit.

Que faire si vous bloquez la clé, la valeur des paires dans un frozenset? Qu'est-ce que cela exigerait, comment cela fonctionnerait-il?

Dans la première partie, vous avez besoin d'un moyen d'encoder les «éléments» de telle sorte qu'un frozenset les traite principalement par leurs clés; Je vais faire une petite sous-classe pour cela.

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

Cela seul vous met à l'écart d'une cartographie immuable:

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

Oh! Malheureusement, lorsque vous utilisez les opérateurs set et les éléments sont égaux mais pas le même objet; celui qui se termine dans la valeur de retour n'est pas défini , nous devrons passer par d'autres girations.

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

Cependant, rechercher les valeurs de cette manière est fastidieux et, pire, crée de nombreux ensembles intermédiaires; ça ne va pas! Nous allons créer une `` fausse '' paire valeur / clé pour la contourner:

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

Ce qui se traduit par le moins problématique:

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

C'est toute la magie profonde; le reste englobe tout cela dans quelque chose qui a une interface comme un dict. Puisque nous sous-classons defrozenset , qui a une interface très différente, il y a pas mal de méthodes; nous obtenons un peu d'aide collections.Mapping, mais la plupart du travail remplace les frozensetméthodes pour les versions qui fonctionnent comme des dictionnaires, à la place:

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)

qui, en fin de compte, répond à ma propre question:

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

La réponse acceptée par @Unknown, ainsi que la réponse de @AlexMartelli fonctionnent parfaitement bien, mais uniquement sous les contraintes suivantes:

1. Les valeurs du dictionnaire doivent être hachables. Par exemple,hash(hashabledict({'a':[1,2]})) augmentera TypeError.
2. Les clés doivent prendre en charge l'opération de comparaison. Par exemple,hash(hashabledict({'a':'a', 1:1})) augmenteraTypeError .
3. L'opérateur de comparaison sur les clés impose un ordre total. Par exemple, si les deux clés d'un dictionnaire sont frozenset((1,2,3))et frozenset((4,5,6)), elles se comparent de manière inégale dans les deux sens. Par conséquent, le tri des éléments d'un dictionnaire avec de telles clés peut entraîner un ordre arbitraire et violera par conséquent la règle selon laquelle les objets égaux doivent avoir la même valeur de hachage.

La réponse beaucoup plus rapide de @ObenSonne lève les contraintes 2 et 3, mais est toujours liée par la contrainte 1 (les valeurs doivent être hachables).

La réponse plus rapide encore de @RaymondHettinger lève les 3 contraintes car elle n'inclut pas .values() dans le calcul de hachage. Cependant, ses performances ne sont bonnes que si:

4. La plupart des dictionnaires (non égaux) qui doivent être hachés ne sont pas identiques .keys() .

Si cette condition n'est pas satisfaite, la fonction de hachage sera toujours valide, mais peut provoquer trop de collisions. Par exemple, dans le cas extrême où tous les dictionnaires sont générés à partir d'un modèle de site Web (noms de champs en tant que clés, entrées de l'utilisateur en tant que valeurs), les clés seront toujours les mêmes et la fonction de hachage renverra la même valeur pour toutes les entrées . En conséquence, une table de hachage qui repose sur une telle fonction de hachage deviendra aussi lente qu'une liste lors de la récupération d'un élément ( O(N)au lieu de O(1)).

Je pense que la solution suivante fonctionnera raisonnablement bien même si les 4 contraintes énumérées ci-dessus sont violées. Il présente un avantage supplémentaire: il peut hacher non seulement des dictionnaires, mais tous les conteneurs, même s'ils ont des conteneurs mutables imbriqués.

J'apprécierais beaucoup vos commentaires à ce sujet, car je n'ai testé cela que légèrement jusqu'à présent.

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

Vous pouvez également ajouter ces deux méthodes pour que le protocole de décapage v2 fonctionne avec les instances de hashdict. Sinon, cPickle essaiera d'utiliser hashdict .____ setitem____ résultant en une TypeError. Fait intéressant, avec les deux autres versions du protocole, votre code fonctionne très bien.

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

Si vous ne mettez pas de nombres dans le dictionnaire et que vous ne perdez jamais les variables contenant vos dictionnaires, vous pouvez faire ceci:

cache[id(rule)] = "whatever"

puisque id () est unique pour chaque dictionnaire

ÉDITER:

Oh désolé, ouais dans ce cas ce que les autres gars ont dit serait mieux. Je pense que vous pouvez également sérialiser vos dictionnaires sous forme de chaîne, comme

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

Si vous avez besoin de récupérer vos dictionnaires à partir des clés, vous devrez faire quelque chose de plus laid comme

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

J'imagine que l'avantage de ceci est que vous n'auriez pas à écrire autant de code.