Asignaciones bidireccionales inyectivas

A menudo trato con mapeos que son inyectivos . En la terminología de progtwigción, esto se puede express como un diccionario donde todos los valores son únicos y, por supuesto, todas las claves.

¿Existe una estructura de datos eficiente en la memoria para las asignaciones inyectivas con todas las propiedades de complejidad de tiempo que espera de los diccionarios?

Por ejemplo:

d = {1: 'a', 2: 'b', 3: 'c', 4: 'd', 5: 'e'} d.get(2) = 'b' # this works with a normal dictionary d.get('b', reverse=True) = 2 # but this is not possible 

Todas las soluciones en Dos vías / mapa inverso parecen requerir el uso o la combinación de dos conjuntos de asignaciones, centrándose en facilitar las operaciones en un mapa de dos vías. Esto está bien para diccionarios pequeños que caben perfectamente en la memoria, pero no es bueno para diccionarios grandes.

El requisito es que no debe haber una sobrecarga de memoria adicional que almacene el mapa bidireccional inyectivo frente a un diccionario regular que almacene solo los mapas unidireccionales.

Entiendo que los diccionarios usan una tabla hash, que usa un tipo de datos de matriz asociativa. Por definición, los arreglos asociativos implementan asignaciones de claves -> valores con claves únicas. ¿Es posible, teóricamente o en la práctica, producir un mapeo inyectivo inteligente que permita la búsqueda inversa?

Si no fuera posible, agradecería una explicación de por qué tal construcción es difícil o imposible de implementar con la misma eficiencia que los diccionarios.

Actualizar

Después de la discusión con @rpy (vea los comentarios a continuación), cualquier información sobre cómo configurar un objeto similar a un diccionario de Python usando una función hash reversible perfecta sería útil. Pero, por supuesto, una implementación funcional sería ideal (ya he probado la perfección ).

La respuesta neta a su pregunta es: NO (para cualquier implementación eficiente)

Pones dos requisitos que no se pueden cumplir al mismo tiempo:

  1. No use memoria extra para el mapeo inverso
  2. No agregue tiempo extra para hacer búsquedas (al revés)

¿Por qué esas dos restricciones están prohibiendo una solución?

Las asignaciones son pares de valores (tuplas). La implementación más trivial sería:

Búsqueda secuencial de todas las tuplas para un partido.

Esto tendría una complejidad idéntica para el mapeo hacia adelante y hacia atrás.
Sin embargo, esto viola claramente la expectativa de time-complexity properties you expect from dictionaries de time-complexity properties you expect from dictionaries :

Si permitiera la complejidad de O (n) , buscar un conjunto de tuplas secuencialmente le brindaría una solución adecuada.

Por lo general, las implementaciones de diccionarios intentan llegar a la complejidad de O (1) o al menos O (n * log (n)) . Esto se está logrando mediante la introducción de datos adicionales para acelerar las búsquedas, como hashes o árboles. Desafortunadamente, estas ayudas solo ayudan en una dirección ya que tratan con claves (caso de mapeo directo) o valores (caso de mapeo inverso).

Por lo tanto, tan pronto como necesite mantener baja la complejidad de la búsqueda (esto también se aplica a la complejidad de la modificación, pero generalmente los diccionarios se adaptan a la búsqueda rápida), deberá agregar datos para lograr la velocidad.

Todo el asunto se reduce a la clásica relación de intercambio de memoria y velocidad.

EDITAR:

Un enfoque para abordar el problema en una implementación general (para los casos en que las claves y los valores permiten obtener un representante numérico si esos no son números integrales en primer lugar) podría ser:

Calcule un valor hash para clave y uno para value y registre la tupla bajo ambos valores hash. De esta manera, puede tomar la clave o el valor e identificar la tupla correspondiente y devolver el resultado adecuado. Esto incluso funcionaría para casos no inyectivos cuando permites la devolución de conjuntos de tuplas coincidentes.

Esto requerirá más espacio (doble las entradas de hash) mientras se mantiene la complejidad de búsqueda dentro de los valores típicos de los dictados basados ​​en hash. Es posible que deba vigilar el tamaño del grupo de hash (longitud de las cadenas de colisión), especialmente cuando los conjuntos de valores de claves y valores no están separados.