Une table de hachage bidirectionnelle efficace en Python? [dupliquer]

Voici une classe pour un bidirectionnel dict , inspiré par trouver la clé de valeur dans le dictionnaire Python et modifié pour permettre les 2) et 3) suivants.

noter que:

• 1) Le répertoire inverse bd.inverse auto-mises à jour lorsque le dict standard bd est modifié
• 2) le répertoire inverse bd.inverse[value] est toujours un liste de key tels que bd[key] == value
• 3) contrairement au module bidict de https://pypi.python.org/pypi/bidict , ici nous pouvons avoir 2 touches ayant la même valeur, c'est très important .

Code:

class bidict(dict):
    def __init__(self, *args, **kwargs):
        super(bidict, self).__init__(*args, **kwargs)
        self.inverse = {}
        for key, value in self.iteritems():
            self.inverse.setdefault(value,[]).append(key) 

    def __setitem__(self, key, value):
        if key in self:
            self.inverse[self[key]].remove(key) 
        super(bidict, self).__setitem__(key, value)
        self.inverse.setdefault(value,[]).append(key)        

    def __delitem__(self, key):
        self.inverse.setdefault(self[key],[]).remove(key)
        if self[key] in self.inverse and not self.inverse[self[key]]: 
            del self.inverse[self[key]]
        super(bidict, self).__delitem__(key)

exemple D'Usage:

bd = bidict({'a': 1, 'b': 2})  
print bd                     # {'a': 1, 'b': 2}                 
print bd.inverse             # {1: ['a'], 2: ['b']}
bd['c'] = 1               # Now two keys have the same value (= 1)
print bd                     # {'a': 1, 'c': 1, 'b': 2}
print bd.inverse             # {1: ['a', 'c'], 2: ['b']}
del bd['c']
print bd                     # {'a': 1, 'b': 2}
print bd.inverse             # {1: ['a'], 2: ['b']}
del bd['a']
print bd                     # {'b': 2}
print bd.inverse             # {2: ['b']}
bd['b'] = 3
print bd                     # {'b': 3}
print bd.inverse             # {2: [], 3: ['b']}

vous pouvez utiliser le même dict lui-même en ajoutant clé,paire de valeur dans l'ordre inverse.

d={'a':1,'b':2}
revd=dict([reversed(i) for i in d.items()])
d.update(revd)

la table de hachage bidirectionnelle d'un pauvre homme n'utiliserait que deux dictionnaires (ce sont déjà des structures de données très précises).

Il ya aussi un bidict Paquet sur l'index:

• https://pypi.python.org/pypi/bidict

la source de bidict se trouve sur GitHub:

• https://github.com/jab/bidict

quelque chose comme ça, peut-être:

import itertools

class BidirDict(dict):
    def __init__(self, iterable=(), **kwargs):
        self.update(iterable, **kwargs)
    def update(self, iterable=(), **kwargs):
        if hasattr(iterable, 'iteritems'):
            iterable = iterable.iteritems()
        for (key, value) in itertools.chain(iterable, kwargs.iteritems()):
            self[key] = value
    def __setitem__(self, key, value):
        if key in self:
            del self[key]
        if value in self:
            del self[value]
        dict.__setitem__(self, key, value)
        dict.__setitem__(self, value, key)
    def __delitem__(self, key):
        value = self[key]
        dict.__delitem__(self, key)
        dict.__delitem__(self, value)
    def __repr__(self):
        return '%s(%s)' % (type(self).__name__, dict.__repr__(self))

vous devez décider ce que vous voulez arriver si plus d'une clé a une valeur donnée; la bidirectionnalité d'une paire donnée pourrait facilement être assommée par une paire ultérieure que vous avez insérée. J'ai mis en œuvre un choix possible.

exemple:

bd = BidirDict({'a': 'myvalue1', 'b': 'myvalue2', 'c': 'myvalue2'})
print bd['myvalue1']   # a
print bd['myvalue2']   # b        

l'extrait de code ci-dessous met en œuvre une carte (bijective) inversible:

class BijectionError(Exception):
    """Must set a unique value in a BijectiveMap."""

    def __init__(self, value):
        self.value = value
        msg = 'The value "{}" is already in the mapping.'
        super().__init__(msg.format(value))


class BijectiveMap(dict):
    """Invertible map."""

    def __init__(self, inverse=None):
        if inverse is None:
            inverse = self.__class__(inverse=self)
        self.inverse = inverse

    def __setitem__(self, key, value):
        if value in self.inverse:
            raise BijectionError(value)

        self.inverse._set_item(value, key)
        self._set_item(key, value)

    def __delitem__(self, key):
        self.inverse._del_item(self[key])
        self._del_item(key)

    def _del_item(self, key):
        super().__delitem__(key)

    def _set_item(self, key, value):
        super().__setitem__(key, value)

l'avantage de cette implémentation est que l'attribut inverse d'un BijectiveMap est de nouveau un BijectiveMap . Par conséquent, vous pouvez faire des choses comme:

>>> foo = BijectiveMap()
>>> foo['steve'] = 42
>>> foo.inverse
{42: 'steve'}
>>> foo.inverse.inverse
{'steve': 42}
>>> foo.inverse.inverse is foo
True

tout d'abord, vous devez vous assurer que la clé de la cartographie des valeurs est une à une, sinon, il n'est pas possible de construire une carte bidirectionnelle.

Deuxièmement, Quelle est la taille de l'ensemble de données? S'il n'y a pas beaucoup de données, il suffit d'utiliser 2 cartes séparées et de les mettre à jour toutes les deux lors de la mise à jour. Ou mieux, utilisez une solution existante comme Bidict , qui est juste une enveloppe de 2 dicts, avec mise à jour/suppression intégrée.

mais si l'ensemble de données est grand, et maintenir 2 dicts n'est pas souhaitable:

• si la clé et la valeur sont numériques, envisager la possibilité d'utiliser Interpolation pour approximation de la cartographie. Si la grande majorité de la les paires de valeurs clés peuvent être couvertes par la fonction de cartographie (et ses
  
  fonction d'inversion), alors vous n'avez qu'à enregistrer les valeurs aberrantes dans les cartes.

• si la plupart des accès sont unidirectionnels (la clé->valeur), alors il est totalement ok pour construire la carte inverse progressivement, pour échanger le temps pour
  
  espace.

Code:

d = {1: "one", 2: "two" }
reverse = {}

def get_key_by_value(v):
    if v not in reverse:
        for _k, _v in d.items():
           if _v == v:
               reverse[_v] = _k
               break
    return reverse[v]