对向量进行排序产生非索引的 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}} feels wrong。正如你建议的，也许我们应该将精力更好地用于使排序更智能化，这是一个不同的问题，或者仅仅使用排序后的集合。

Answer 5

评论人：hiredman

在这里，最好的办法可能是将sort改为返回向量。在序列管道中sort的使用将继续工作，但随后使用conj将中断（我无法立刻回忆起这种情况的实例，但我确信它们存在）。排序似乎意味着一个完整的集合，而向量是可以返回这里的“最强”集合。

鉴于核心是保守的，以及上面提到的conj排序问题，接下来的最佳选择可能是添加一个类似现有的mapv的sortv。

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

Answer 6

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