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

Question

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

Answer 1

评论作者：michalmarczyk

只是想指出(data.avl：https://github.com/clojure/data.avl)提供了这种功能，尽管有一个Clojure接口。实现descendingMap应该是简单直接，但它可能会使某些可能更具吸引力的功能的实现复杂化。如果有需要，我可以详细说明，不过也许最好在data.avl的跟踪器上讨论。

在PersistentTreeMap中实现NavigableMap的全部内容可能比看起来要复杂，因为我们可能希望保持结果结构的计数特性为O(1)。当然，可以取消此要求，但请参见下文。

data.avl集合在节点中存储等级信息；这使您可以进行等级查询和可导航的映射操作，其返回值的计数为O(1)，但这会在节点大小上付出代价。我认为，对于不同的使用案例，尤其是data.avl对于基本操作（即在相同的路径上通过节点的访问；某些单个树操作可能稍微慢一些，但AVL树通常较浅）非常快，因此拥有紧凑的PTM和功能更完善但节点量更大的data.avl是有用的。

Answer 2

评论者：jafingerhut

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

Answer 3

_评论者：michalmarczyk_

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

以对数时间对红黑树进行子集操作是完全可能的，但是，正如我在之前的评论中提到的，如果你想在得到的结构上保持 {{count}} 属性（如果不是 O(1)，至少也要比 O\(n\) 突出得多），那么就不能这样做。这是因为没有一种方法可以知道任何 BST 子范围中的节点数，而不实际遍历或提前在（至少一些）节点上存储注释。

我在去年11月的 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 报告）