Clojure:顺序回到矢量

Question

如何在序列生成操作(如排序)后将序列转换回向量？在矢量序列上使用(vec ..)是否代价高昂？

一个(坏？)可能性是不按顺序创建一个新的向量:

(vec (sort [1 2 3 4 5 6]))

我问,因为我需要随机访问(第n ..)到巨大的排序向量 - 现在是排序后的巨大序列,可怕的O(n)随机访问时间

Answer 1

Meikel Brandmeyer刚刚在Clojure小组上发布了一个解决方案.

(defn sorted-vec
  [coll]
  (let [arr (into-array coll)]
    (java.util.Arrays/sort arr)
    (vec arr)))

Clojure sort在一个有序数组中返回一个seq; 这种方法做了很多相同的事情,但返回一个向量,而不是seq.

如果您愿意,您甚至可以跳过转换回Clojure持久数据结构:

(defn sorted-arr
  "Returns a *mutable* array!"
  [coll]
  (doto (into-array coll)]
    (java.util.Arrays/sort))

但是由此产生的Java数组(在大多数情况下,您可以将其视为Clojure集合)将是可变的.如果您没有将其交给其他代码,那很好,但要小心.

Answer 2

如果您需要对具有巨大向量的排序结果进行随机访问，那么调用 vec 所花费的时间应该远远超过这样做所节省的时间。

如果您分析并发现它太慢，您可能不得不使用 java 数组。

Answer 3

从我自己的测试(没有科学的)你可能会更好地直接在数组上进行大量排序.但是如果您很少排序并且有很多随机访问权限,那么使用向量可能是更好的选择,因为随机访问时间平均快40%以上,但由于将向量转换为向量,排序性能非常糟糕一个数组,然后回到一个向量.这是我的发现:

(def foo (int-array (range 1000)))

(time
  (dotimes [_ 10000]
    (java.util.Arrays/sort foo)))

; Elapsed time: 652.185436 msecs

(time
  (dotimes [_ 10000]
    (nth foo (rand-int 1000))))

; Elapsed time: 7.900073 msecs

(def bar (vec (range 1000)))

(time
  (dotimes [_ 10000]
    (vec (sort bar))))

; Elapsed time: 2810.877103 msecs

(time
  (dotimes [_ 10000]
    (nth bar (rand-int 1000))))

; Elapsed time: 5.500802 msecs

PS:请注意,矢量版本实际上并不会将排序后的矢量存储在任何位置,但是这不应该大大改变结果,因为您将在循环中使用简单绑定来提高速度.