排序向量产生非索引的 ArraySeq

Question

对向量进行排序返回一个具有 O(n) 获取而不是 O(log N) 获取的 ArraySeq。这意味着将向量排序并再次将其转换成向量可能会更加高效。

原因： {{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}}对于序列类型，感觉是错误的。正如你建议的，或许将精力投入到使sort更智能上会更有效，这是一个不同的问题，或者直接使用已排序的集合。

Answer 5

评论者：hiredman

在这里，最好的办法可能就是把sort改为返回向量。在整个序列管道中使用的sort仍将继续工作，但随后使用conj（我无法立即回忆起具体的例子，但确信存在）将导致中断。排序似乎意味着一个完整的集合，而向量是这里可以返回的“最完整”的集合。

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

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

Answer 6

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