我有一对向量 x
和 y
独特的元素,我知道每个元素都需要分类。我希望有两者的交集,保持排序顺序。理想情况下,结果将是另一个向量,用于快速随机访问。
下面的一代只是为了举例,我的x
和 y
将预先分类和预先区分(它们实际上是时间样本)。
(defn gen-example [c] (-> (repeatedly c #(-> c rand int)) distinct sort vec))
user=> (def x (gen-example 100000)) (count x)
#'user/x
63161
user=> (def y (gen-example 100000)) (count y)
#'user/y
63224
我知道 Clojure 有
clojure.set/intersection
可以在 sorted-set
上工作.我的 x
和 y
具有相同的属性(已排序的不同元素)但类型不同。问题1:有没有更好/更快的方法来转换
x
和 y
至sorted-set
小于 (apply sorted-set x)
鉴于它们已经是不同的和排序的? user=> (time (def ssx (apply sorted-set x)))
"Elapsed time: 607.642592 msecs"
user=> (time (def ssy (apply sorted-set y)))
"Elapsed time: 617.046022 msecs"
现在我准备好执行我的交叉点了
user=> (time (count (clojure.set/intersection ssx ssy)))
"Elapsed time: 355.42534 msecs"
39992
这有点令人失望,粗略地看一下
(source clojure.set/intersection)
似乎没有对这些集合进行排序这一事实表现出任何特殊处理。问题 2:是否有更好/更快的方法来执行
sorted-set
的交集?小于 clojure.set/intersection
? (defn intersect-sorted-vector [x y]
(loop [x (seq x) y (seq y) acc []]
(if (and x y)
(let [x1 (first x)
y1 (first y)]
(cond
( < x1 y1) (recur (next x) y acc)
( > x1 y1) (recur x (next y) acc)
:else (recur (next x) (next y) (conj acc x1))))
acc)))
事实证明,这速度更快(近 10 倍)。
user=> (time (count (intersect-sorted-vector x y)))
"Elapsed time: 40.142532 msecs"
39992
但是,我不禁觉得我的代码过于程序化/迭代。
问题 3:谁能提出一种更惯用的方法来处理 Clojure 中的一对向量?
最佳答案
通常情况下,快速的 Clojure 代码看起来有点势在必行。函数式代码通常很优雅,但会带来一些相关的性能成本,您必须为此付出代价(懒惰、来自丢弃的不可变对象(immutable对象)的额外 GC 压力等)
此外,转换成套装总是会更昂贵。建立一个集合是一个 O(n log n)
操作本身,但您可以利用向量已经支持在 O(n)
中实现交集操作这一事实。时间。
您的代码已经很不错了,但您还可以进行更多优化:
生成的代码可能类似于:
(defn intersect-sorted-vector [x y]
(loop [i (long 0), j (long 0), r (transient [])]
(let [xi (nth x i nil), yj (nth y j nil)]
(cond
(not (and xi yj)) (persistent! r)
(< xi yj) (recur (inc i) j r)
(> xi yj) (recur i (inc j) r)
:else (recur (inc i) (inc j) (conj! r xi))))))
(time (count (intersect-sorted-vector x y)))
=> "Elapsed time: 5.143687 msecs"
=> 40258
如您所见,这可能会给您额外的 6-8 倍加速或大约。
关于vector - 相交两个先验排序向量的惯用/高效Clojure方法?,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/14160830/