言い換えれば、永続データ構造の多対多の関係を効率的にモデル化できますか？
一方向のマルチマップのペアが提案されました。ただし、これが永続データ構造での削除にどのように機能するかはわかりません。キー1..4から値"1".. "4"があり、それぞれが他のすべてを参照しているとすると、両方向で非常によく似た2つのマップがあります。
{1 => ["2"、 "3"、 "4"]、2 => ["1"、 "3"、 "4"]、...} {"1" => [2,3、 4]、 "2" => [1,3,4]、...}
次に、アイテム1をシステムから完全に削除します。これには、最初のマップで1つのノードを変更する必要がありますが、2番目のマップでn-1ノードを変更する必要があります。数千のnの場合（これを検討している場合は可能性が高いです）、それはかなり高価ではないでしょうか？または、マルチマップはそのタイプの変更を処理するために最適化されていますか？病的なケースですが、それでも...
四分木は魅力的なアイデアのようです。もう少し考えてみます。
最も簡単な方法は、単方向マップのペアを使用することです。多少のコストはかかりますが、それほど良くなることはありません (専用のバイナリ ツリーを使用すると少し良くなる可能性がありますが、自分で実装する必要がある場合は、複雑なコストがかかります)。基本的に、ルックアップは同じくらい速くなりますが、追加と削除は 2 倍遅くなります。これは、対数演算にはそれほど悪くありません。この手法のもう 1 つの利点は、キーまたは値の型に特化したマップ型があれば、それを使用できることです。特定のジェネラリスト データ構造では、柔軟性があまり得られません。
別の解決策は、四分木を使用することです (NxN の関係を 1xN と Nx1 の関係のペアと見なすのではなく、タイプのデカルト積 (キー*値) の要素のセット、つまり空間しかし、時間とメモリのコストが 2 つのマップよりも優れているかどうかはわかりません。テストする必要があると思います。
最後に、それを行うための驚異的な非正規再帰データ構造がありますが、英語でのリファレンスが見つかりません。
編集:この不思議なデータ構造の元のコードの適応バージョンをすぐに貼り付けました。
構成による証明: Haskell のbimapパッケージ。
Bimap は基本的に、その 2 つの引数タイプのサブセット間の全単射です。
そして、それはどのように実装されていますか？
data Bimap a b = MkBimap !(M.Map a b) !(M.Map b a)
一方向マップのペアとして。