tuplas - ¿Una estructura de datos para mapeos 1: 1 en python?

listas por comprensión python

Question

Tengo un problema que requiere un mapeo reversible 1: 1 de las claves de los valores.

Eso significa que a veces quiero encontrar el valor dado a una clave, pero otras veces 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: Invertir un diccionario es muy fácil, aquí hay una receta, pero para un diccionario grande puede ser muy lento .

La otra alternativa es crear una nueva clase que combine 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.

Entonces, ¿hay una mejor estructura que pueda usar?

• Mi aplicación requiere que esto sea muy rápido y use 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 artículos.
• Keys & Valus tienen la garantía de ser únicos, es decir len (set (x)) == len (x) for for x en [D.keys (), D.valuies ()]

Answer 1

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.

En realidad, no, 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 las bases de datos relacionales pueden ser muy rápidas.

Answer 2

La otra alternativa es crear una nueva clase que combine 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.

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

Lo que quiero decir es que los datos reales no se copiarían. 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}

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

No puedo imaginar una solución en la que tenga la velocidad de búsqueda clave al buscar por valor, si no gasta al menos suficiente memoria para almacenar una tabla hash de búsqueda inversa (que es exactamente lo que se está haciendo en su "unir dos" dict s "solución).

Answer 3

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

Eso está escrito de forma extraña: "la clave o el valor (o ambos)" no se siente bien. O bien son enteros o no son enteros.

Parece que todos son enteros.

O bien, parece que estás pensando en reemplazar el objeto objetivo por un valor entero, por lo que solo tienes 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 dos. 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

Tienes una tupla de heapq (key,value) . O bien, si su objeto subyacente es más complejo, las tuplas (key,object ).

Tienes 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 estructurada de heapq.

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

Answer 4

¿Qué hay de 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.

Answer 5

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

El objetivo es hacerlo tan transparente para el usuario como sea posible. El único atributo significativo introducido es partner .

Subclases OneToOneDict de dict : sé que generalmente no se recomienda , pero creo que tengo cubiertos los casos de uso común. El backend es bastante simple, ( dict1 ) mantiene un weakref a un ''socio'' OneToOneDict ( dict2 ) que es su inverso. Cuando se modifica dict2 se actualiza también y viceversa.

Desde el docstring:

>>> 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 tenga algo de tiempo libre, pretendo hacer una versión que no almacene cosas dos veces. No hay idea de cuándo será eso :)

Answer 6

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 es de alguna utilidad:

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

Answer 7

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.

Answer 8

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]