是否有双向multimap持久数据结构？

换句话说，我们可以在持久数据结构中有效地模拟多对多关系吗？是否有双向multimap持久数据结构？

建议使用一对单向multimaps。但是，我不确定这对于在持久数据结构中删除将如何工作。我们来看一下情况：我们将键1..4设为值“1”，“4”，并且假设它们各自指的是所有其他键，所以我们有两张在两个方向上看起来非常相似的地图：

{1 => [“2”，“3”，“4”]，2 => [“1”，“3”，“4”]，...} {“1”=> [2,3 ，4]，“2”=> [1,3,4]，...}

现在我们想要从系统中完全删除项目1。这需要更改第一个映射中的一个节点，但它需要在第二个映射中更改n-1个节点。对于数千人中的n（这可能是我正在考虑的情况）不会很贵吗？或者是为处理这种类型的更改而优化的multimap？这是一个病态的情况，但仍然...

Quadtrees似乎是一个迷人的想法。我会给予更多的思考。

来源

2011-04-16 mentics

最简单的方法是使用一对单向地图。它有一定的代价，但是你不会变得更好（使用专用的二叉树可能会更好一些，但如果你必须自己实现它，则需要付出巨大的复杂成本）。实质上，查找速度一样快，但添加和删除速度会降低一倍。这对于对数运算来说并不是那么糟糕。这种技术的另一个优点是，如果你有一个可用的键，你可以为键或值类型使用专门的地图类型。对于特定的通用数据结构，您不会获得足够的灵活性。

不同的解决方案是使用四叉树（而不是将NxN关系看作一对1xN和Nx1关系，您将它看作是类型的笛卡尔积（Key * Value）中的一组元素，即是一个空间平面），但我不清楚时间和内存成本优于两张地图。我想它需要测试。

最后，我有一个令人兴奋的非常规递归数据结构来做到这一点，但我找不到它的英文参考。

编辑：我只是quickly pasted这个神秘的数据结构的原始代码的改编版本。

来源

2011-04-16 16:11:26 gasche

我很好奇，我想引用令人兴奋的数据结构，即使不是英文。 – mentics 2011-04-18 06:16:51

@taotree>我只是为它添加了一些代码。你怎么看？ – gasche 2011-04-18 12:48:29

有趣的是，虽然我注意到没有删除功能，这是我看到有这种类型的事情的挑战。此外，它看起来键和值必须是不同的类型，或者至少他们不能有两个相同的值。 – mentics 2011-04-18 17:24:11

结构证明：用于Haskell的bimap包。

一个BIMAP本质上是它的两个参数类型

和子集的双射它是如何实现的？

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

作为一对单向地图。

来源

2011-04-16 18:07:16

是否有双向multimap持久数据结构？

回答

相关问题