tablas - ¿Tabla hash bidireccional eficiente en Python?

tabla hash implementacion

Question

Esta pregunta ya tiene una respuesta aquí:

• Two way / reverse map 12 respuestas

Python dict es una estructura de datos muy útil:

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

d[''a''] # get 1

A veces también te gustaría indexar por valores.

d[1] # get ''a''

¿Cuál es la forma más eficiente de implementar esta estructura de datos? ¿Alguna forma oficial recomendada para hacerlo?

¡Gracias!

Answer 1

Algo como esto, tal vez:

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

Debe decidir qué quiere que suceda si más de una clave tiene un valor determinado; la bidireccionalidad de un par determinado podría ser golpeada fácilmente por algún par posterior que hayas insertado. Implementé una posible elección.

Ejemplo:

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

Answer 2

Aquí hay una clase para un dict bidireccional, inspirado en la búsqueda de la clave del valor en el diccionario Python y modificado para permitir lo siguiente 2) y 3).

Tenga en cuenta que :

• 1) El directorio inverso bd.inverse actualiza automáticamente cuando se modifica el dict bd estándar
• 2) El directorio inverso bd.inverse[value] es siempre una lista de key tal que bd[key] == value
• 3) A diferencia del módulo bidict de https://pypi.python.org/pypi/bidict , aquí podemos tener 2 claves con el mismo valor, esto es muy importante .

Código:

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)

Ejemplo de uso:

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 3

El siguiente fragmento de código implementa un mapa invertible (bijective):

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)

La ventaja de esta implementación es que el atributo inverse de un BijectiveMap es nuevamente un BijectiveMap . Por lo tanto, puedes hacer cosas como:

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

Answer 4

En primer lugar, debe asegurarse de que la clave para la asignación de valores sea uno a uno; de lo contrario, no es posible construir un mapa bidireccional.

En segundo lugar, ¿qué tan grande es el conjunto de datos? Si no hay mucha información, simplemente use 2 mapas separados y actualícelos al actualizar. O mejor, use una solución existente como https://github.com/jab/bidict , que es solo un contenedor de 2 dicts, con actualización / eliminación incorporada.

Pero si el conjunto de datos es grande, y mantener 2 dicts no es deseable:

• Si tanto la clave como el valor son numéricos, considere la posibilidad de usar Interpolación para aproximar la asignación. Si la gran mayoría de los pares clave-valor pueden ser cubiertos por la función de mapeo (y su
  función inversa), entonces solo necesita registrar los valores atípicos en los mapas.

• Si la mayor parte del acceso es unidireccional (clave-> valor), entonces está totalmente bien construir el mapa inverso incrementalmente, para intercambiar tiempo por
  espacio.

Código:

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]

Answer 5

La tabla de hash bidireccional de un pobre sería usar solo dos diccionarios (estas son estructuras de datos altamente ajustadas).

También hay un paquete https://pypi.python.org/pypi/bidict en el índice:

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

La fuente para bidict se puede encontrar en github:

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

Answer 6

Puede usar la misma dicción añadiendo clave, par de valores en orden inverso.

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