У меня есть пара векторов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?