是否有雙向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持久數據結構？

回答

相關問題