对向量排序返回非索引型ArraySeq

Question

对向量进行排序，导致返回的ArraySeq的获取时间从O(log N)降低到O(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}}只承诺会返回给定集合的排序序列。仅仅因为底层数据结构支持通过索引高效查找就为实现{{Indexed}}函数而实施，感觉并不合适。正如你建议的那样，我们可能更应该思考如何使排序更智能，这是一个不同的问题，或者直接使用排序好的集合。

Answer 5

评论者：hiredman

可能最好的改动就是将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报告）