Идиоматический/эффективный способ 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)))

Это оказывается неплохим (почти 10x) быстрее.

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

Но я не могу не чувствовать, что мой код чрезмерно процедурный/итеративный.

Вопрос 3: Может ли кто-нибудь любезно предложить более идиоматический способ обработки пары векторов в Clojure?

Ответы

Ответ 1

Часто бывает, что быстрый Clojure код выглядит немного императивом. Функциональный код часто изящный, но поставляется с некоторыми связанными с ним эксплуатационными расходами, которые вам приходится платить (лень, дополнительное давление в GC от отброшенных неизменяемых объектов и т.д.).

Кроме того, преобразование в множество всегда будет дороже. Построение набора - это операция O(n log n) сама по себе, но вы можете использовать тот факт, что векторы уже поддерживаются для реализации операции пересечения в O(n) времени.

Ваш код уже очень хорош, но есть еще несколько оптимизаций, которые вы можете сделать:

  • Используйте transient вектор для сбора результатов. Это немного быстрее, чем регулярные постоянные векторы для множества последовательных операций сопряжения.
  • Используется индексированный доступ с примитивами в векторы, а не перемещение последовательности с первой/следующей. Это позволяет избежать создания временных объектов 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-8x или около того.