是否存在双向多图持久数据结构？

Question

换句话说,我们可以有效地在持久数据结构中建模多对多关系吗？

---

建议使用一对单向多图.但是,我不确定这对于在持久数据结构中删除是否会很好.让我们假设我们将键1..4设置为值"1".."4"并且假设它们各自引用所有其他的,所以我们有两个看起来非常相似的两个方向的地图:

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

现在我们想要从系统中完全删除第1项.这需要更改第一个映射中的一个节点,但它需要在第二个映射中更改n-1个节点.对于成千上万的n(可能在我考虑这个的情况下)不会那么贵吗？或者是针对处理此类更改而优化的多图？这是一个病态案例,但仍然......

---

四叉树似乎是一个迷人的想法.我要多考虑一下.

Answer 1

最简单的方法是使用一对单向映射.它有一些成本,但你不会变得更好(你可以使用专用二叉树更好一点,但如果你必须自己实现它,你需要支付巨大的复杂成本).从本质上讲,查找速度一样快,但添加和删除速度会慢一倍.这对于对数操作来说并不是那么糟糕.此技术的另一个优点是,如果有可用的键,则可以使用专用的地图类型作为键或值类型.使用特定的通用数据结构不会获得足够的灵活性.

另一种解决方案是使用四叉树(而不是将NxN关系视为一对1xN和Nx1关系,您将其视为类型的笛卡尔积(Key*Value)中的一组元素,即空间飞机),但我不清楚时间和内存成本比两张地图好.我想它需要进行测试.

最后,我有一个令人兴奋的非常规递归数据结构,但我无法用英语找到它的参考.

编辑:我刚刚为这个神秘的数据结构快速粘贴了原始代码的改编版本.

Answer 2

构造证明:Haskell 的bimap包.

Bimap本质上是两种参数类型的子集之间的双射

它是如何实现的？

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

作为一对单向地图.