实现排序的映射和集合，使其实现 j.u.NavigableMap 和 NavigableSet 接口

Question

由于 Clojure 1.5 可能将不再针对 JVM 5，因此添加了对 (Concurrent)?Navigable(Map|Set) 接口的支持。这可能需要向 PersistentTreeMap 添加函数，以便向下遍历红黑树以选择最接近的项目。

Answer 1

评论者：michalmarczyk

只是想指出，(链接：https://github.com/clojure/data.avl 文本：data.avl) 提供了这项功能，尽管是通过 Clojure 接口。实现 descendingMap 会很直接，但这可能会使某些功能的实现变得更加复杂，我认为这些功能可能更有说服力。如果需要，我可以提供更多详细信息，不过也许最好在 data.avl 的跟踪器上讨论。

在 PersistentTreeMap 中实现完整的 NavigableMap 可能比想象中更复杂，因为我们可能希望维持结果结构的 count 属性为 O(1)。当然，可以去掉这个要求，但请参阅以下内容。

data.avl 集合在节点中存储排名信息；这使我们可以以 O(1) 的成本进行排名查询和可导航的映射操作，但它在节点大小上有所牺牲。我认为对于不同的用例，拥有更紧凑的 PTM 和功能更全但节点更多的 data.avl 是有用的，尤其是在 data.avl 在基本操作方面非常快的情况下（例如，完全与 PTM 相当，通过路径访问节点；一些单个树操作可能稍微慢一些，但 AVL 树通常更浅）。

Answer 2

评论者：jafingerhut

我没有仔细检查，但它似乎可能是这样的：NavigableMap 和 NavigableSet 接口可以使用现有的 clojure.core/subseq 和 clojure.core/rsubseq 函数（以及 first、seq 等）来实现。

Answer 3

_评论者：michalmarczyk_

{{subseq}} 和 {{rsubseq}} + {{first}} 解决了 {{NavigableMap}} 的 "邻近查找" 部分，但不是子映射方法。

以对数时间分割红黑树是完全可能的，但如前所述，如果您想要保持结果结构上的 {{count}} 属性不是 O(1)，至少也要比 O(n) 显著更好，这是不可能的。这是因为，没有方法知道 BST 的任何子范围内包含多少节点，除非实际遍历它或提前在节点（至少是部分节点）中存储注释。

我在去年十一月的 Conj 讲座中描述了一种可能的解决方案，我在某处有一个草图，但它不会提供像 data.avl 那样的便利类型；上面描述的限制是根本性的；它可能适用于在使用中几乎从不调用 {{count}} 的情况。


作为旁注，data.avl 在其测试套件中使用基于 {{subseq}} 等的邻近查找实现，作为对由 {{clojure.data.avl/nearest}} 使用的直接实现的合理性检查。它还有一个基于 {{subseq}} 的{{subrange}}实现（data.avl 集合的通用子集函数）；如预期的那样，它对于所有除最小输出大小之外的所有情况都非常慢。

Answer 4

参考：https://clojure.atlassian.net/browse/CLJ-1008（由 jim.blomo 报告）