Table de hachage bidirectionnelle efficace en Python?

Question

Python dict est une structure de données très utile:

d = {'a': 1, 'b': 2} 

d['a'] # get 1 

Parfois, vous souhaitez également l'indice des valeurs.

d[1] # get 'a' 

Quelle est la manière la plus efficace d'implémenter cette infrastructure de données? Un moyen officiel recommande de le faire?

Merci!

Answer 1

La table de hachage bidirectionnelle d'un pauvre serait d'utiliser seulement deux dictionnaires (ce sont déjà des structures de données fortement accordées).

Il y a aussi un paquet bidict sur l'indice:

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

La source de bidict se trouve sur github:

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

Answer 2

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 bousculée par une paire ultérieure que vous avez insérée. J'ai mis en place un choix possible.

---

Exemple:

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

Answer 3

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

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

Answer 4

Voici une classe pour un dict bidirectionnel, inspiré par Finding key from value in Python dictionary et modifié pour permettre la suite 2) et 3).

Notez que:

• 1) Le répertoire inverse bd.inverse mises à jour automatiques lui-même lorsque la norme dict bd est modifié
• 2) Le répertoire inverse bd.inverse[value] est toujours une liste de key tel que bd[key] == value
• 3) Contrairement au module bidict de https://pypi.python.org/pypi/bidict, ici nous pouvons avoir 2 clés 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'utilisation:

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']} 

Answer 5

L'extrait ci-dessous du code implémente un inversible (bijective) Carte:

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

Answer 6

D'abord, vous devez vous assurer que la clé de la cartographie de la valeur est une à une, sinon, il est impossible de construire une carte bi-directionnel.

Deuxièmement, quelle est la taille de l'ensemble de données? S'il n'y a pas beaucoup de données, utilisez simplement deux cartes distinctes et mettez-les à jour toutes les deux lors de la mise à jour. Ou mieux, utiliser une solution existante comme Bidict, qui est juste une enveloppe de 2 dicts, avec la mise à jour/suppression construite en

Mais si l'ensemble de données est grande, et le maintien de 2 dicts est pas souhaitable.

• Si la clé et la valeur sont numériques, considérez la possibilité d'utiliser Interpolation pour approximer le mappage. Si la grande majorité des paires valeur/clé peut être couverte par la fonction de mappage (et sa fonction inverse
  ), il vous suffit d'enregistrer les valeurs aberrantes dans les mappes.

• Si la plupart d'accès est unidirectionnel (valeur key->), il est tout à fait ok pour construire la carte inverse progressivement, au commerce du 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]