是否存在双向多映射持久数据结构？
换句话说，我们可以在持久数据结构中有效地建模多对多关系吗？
建议使用一对单向多重映射。但是，我不确定这如何在持久数据结构中很好地进行删除。让我们以键 1..4 到值“1”..“4”为例，假设它们各自引用所有其他键，因此我们有两个在两个方向上看起来都非常相似的映射：
{1 => ; [“2”,“3”,“4”], 2 => [“1”，“3”，“4”]，...} {“1”=>； [2,3,4], "2" => [1,3,4], ...}
现在我们要从系统中完全删除第 1 项。这需要更改第一个映射中的一个节点，但需要更改第二个映射中的 n-1 个节点。对于数千个 n （这可能是我正在考虑的情况）那不是相当昂贵吗？或者多重映射是否针对处理此类更改进行了优化？这是一个病态的案例，但仍然......
四叉树似乎是一个令人着迷的想法。我会再考虑一下。
In other words, can we model many to many relationships in a persistent data structure efficiently?
A pair of unidirectional multimaps was suggested. However, I'm not sure how this would work well for removal in a persistent data structure. Let's take the case where we have keys 1..4 to values "1".."4" and let's say they each refer to all the others, so we have two maps that look very similar for both directions:
{1 => ["2","3","4"], 2 => ["1","3","4"], ...}
{"1" => [2,3,4], "2" => [1,3,4], ...}
Now we want to remove item 1 completely from the system. That requires changing one node in the first map, but it requires changing n-1 nodes in the second. For n in the thousands (which is likely in the case I'm considering this for) wouldn't that be rather expensive? Or is a multimap optimized for handling that type of a change? It's a pathological case, but still...
Quadtrees seems like a fascinating idea. I'm going to give that some more thought.
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（2）
最简单的方法是使用一对单向地图。它有一些成本，但你不会变得更好（使用专用二叉树你可以得到更好一点，但如果你必须自己实现它，你将付出巨大的复杂性成本）。本质上，查找速度会一样快，但添加和删除速度会慢一倍。这对于对数运算来说还不错。此技术的另一个优点是，如果有可用的映射类型，您可以使用键或值类型的专用映射类型。对于特定的通用数据结构，您不会获得那么多的灵活性。
一种不同的解决方案是使用四叉树（而不是将 NxN 关系视为一对 1xN 和 Nx1 关系，而是将其视为类型的笛卡尔积 (Key*Value) 中的一组元素，即空间飞机），但我不清楚时间和内存成本是否比两张地图更好。我想它需要进行测试。
最后，我有一个令人兴奋的非常规递归数据结构可以做到这一点，但我找不到它的英文参考。
编辑：我刚刚快速粘贴这个神秘数据结构的原始代码的改编版本。
The simplest way is to use a pair of unidirectional maps. It has some cost, but you won't get much better (you could get a bit better using dedicated binary trees, but you have a huge complexity cost to pay if you have to implement it yourself). In essence, lookups will be just as fast, but addition and deletion will be twice as slow. Which isn't so bad for a logarithmic operation. Another advantage of this technique is that you can use specialized maps types for the key or value type if you have one available. You won't get as much flexibility with a specific generalist data structure.
A different solution is to use a quadtree (instead of considering a NxN relation as a pair of 1xN and Nx1 relations, you see it as a set of elements in the cartesian product (Key*Value) of your types, that is, a spatial plane), but it's not clear to me that the time and memory costs are better than with two maps. I suppose it needs to be tested.
Finally, I there is a mind-blowing non-regular recursive data structure to do that, but I can't find a reference for it in english.
Edit: I just quickly pasted an adapted version of the original code for this mysterious data structure.
构造证明：Haskell 的 bimap 包。
，它是如何实现的？
作为一对单向地图。
Proof by construction: the bimap package for Haskell.
And how is it implemented?
As a pair of unidirectional maps.