排序向量返回非索引化ArraySeq

Question

排序向量会产生O(n)获取的ArraySeq，而不是O(log N)获取。这意味着取一个向量，排序，然后重新将其转换为向量可能更有效。

原因： {{sort}}通过将待排序的集合复制到一个数组中，调用{{Arrays/sort}}进行排序，然后返回一个在排序数组上的序列来实现。 返回的序列是ArraySeq，不实现Indexed。

替代方案

1. 使ArraySeq（及其原语特化）实现Indexed，提供通过索引的常数时间查找。
2. 对不同的集合类型进行排序特化
3. ???

Answer 1

评论由：ragge

更新描述，附加补丁。

Answer 2

评论由：ragge

添加当前补丁链接。

Answer 3

评论由：alexmiller

这里可以考虑的另一个替代方案是让sort做更智能的事情。

Answer 4

评论由：ragge

经过进一步思考这个方法及其影响，我不太确定这个补丁真的很好。对于排序向量的特定情况，它有点道理，但从另一方面讲，{{sort}} 只承诺返回给定 coll 的排序序列。仅仅因为底层数据结构支持高效的索引查找就为序列类型实现 {{Indexed}} 感觉是错误的。正如你建议的，也许我们应该多花点时间思考如何让排序更智能，这是一个不同的问题，或者干脆使用排序好的集合。

Answer 5

评论者：hiredman

最好的办法可能是将 sort 改为返回向量。在序列管道中间的状态中调用 sort 依然会继续工作，但是排序后紧跟 conj 的话会出错（我手头没有这样的实例，但我确信存在）。排序似乎意味着一个完全实现好的集合，向量是这里可以返回的“最强”实现好的集合。

鉴于核心的保守性，以及上面 conj 排序的问题，下一种最好的办法可能是添加一个类似于现有 mapv 的 sortv。

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

Answer 6

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