在 Clojure 排序集中查找最大元素

Question

我正在寻找一种惯用的 O(1) 方法来sorted-set在 Clojure 中提取整数a 的最大元素。我必须将集合转换为 seq 吗？

Answer 1

使用 Clojure 的内置排序集，这是 O(log n)：

(first (rseq the-set))

使用data.avl集，以上也有效，您还可以使用nthO(log n) 时间按等级访问元素：

(nth the-set (dec (count the-set)))

这些数据结构都没有提供对极端元素的 O(1) 访问，但是[the-set max-element]如果您希望对最大元素执行频繁的重复访问，您当然可以使用带有自定义 API 的包（可能表示为记录以进行更清晰的操作）。

如果您只关心对最大元素的快速访问而不关心有序遍历，您实际上可以使用带有“未排序”集合的捆绑方法——内置哈希集或data.int-map集。这对于重复disj最大元素没有用，当然，仅用于维护基本未排序集合的上限信息（除非您在包中保留一堆最大元素，在这一点上，简单地使用已排序的集合并获得所有相关操作免费）。