Существует ли двунаправленная многокарточная постоянная структура данных?
Другими словами, можем ли мы эффективно смоделировать многие-многие отношения в постоянной структуре данных?
Была предложена пара однонаправленных мультикарт. Тем не менее, я не уверен, как это будет хорошо работать для удаления в постоянной структуре данных. Давайте возьмем случай, когда у нас есть ключи 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 кажется увлекательной идеей. Я собираюсь подумать об этом.
2 ответа
Самый простой способ - использовать пару однонаправленных карт. Это имеет определенную стоимость, но вы не станете намного лучше (вы могли бы стать немного лучше, используя выделенные двоичные деревья, но вам придется заплатить огромную сложность, если вам придется реализовать это самостоятельно). По сути, поиск будет таким же быстрым, но добавление и удаление будут в два раза медленнее. Что не так уж плохо для логарифмической операции. Еще одним преимуществом этого метода является то, что вы можете использовать специализированные типы карт для типа ключа или значения, если он у вас есть. Вы не получите такой гибкости с конкретной универсальной структурой данных.
Другое решение состоит в том, чтобы использовать квадродерево (вместо того, чтобы рассматривать отношение NxN как пару отношений 1xN и Nx1, вы видите его как набор элементов в декартовом произведении (Key*Value) ваших типов, то есть пространственном самолет), но мне не понятно, что затраты времени и памяти лучше, чем с двумя картами. Я полагаю, это нужно проверить.
Наконец, у меня есть потрясающая нерегулярная рекурсивная структура данных, чтобы сделать это, но я не могу найти ссылку на нее на английском языке.
Редактировать: я просто быстро вставил адаптированную версию исходного кода для этой загадочной структуры данных.
Доказательство по конструкции: пакет bimap для Haskell.
Bimap - это биекция между подмножествами двух типов аргументов.
И как это реализовано?
data Bimap a b = MkBimap !(M.Map a b) !(M.Map b a)
Как пара однонаправленных карт.