在序列生成操作(如排序)之后,如何将序列转换回向量?使用(vec..)作为载体的序列是昂贵的吗?
一个(不好?)可能性是无序地创建一个新的向量:
(vec (sort [1 2 3 4 5 6]))
我问是因为我需要随机访问(nth ..)大的排序向量-现在是排序后的大序列,具有可怕的O(n)随机访问时间
发布于 2010-01-03 02:12:42
根据我自己的测试(没有什么科学依据),在进行大量排序的情况下,直接处理数组可能会更好。但是如果你很少排序,并且有很多随机访问要做,那么使用向量可能是一个更好的选择,因为随机访问时间平均要快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
附注:请注意,向量版本实际上不会将排序后的向量存储在任何地方,但这不会显著改变结果,因为您将在循环中使用简单的绑定来提高速度。
发布于 2010-01-03 12:49:24
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集合)将是可变的。如果您没有将它交给其他代码,这是很好的,但要小心。
发布于 2010-01-02 08:16:38
如果你需要随机访问大向量排序的结果,那么调用vec所花费的时间应该远远超过这样做所节省的时间。
如果你分析发现它太慢了,你可能不得不使用java数组。
https://stackoverflow.com/questions/1989301
复制相似问题