data-structures - 排序集的目的是什么？

Question

Clojure 有个函数 sorted-set 这会创建一个 PersistentTreeSet目的。顾名思义， sorted-set 创建独特对象的排序集合。

排序集什么时候有用？什么时候用比较好 sorted-set 比 sort 和 distinct ?

=> (apply sorted-set [2 2 1 1 3 3])
#{1 2 3}
=> (sort (distinct [2 2 1 1 3 3]))
(1 2 3)

Answer 1

当您需要集合语义时，排序集合很有用 – 快速 contains? , conj和 disj (= 元素删除)，正如 Leon 所解释的那样 - 并以明确定义的顺序遍历。对于内置的有序集合(和映射)，可以在整个集合( seq 、 rseq )和两个键之间的任何“子范围”( subseq 、 rsubseq )上进行有序遍历，包容或排斥。

如果您愿意访问非核心集合，请访问 Contrib 库 data.avl (我是作者和维护者)提供了一种带有附加功能的排序集和映射的风格 – nth用于按等级访问集合元素，rank-of用于发现集合中元素的等级、最近邻查询以及返回输入集合的完全功能子集的“子范围”和类似拆分的操作(想想 subseq 返回原始的完全功能子集，而不仅仅是一个seq，而不会为了 GC 的目的保留任何不存在于子集中的原始元素)。所有这些都在 O(log n) 时间最坏情况下运行，就像标准的有序集合操作一样。

如果您只需要contains? + conj + disj ，您可能希望改用哈希集，因为它们往往会为这些操作提供更好的性能。然而，值得注意的是，如果您预期将来自可能是恶意的外部源的输入添加到您的集合中，即使您不关心顺序，您也可能希望使用已排序的集合。这是因为散列集的性能在存在散列冲突的情况下会降低到 O(n)(对手可能会强制，使用中的散列函数是确定性的并且是预先固定的)，而排序集的 O(log n) 是一个硬保证。

如果您只需要对输入集合进行一次排序，然后反复遍历它，或者遍历它的各种前缀/后缀，那么构建唯一项的排序向量可能确实是更好的选择。但是，如果您需要 subseq，即使对于仅遍历的工作负载，排序集可能仍然更可取。/rsubseq从集合的任意元素开始的特征( (subseq a-set >= 5) = seq 超过 a-set 的那些元素，相对于 a-set 的排序 >= 5)。