Tengo un par de vectoresx yy De artículos únicos, cada uno de los cuales sé que deben ser ordenados. Deseo tener la intersección de los dos, manteniendo el orden. El resultado sería idealmente otro vector, para un acceso aleatorio rápido.

La siguiente generación es meramente por ejemplo, mix yy Vendrán precortados y predefinidos (en realidad son muestras de tiempo).

(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

Sé que Clojure tieneclojure.set/intersection que puede trabajar en unsorted-set. Mix yy tienen las mismas propiedades (elementos distintos ordenados) pero no son del mismo tipo.

Pregunta 1: ¿Hay una forma mejor / más rápida de convertir?x yy asorted-sets que(apply sorted-set x) Dado que ya son distintos y ordenados?

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"

Ahora estoy listo para realizar mi intersección

user=> (time (count (clojure.set/intersection ssx ssy)))
"Elapsed time: 355.42534 msecs"
39992

Este es un rendimiento algo decepcionante, y una mirada superficial a(source clojure.set/intersection) No parece mostrar ningún tratamiento especial por el hecho de que estos conjuntos están ordenados.

Pregunta 2: ¿Existe una forma mejor / más rápida de realizar la intersección desorted-sets queclojure.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)))

Esto resulta ser mucho más rápido (casi 10 veces).

user=> (time (count (intersect-sorted-vector x y)))
"Elapsed time: 40.142532 msecs"
39992

Pero no puedo evitar sentir que mi código es excesivamente procesal / iterativo.

Pregunta 3: ¿Podría alguien sugerir amablemente una manera más idiomática de procesar un par de vectores en Clojure?