成语/高效Clojure的方式相交两个先验分类引导？(Idiomatic/Efficient Clo

我有一对向量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代码看起来有点势在必行的情况。功能代码往往是优雅的，但附带了，你必须为此付出代价（从废弃的不可变对象等懒惰，额外的GC压力）的一些相关的性能开销

此外，转换成集总是会更贵。建设集是O(n log n)操作本身，但是你可以利用该载体已经被支持，以实现一个交集操作的事实， O(n)时间。

您的代码已经是相当不错的，但仍有一对夫妇更多的优化，你可以这样做：

使用瞬时矢量收集的结果。这是比许多连续连词操作的常规持续向量更快一点。
使用原语到矢量索引访问，而不是与第一/下一个遍历序列。这避免了创建临时序列对象（和相关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-8x加速左右。