¿Hay una estructura de datos persistente multimap bidireccional?

Question

En otras palabras, ¿podemos modelar muchas a muchas relaciones en una estructura de datos persistente de manera eficiente?

---

Se sugirió un par de multimaps unidireccionales. Sin embargo, no estoy seguro de cómo esto funcionaría bien para su eliminación en una estructura de datos persistente. Tomemos el caso donde tenemos las claves 1..4 a valores "1" ... "4" y digamos que cada una se refiere a todas las demás, entonces tenemos dos mapas que se parecen mucho en ambas direcciones:

{1 => ["2", "3", "4"], 2 => ["1", "3", "4"], ...} {"1" => [2,3 , 4], "2" => [1,3,4], ...}

Ahora queremos eliminar completamente el elemento 1 del sistema. Eso requiere cambiar un nodo en el primer mapa, pero requiere cambiar n-1 nodos en el segundo. Para n en los miles (que es probable en el caso en el que estoy considerando esto), ¿no sería bastante caro? ¿O es un multimap optimizado para manejar ese tipo de cambio? Es un caso patológico, pero aún así ...

---

Quadtrees parece una idea fascinante. Voy a pensar un poco más.

Answer 1

La manera más simple es usar 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.

Finalmente, existe una estructura de datos recursiva no regular alucinante para hacer eso, pero no puedo encontrar una referencia para ello en inglés.

Editar: Acabo de recibir quickly pasted una versión adaptada del código original para esta misteriosa estructura de datos.

Answer 2

Prueba de construcción: el paquete bimap para Haskell.

Un BIMAP es esencialmente una biyección entre los subconjuntos de sus dos tipos de argumentos

Y cómo se implementa?

data Bimap a b = MkBimap !(M.Map a b) !(M.Map b a) 

Como un par de mapas unidireccionales.