排序集的目的是什么？

Question

sorted-setClojure 有一个创建对象的函数PersistentTreeSet。顾名思义，sorted-set创建唯一对象的排序集合。

排序集什么时候有用？什么时候使用sorted-setandsort更好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?当您需要快速设置语义 \xe2\x80\x93和(= 元素删除)时，排序集非常有用，如 Leon \ conjxe2 disj\x80\x93 所解释的以及以明确定义的顺序进行遍历。对于内置排序集（和映射），可以在整个集 ( seq, rseq) 以及两个键之间的任何“子范围” ( subseq, rsubseq) 上进行有序遍历，包括或排除。

\n\n

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

\n\n

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

\n\n

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

\n