Эффективная функциональная структура данных для конечных биекций
Я ищу функциональную структуру данных, которая представляет собой конечную разбивку между двумя типами, которая экономит пространство и время.
Например, я был бы счастлив, если бы, рассматривая биекцию f размера n:
- расширение f новой парой элементов имеет сложность O(ln n)
- запрос f(x) или f^-1(x) имеет сложность O(ln n)
- внутреннее представление для f более эффективно с точки зрения пространства, чем наличие 2 конечных отображений (представляющих f и его обратное)
Мне известно эффективное представление перестановок, как в этой статье, но, похоже, это не решает мою проблему.
2 ответа
Пожалуйста, посмотрите на мой ответ для относительно аналогичного вопроса. Предоставленный код может обрабатывать общие отношения NxM, но также может быть специализирован только для биекций (так же, как для двоичного дерева поиска).
Вставьте ответ здесь для полноты:
Самый простой способ - использовать пару однонаправленных карт. Это имеет определенную стоимость, но вы не станете намного лучше (вы могли бы стать немного лучше, используя выделенные двоичные деревья, но вам придется заплатить огромную сложность, если вам придется реализовать это самостоятельно). По сути, поиск будет таким же быстрым, но добавление и удаление будут в два раза медленнее. Что не так уж плохо для логарифмической операции. Еще одним преимуществом этого метода является то, что вы можете использовать специализированные типы карт для типа ключа или значения, если он у вас есть. Вы не получите такой гибкости с конкретной универсальной структурой данных.
Другое решение состоит в том, чтобы использовать квадродерево (вместо того, чтобы рассматривать отношение NxN как пару отношений 1xN и Nx1, вы видите его как набор элементов в декартовом произведении (Key*Value) ваших типов, то есть пространственном самолет), но мне не понятно, что затраты времени и памяти лучше, чем с двумя картами. Я полагаю, это нужно проверить.
Хотя это не удовлетворяет вашему третьему требованию, bimap s кажется подходящим вариантом. (Они просто делают две конечные карты, по одной в каждом направлении, удобно использовать.)