排序向量产生非索引的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}}仅仅承诺返回给定collection的已排序序列。仅因为底层数据结构支持通过索引高效查找，就为sequence类型实现{{Indexed}}感觉不太对。正如您所建议的，也许我们更应该花时间考虑使sort更智能化的方案，这是一个不同的问题，或者简单地使用已排序的collections。

Answer 5

评论者：hiredman

看来最好的办法是将sort修改为返回一个向量。在sequence pipelines中使用sort的中途会继续工作，但排序后接属性的操作将失败（我无法立刻回忆起具体的例子，但我确信它们是存在的）。排序似乎暗示了一个完整实现了的collection，而vector是这里可以返回的“最强”实现。

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

另一种选择可能是去掉对seq的调用，这样sort就返回一个已排序的数组。这实际上非常有用，因为你可以使用Arrays.binarySearch。然后在sort之后调用conj将抛出异常，而不是conj到“错误”的位置。

Answer 6

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