我正在寻找一种表示两种类型之间有限双射的功能数据结构，即节省空间和节省时间。
例如，如果考虑到大小为 n 的双射 f，我会很高兴：
- 用一对新元素扩展 f 的复杂度为 O(ln n)
- 查询 f(x) 或 f^-1(x) 的复杂度为 O(ln n)
- f 的内部表示比具有 2 个有限映射（表示 f 及其逆）更节省空间
我知道排列的有效表示，比如这篇论文，但它似乎并没有解决我的问题。
问问题
1378 次
2 回答
11
请查看我对一个相对相似的问题的回答。提供的代码可以处理一般的 NxM 关系，但也可以专门用于双射（就像二叉搜索树一样）。
为了完整起见，在此处粘贴答案：
最简单的方法是使用一对单向地图。它有一些成本，但您不会变得更好（使用专用二叉树可能会变得更好，但是如果您必须自己实现它，则需要付出巨大的复杂性成本）。本质上，查找速度会一样快，但添加和删除速度会慢一倍。这对于对数运算来说还不错。这种技术的另一个优点是，如果您有可用的键或值类型，您可以使用专门的映射类型。对于特定的通用数据结构，您不会获得那么多的灵活性。
另一种解决方案是使用四叉树（而不是将 NxN 关系视为一对 1xN 和 Nx1 关系，您将其视为您的类型的笛卡尔积 (Key*Value) 中的一组元素，即空间飞机），但我不清楚时间和内存成本是否比两张地图更好。我想它需要进行测试。
于 2012-05-20T07:49:56.977 回答
6
尽管它不满足您的第三个要求，但bimap似乎是要走的路。（他们只是制作了两张有限地图，每个方向一张，使用方便。）
于 2012-05-19T22:57:03.077 回答