是否有双向multimap持久性数据结构？ [英] Is there a bidirectional multimap persistent data structure?
问题描述
一对建议使用单向多图。但是，我不知道如何在持久性数据结构中进行删除。让我们来看一下我们有键1..4到值1..4，我们假设他们每个都是指所有其他的，所以我们有两个两个方向看起来非常相似的地图：
{1 => [2，3，4]，2 => [1，3，4]，...}
{1=> [2,3,4]，2=> [1,3,4]，...}
现在我们要从系统中完全删除项目1。这需要改变第一个地图中的一个节点，但是需要在第二个地图中更改n-1个节点。对于成千上万的人（在这种情况下，我正在考虑这个）可能不是那么贵吗？还是为了处理这种变化而优化的一个多重映射？这是一个病态，但仍然...
四叉树似乎是一个迷人的想法。我会给出一些更多的想法。
最简单的方法是使用一对单向地图。它有一些成本，但你不会变得更好（你可以使用专用的二进制树更好一些，但是如果你必须自己实现，你需要付出巨大的代价）。实质上，查找将是一样快，但添加和删除将是缓慢的两倍。哪个对于对数运算来说不是那么糟糕。这种技术的另一个优点是，如果您有一个可用的，您可以使用专门的地图类型作为键或值类型。一个不同的解决方案是使用一个四叉树（而不是将一个NxN关系作为一对1xN来考虑），而不是使用特定的通才数据结构来获得尽可能多的灵活性。
<和Nx1关系，您将其视为您的类型的笛卡尔乘积（Key * Value）中的一组元素，即空间平面），但是我不清楚，时间和内存成本比两个地图我想它需要测试。
最后，我有一个令人兴奋的非正则递归数据结构来做到这一点，但是我找不到参考
编辑：我只是快速粘贴这个神秘数据结构的原始代码的修改版本。
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.
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.
这篇关于是否有双向multimap持久性数据结构？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
