2009-05-14 26 views
28

Tengo un problema que requiere un mapeo 1: 1 reversible de las claves de los valores.¿Una estructura de datos para mapeos 1: 1 en python?

Eso significa que a veces quiero encontrar el valor dado a una clave, pero en otras ocasiones quiero encontrar la clave dada el valor. Tanto las claves como los valores son únicos.

x = D[y] 
y == D.inverse[x] 

La solución obvia es simplemente invertir el diccionario cada vez que quiero una búsqueda inversa: La inversión de un diccionario es muy fácil, there's a recipe here but for a large dictionary it can be very slow.

La otra alternativa es crear una nueva clase que una dos diccionarios, uno para cada tipo de búsqueda. Eso probablemente sea rápido, pero usaría el doble de memoria que un solo dict.

¿Existe una mejor estructura que pueda usar?

  • Mi aplicación requiere que esto sea muy rápido y utilice la menor cantidad de memoria posible.
  • La estructura debe ser mutable, y es muy conveniente que la mutación del objeto no lo haga más lento (por ejemplo, forzar un re-índice completo)
  • Podemos garantizar que la clave o el valor (o ambos)) será un número entero
  • Es probable que la estructura sea necesaria para almacenar miles o posiblemente millones de elementos.
  • Keys & Valus se garantiza que sea único, es decir, len (conjunto (x)) == len (x) para x en [d.keys(), D.valuies()]
+0

¿Qué tan grande es este diccionario? ¿Estás seguro de que dos copias no caben en la memoria? –

Respuesta

11
class TwoWay: 
    def __init__(self): 
     self.d = {} 
    def add(self, k, v): 
     self.d[k] = v 
     self.d[v] = k 
    def remove(self, k): 
     self.d.pop(self.d.pop(k)) 
    def get(self, k): 
     return self.d[k] 
+1

Esta clase falla en este ejemplo: '{1: 2, 2: 4}' Se debe implementar un método inverso, en mi humilde opinión. –

5

La otra alternativa es crear una nueva clase que combine dos diccionarios, uno para cada tipo de búsqueda. Eso probablemente usaría el doble de memoria que un solo dict.

No realmente, ya que solo mantendrían dos referencias a los mismos datos. En mi opinión, esta no es una mala solución.

¿Ha considerado una búsqueda en la base de datos en memoria? No estoy seguro de cómo se comparará en velocidad, pero las búsquedas en bases de datos relacionales pueden ser muy muy rápido.

+0

¡La clase de 2 dictos es la mejor hasta ahora! –

1

Suponiendo que tiene una clave con la que busca un objeto mutable más complejo, simplemente convierta la clave en una propiedad de ese objeto. Parece que es mejor que pienses un poco sobre el modelo de datos.

+0

En este caso no puedo - los objetos de un lado son numpy.int64s - el propósito de la aplicación es adaptar una clase de teoría de grafos numérica muy austera a algo que parece más naturalmente pitónico. –

+0

En ese caso, un peso mosca haría. –

26

La otra alternativa es hacer una nueva clase que une dos diccionarios, uno para cada tipo de búsqueda. Es muy probable que sea rápido, pero consumirá el doble de memoria que un solo dict .

Realmente no. ¿Has medido eso? Como ambos diccionarios utilizarían referencias a los mismos objetos como claves y valores, la memoria gastada sería solo la estructura del diccionario. Eso es mucho menos que dos veces y es un valor fijo independientemente de su tamaño de datos.

Lo que quiero decir es que los datos reales no se copiarán. Entonces gastarías poca memoria extra.

Ejemplo:

a = "some really really big text spending a lot of memory" 

number_to_text = {1: a} 
text_to_number = {a: 1} 

Sólo existe una única copia de la cadena "muy grande", por lo que termina gastando sólo un poco más de memoria. Eso es generalmente asequible.

No me puedo imaginar una solución en la que tendría la velocidad de clave de búsqueda cuando se busca por valor, si no pasas al menos memoria suficiente para almacenar una tabla de búsqueda inversa de hash (que es exactamente lo que se está hecho en su solución "unite two dict s").

+2

Creo que esta es una buena solución. Sin embargo, estaría duplicando la sobrecarga de mantener un dict (memoria y computación) porque ahora hay dos. Sospecho que esta sobrecarga sería pequeña en comparación con el resto del problema. – Doug

+1

@Doug: está intercambiando los gastos generales de mantenimiento de un segundo dict, por la velocidad de cerca de O (1) búsquedas en él. No puedo ver otro enfoque que no duplique el esfuerzo. – nosklo

+2

@Doug & nosklo: Solo quiero enfatizar el punto de nosklo. Este problema es un ejemplo * clásico * de la compensación entre tiempo y espacio. Si desea garantizar búsquedas rápidas en ambos extremos, debe mantener ambos diccionarios. El segundo diccionario es el precio que paga por búsquedas inversas. Si la sobrecarga de espacio es demasiado, será necesaria una solución más lenta. La única manera de hacer una búsqueda inversa rápida es si * algo * de tipo de información se mantiene para hacerlo ... – Tom

1

"Podemos garantizar que sea la clave o el valor (o ambos) será un número entero"

Eso es extrañamente escrito - "clave o el valor (o ambos)" no se siente bien. O bien son enteros o no son enteros.

Parece que todos son enteros.

O, parece que está pensando en reemplazar el objeto de destino por un valor entero, por lo que solo tiene una copia referenciada por un entero. Esta es una economía falsa. Solo mantén el objeto de destino. Todos los objetos de Python son, en efecto, referencias. Se realiza muy poca copia real.

Imaginemos que simplemente tiene dos enteros y puede hacer una búsqueda en cualquiera de los pares. Una forma de hacerlo es utilizar colas de montón o el módulo de bisección para mantener listas ordenadas de tuplas de valor-clave enteras.

Ver http://docs.python.org/library/heapq.html#module-heapq

Ver http://docs.python.org/library/bisect.html#module-bisect

Tiene uno heapq (key,value) tuplas. O bien, si su objeto subyacente es más complejo, el (key,object) tuplas.

Tiene otras tuplas de heapq (value,key). O bien, si su objeto subyacente es más complejo, (otherkey,object) tuplas.

Una "inserción" se convierte en dos inserciones, una para cada lista de estructura heapq.

Una búsqueda de teclas está en una fila; una búsqueda de valor está en la otra cola. Haga las búsquedas usando bisect(list,item).

+1

Era una afirmación bastante clara: al menos uno de los elementos en cada par clave/valor será un número entero y, a veces, ambos serán números enteros. –

+0

¿Por qué la declaración de ronda? ¿Por qué no una lista positiva de qué tipos de datos están involucrados? La lógica puede ser clara, pero es inútil para el diseño de algoritmos. El "cualquiera-o" suele ser un exclusivo o. Pero el "o ambos" significa que es inclusivo o. Lo que significa que CUALQUIER combinación de tipos (excepto 2 no enteros) sería válida. Haciéndolo difícil de optimizar. –

0

Sucede que me hago esta pregunta todo el tiempo (ayer en particular). Estoy de acuerdo con el enfoque de hacer dos diccionarios. Haga una evaluación comparativa para ver cuánta memoria está tomando. Nunca he necesitado que sea mutable, pero así es como lo resumen, si sirve de algo:

class BiDict(list): 
    def __init__(self,*pairs): 
     super(list,self).__init__(pairs) 
     self._first_access = {} 
     self._second_access = {} 
     for pair in pairs: 
      self._first_access[pair[0]] = pair[1] 
      self._second_access[pair[1]] = pair[0] 
      self.append(pair) 

    def _get_by_first(self,key): 
     return self._first_access[key] 

    def _get_by_second(self,key): 
     return self._second_access[key] 

    # You'll have to do some overrides to make it mutable 
    # Methods such as append, __add__, __del__, __iadd__ 
    # to name a few will have to maintain ._*_access 

class Constants(BiDict): 
    # An implementation expecting an integer and a string 
    get_by_name = BiDict._get_by_second 
    get_by_number = BiDict._get_by_first 

t = Constants(
     (1, 'foo'), 
     (5, 'bar'), 
     (8, 'baz'), 
    ) 

>>> print t.get_by_number(5) 
bar 
>>> print t.get_by_name('baz') 
8 
>>> print t 
[(1, 'foo'), (5, 'bar'), (8, 'baz')] 
1

¿Qué le parece usar sqlite? Simplemente cree una: memoria: base de datos con una tabla de dos columnas. Incluso puede agregar índices, luego consultar por uno. Envuélvelo en una clase si es algo que vas a usar mucho.

+1

dependiendo de los requisitos, usar un DB para hacer esta búsqueda puede costar más en términos de memoria y ciclos de CPU que un doble dict. – Chii

+1

¡En mi caso, eso será demasiado lento! –

2

Aquí es mi propia solución a este problema: http://github.com/spenthil/pymathmap/blob/master/pymathmap.py

El objetivo es que sea lo más transparente para el usuario como sea posible. El único atributo significativo introducido es partner.

OneToOneDict subclases de dict - Sé que isn't generally recommended, pero creo que tengo los casos de uso común cubiertos. El backend es bastante simple, (dict1) mantiene un weakref a un 'socio' OneToOneDict (dict2) que es el inverso. Cuando se modifica dict1, dict2 también se actualiza y viceversa.

Desde la cadena de documentación:

>>> dict1 = OneToOneDict() 
>>> dict2 = OneToOneDict() 
>>> dict1.partner = dict2 
>>> assert(dict1 is dict2.partner) 
>>> assert(dict2 is dict1.partner) 
>>> dict1['one'] = '1' 
>>> dict2['2'] = '1' 
>>> dict1['one'] = 'wow' 
>>> assert(dict1 == dict((v,k) for k,v in dict2.items())) 
>>> dict1['one'] = '1' 
>>> assert(dict1 == dict((v,k) for k,v in dict2.items())) 
>>> dict1.update({'three': '3', 'four': '4'}) 
>>> assert(dict1 == dict((v,k) for k,v in dict2.items())) 
>>> dict3 = OneToOneDict({'4':'four'}) 
>>> assert(dict3.partner is None) 
>>> assert(dict3 == {'4':'four'}) 
>>> dict1.partner = dict3 
>>> assert(dict1.partner is not dict2) 
>>> assert(dict2.partner is None) 
>>> assert(dict1.partner is dict3) 
>>> assert(dict3.partner is dict1) 
>>> dict1.setdefault('five', '5') 
>>> dict1['five'] 
'5' 
>>> dict1.setdefault('five', '0') 
>>> dict1['five'] 
'5' 

Cuando consigo algo de tiempo libre, tengo la intención de hacer una versión que no almacena las cosas dos veces. No hay idea de cuándo será eso :)

Cuestiones relacionadas