estructura de datos funcional eficiente para biyecciones finitas

Estoy buscando una estructura de datos funcional que represente biyecciones finitas entre dos tipos, que sea eficiente en cuanto a espacio y tiempo.estructura de datos funcional eficiente para biyecciones finitas

Por ejemplo, estaría feliz si, teniendo en cuenta una biyección f de tamaño n:

extiende f con un nuevo par de elementos tiene complejidad O (ln n)
consulta de f (x) o f^-1 (x) tiene complejidad o (ln n)
la representación interna de f es más espacio eficiente que tener 2 mapas finitos (que representa f y su inversa)

soy consciente de representación eficiente de la permutación s, como this paper, pero no parece resolver mi problema.

Fuente

2012-05-19 esope

+10

Tener dos mapas finitos es bastante eficiente en el uso del espacio ... es O (n) espacio. No puedo imaginar que puedas hacerlo mejor que eso. –

Comience con dos mapas finitos y preocúpese por algo más inteligente cuando se quede sin memoria. Los Hashmaps son buenos, si puedes hash los dos tipos. – augustss

Parece que si su función es estrictamente monótona, puede buscar en el mismo árbol tanto para la función como para la inversa. Es una posibilidad remota, supongo. –

Por favor, eche un vistazo a my answer para una pregunta relativamente similar. El provided code puede manejar las relaciones generales de NxM, pero también se especializará solo en biyecciones (tal como lo haría con un árbol de búsqueda binario).

pegar la respuesta aquí para completar:

La forma más sencilla es utilizar un par de mapas unidireccionales. Tiene algún costo, pero no mejorará mucho (podría mejorar un poco utilizando árboles binarios dedicados, pero tiene que pagar un enorme costo de complejidad si tiene que implementarlo usted mismo). Básicamente, las búsquedas serán igual de rápidas, pero la suma y la eliminación serán dos veces más lentas. Lo cual no es tan malo para una operación logarítmica. Otra ventaja de esta técnica es que puede usar tipos de mapas especializados para la clave o tipo de valor si tiene uno disponible. No obtendrá tanta flexibilidad con una estructura de datos generalista específica.

Una solución diferente es utilizar un quadtree (en lugar de considerar una relación NxN como un par de relaciones 1xN y Nx1, lo ve como un conjunto de elementos en el producto cartesiano (clave * valor) de sus tipos, que es, un plano espacial), pero no es claro para mí que los costos de tiempo y memoria sean mejores que con dos mapas. Supongo que necesita ser probado.

Fuente

2012-05-20 07:49:56 gasche

Su estructura de datos parece similar en espíritu a un [kd-tree] (https://en.wikipedia.org/wiki/Kd-tree). – esope

Aunque no satisface su tercer requisito, bimap s parece ser el camino a seguir. (Solo hacen dos mapas finitos, uno en cada dirección, cómodo de usar.)

Fuente

2012-05-19 22:57:03

estructura de datos funcional eficiente para biyecciones finitas

Respuesta

Cuestiones relacionadas