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

Question

对向量进行排序返回的是具有 O(n) 获取时间的 ArraySeq，而不是 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}}，感觉不妥。像你建议的那样，可能更好的做法是思考如何使排序算法更智能，这是一个不同的问题，或者直接使用有序集合。

Answer 5

评论人：hiredman

在这里，似乎最好的办法是把sort改为返回向量。在序列管道中使用sort的情况将继续工作，但紧接着sort和conj的操作将会出错。排序似乎意味着一个完全实现的集合，而向量是这里可以返回的最“强大”的实现集合。

考虑到核心的保守性，以及上面提到的conj排序问题，下一步可能是在现有的mapv基础上添加一个类似sortv的函数。

另一个选择可能是删除对seq的调用，这样sort就返回排序后的数组。这实际上非常有用，因为你可以使用Arrays.binarySearch。在排序后的操作中调用conj将抛出异常，而不是把元素放到错误的位置。

Answer 6

参考：[https://clojure.atlassian.net/browse/CLJ-1794](https://clojure.atlassian.net/browse/CLJ-1794) (由 alexmiller 提出)