Dicts hachables Python

Question

A titre d'exercice, et surtout pour mon propre amusement, j'implémente un analyseur packrat 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 hygeniques fonctionneraient dans un langage de type algol (par opposition aux dialectes lisp sans syntaxe dans lesquels on les trouve normalement). A cause de cela, différentes passes à travers l'entrée peuvent voir différentes grammaires, donc les résultats de l'analyse en cache sont invalides, à moins que je ne stocke également la version actuelle de la grammaire avec les résultats de l'analyse en cache. ( EDITAR une conséquence de cette utilisation de collections de valeurs-clés est qu'elles doivent ê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 parfaitement).

Le problème est que les dicts python ne peuvent pas apparaître comme des clés d'autres dicts. Même l'utilisation d'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 ça doit être des tuples tout du long. La bibliothèque standard de Python fournit approximativement ce dont j'ai besoin, collections.namedtuple a une syntaxe très différente, mais peut être utilisé comme une clé, en continuant la session précédente :

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

Ok. 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, donc cette classe peut être définie en même temps que la fonction qui analyse la règle.

Edit : Un problème supplémentaire avec namedtuple 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 puis-je obtenir dict qui peuvent être utilisés comme clés pour d'autres dict s ?

Après avoir piraté un peu les réponses, voici la solution plus complète que j'utilise. Notez que cela fait un peu de travail supplémentaire pour rendre les dicts résultants vaguement immuables pour des raisons pratiques. Bien sûr, il est toujours très facile de contourner ce problème 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()

Answer 1

Voici la manière 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())))

Answer 2

Les variables de hachage doivent être immuables - sans l'imposer, mais en vous faisant confiance pour ne pas modifier 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 faire muter vos dicts et que vous voulez TOUJOURS les utiliser comme clés, la complexité explose au centuple -- je ne dis pas que c'est impossible, mais j'attendrai une indication TRES spécifique avant de me lancer dans cet incroyable bourbier !-)

Answer 3

Pour que les dictionnaires soient utilisables dans votre cas, il suffit d'ajouter une méthode __hash__ :

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

Remarque, le frozenset fonctionnera pour tous les dictionnaires (c'est-à-dire qu'il n'est pas nécessaire 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 des valeurs distinctes, il est nécessaire que le hachage prenne en compte les valeurs. La façon la plus rapide de le faire est la suivante :

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

C'est plus rapide que frozenset(self.iteritems()) pour deux raisons. Premièrement, le frozenset(self) réutilise les valeurs de hachage stockées dans le dictionnaire, ce qui permet d'éviter les appels inutiles à la fonction hash(key) . Deuxièmement, en utilisant itervalues accèdera directement aux valeurs et évitera les nombreux appels à l'allocateur de mémoire utilisé par articles pour former de nouveaux tuples clé/valeur en mémoire à chaque fois que vous effectuez une recherche.

Answer 4

Les réponses données sont correctes, mais elles pourraient être améliorées en utilisant les éléments suivants 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 frozenset est au moins deux fois plus rapide (principalement parce qu'elle n'a pas besoin de trier).

Answer 5

Une mise en œuvre raisonnablement propre et directe est la suivante

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