习惯性/高效的Clojure方式交叉两个先验分类的向量？

Question

我有一对向量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除S (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-sets 的交集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中处理一对向量的更惯用的方法吗？

Answer 1

通常情况下,快速的Clojure代码看起来有点必要.功能代码通常很优雅,但需要支付一些相关的性能成本(懒惰,来自丢弃的不可变对象的额外GC压力等)

此外,转换成套装总是会更昂贵.构建集合O(n log n)本身就是一个操作,但是您可以利用已经支持向量的事实来及时实现交集操作O(n).

您的代码已经非常好了,但您仍可以进行更多优化:

• 使用瞬态向量来收集结果.对于许多连续的conj操作,这些比常规持久向量快一点.
• 使用带有基元的索引访问到向量中,而不是遍历带有first/next的序列.这避免了创建临时seq对象(和相关的GC)

结果代码可能类似于:

(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 (or 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倍的加速比.