Идиоматический / эффективный способ Clojure для пересечения двух априори отсортированных векторов?
У меня есть пара векторов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?