实现排序映射和集合以实现 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 可能比看起来要复杂，因为我们可能希望维护结构计数为 O(1) 的属性。（当然，我们可以去除这个要求，但请参见以下内容。）

data.avl 集合在节点中存储排名信息；这使您可以以 O(1) 的计数查询排名并发航的映射操作，但这会以节点大小为代价。我认为对于不同的用例，特别是由于 data.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 报告）