Существует ли двунаправленная многокарточная постоянная структура данных?

Question

Другими словами, можем ли мы эффективно моделировать многие отношения в постоянной структуре данных?

---

Была предложена пара однонаправленных мультикарт. Тем не менее, я не уверен, как это будет хорошо работать для удаления в постоянной структуре данных. Давайте возьмем случай, когда у нас есть ключи 1..4 для значений «1» .. «4», и предположим, что каждый из них относится ко всем остальным, поэтому у нас есть две карты, которые очень похожи в обоих направлениях:

{1 => ["2", "3", "4"], 2 => ["1", "3", "4"], ...} {"1" => [2,3,4], "2" => [1,3,4], ...}

Теперь мы хотим полностью удалить пункт 1 из системы. Это требует изменения одного узла в первой карте, но это требует изменения n-1 узлов во второй. Для n в тысячах (что, вероятно, в случае, я рассматриваю это для), не будет ли это довольно дорого? Или мультикарта оптимизирована для обработки изменений такого типа? Это патологический случай, но все же ...

---

Quadtrees кажется увлекательной идеей. Я собираюсь еще об этом подумать.

Answer 1

Доказательство по конструкции: пакет bimap для Haskell.

Bimap - это, по сути, биекция между подмножествами двух типов аргументов

А как это реализовано?

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

как пара однонаправленных карт.

Answer 2

Самый простой способ - использовать пару однонаправленных карт. Это имеет определенную стоимость, но вы не станете намного лучше (вы могли бы стать немного лучше, используя выделенные двоичные деревья, но вам придется заплатить огромную сложность, если вам придется реализовать это самостоятельно). По сути, поиск будет таким же быстрым, но добавление и удаление будут в два раза медленнее. Что не так уж плохо для логарифмической операции. Еще одним преимуществом этого метода является то, что вы можете использовать специализированные типы карт для типа ключа или значения, если он у вас есть. У вас не будет такой гибкости с конкретной универсальной структурой данных.

Другое решение состоит в том, чтобы использовать квадродерево (вместо того, чтобы рассматривать отношение NxN как пару отношений 1xN и Nx1, вы видите его как набор элементов в декартовом произведении (ключ * значение) ваших типов, то есть (пространственная плоскость), но мне не ясно, что затраты времени и памяти лучше, чем с двумя картами. Я предполагаю, что это должно быть проверено.

Наконец, у меня есть потрясающая нерегулярная рекурсивная структура данных, чтобы сделать это, но я не могу найти ссылку на нее на английском языке.

Редактировать: я просто быстро вставил адаптированную версию исходного кода для этой загадочной структуры данных.