对向量进行排序导致返回非索引的 ArraySeq

Question

对向量进行排序会返回一个 ArraySeq，其获取时间为 O(n)，而不是 O(log N)。这意味着将向量排序后再将其转换回向量可能更有效。

原因： {{sort}} 通过将待排序的集合复制到一个数组中来工作，调用 {{Arrays/sort}} 来排序它，然后返回一个在已排序数组上的 seq。返回的 seq 是一个 ArraySeq，没有实现 Indexed。

替代方案

1. 使 ArraySeq（及其原始特殊化）实现 Indexed，提供通过索引的常量时间查找。
2. 分别为不同类型的集合类型专门化排序
3. ???

Answer 1

由：ragge 发布的评论

更新描述，附加补丁。

Answer 2

由：ragge 发布的评论

添加了对当前补丁的链接。

Answer 3

由：alexmiller 发布的评论

这里还可以考虑的一个替代方案是让 sort 做得更智能一些。

Answer 4

由：ragge 发布的评论

关于这种方法及其影响，我更不确定这个补丁是否是一个好主意。对于排序向量的特定情况，这有一点道理，但从另一方面来看，{{sort}}只承诺返回给定coll的排序序列。只是在它支持通过索引高效查找数据结构的序列类型上实现{{Indexed}}感觉是不正确的。正如你建议的，也许我们应该把精力更多地放在让sort变得更智能上，这是一个不同的问题，或者简单地使用排序集合。

Answer 5

评论者：hiredman

在这里，最好的办法可能就是将sort改为返回向量。序列管道中sort的使用将继续正常工作，但一个sort后跟一个conj将失败（我无法立即回忆起此类示例，但我知道它们确实存在）。排序似乎意味着一个完整的集合，而向量可以在这里返回的“最强”的集合。

由于核心的保守性质以及conj排序的问题，最好的下一件事情可能是添加一个类似于现有mapv的sortv。

另一个选项可能是移除对seq的调用，这样sort就返回排序后的数组。这实际上是非常有用的，因为你可以使用Arrays.binarySearch。在排序后对conj的调用将引发异常，而不是将conj放置在“错误”的位置。

Answer 6

参考：https://clojure.atlassian.net/browse/CLJ-1794（由alexmiller提交）