实现有序映射和集合以实现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发表

我没有详细检查，但看起来有可能使用现有的 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 报告）