В ближайшем будущем, как эффективен способ свертывания вектора ядром?

Question

Я придумал это:

(def kernel [0 1 1 2 3 3 0 0 0 0 0 0])
(def data [1 5 7 4 8 3 9 5 6 3 2 1 1 7 4 9 3 2 1 8 6 4])

(defn capped+ [a b c] (let [s (+ a b)] (if (> s c) c s)))

(defn *+ [a b]
  (if (> (count a) (count b))  
    (reduce + (map-indexed (fn _ [i x] (* (a i) (b i))) b))
    (reduce + (map-indexed (fn _ [i x] (* (a i) (b i))) a))))

(defn slide*i [d k] 
 (let [ki (into [] (reverse k)) kl (count k) dl (count d)]
   (map-indexed 
      (fn [idx item] 
        (/ (*+ ki (subvec d idx (capped+ idx kl dl))) 
           (reduce + ki))) 
      d)))

(def s (slide*i data kernel))

Это не самый элегантный код, но он отлично работает.Я на самом деле хочу использовать это, чтобы сгладить некоторые очень колючие!data.

Приветствуются любые предложения, чтобы сделать это более красивым, более эффективным или более точным (лично мне все равно, что хвост неточный, потому что в моем случае я им никогда не пользуюсь)

Answer 1

Вы, безусловно, можете значительно улучшить производительность этой операции.Хорошая новость заключается в том, что вам не нужно заходить в Java для этого: Clojure чрезвычайно быстр, если вы правильно его оптимизируете, и в большинстве случаев может производить ту же скорость, что и чистая Java.

Для максимальной производительности числовойкод в Clojure, который вы захотите использовать:

• массивы , потому что вам требуется изменяемое хранилище с очень быстрой записью и поиском.Последовательности и векторы Clojure прекрасны, но они идут с накладными расходами, которых вы, вероятно, хотите избежать для действительно критичного к производительности кода
• double примитивов, потому что они предлагают намного более быстрые математические вычисления.
• aset / aget / areduce - это чрезвычайно быстрые операции, разработанные для массивов, которые в основном дают тот же байт-код, что и чистые эквиваленты Java.
• императивный стиль - хотяв Clojure он недиоматичен, он дает самые быстрые результаты (в основном потому, что вы можете избежать накладных расходов из-за выделения памяти, упаковки и вызовов функций).В качестве примера можно использовать dotimes для быстрого императивного цикла.
• (установите! * Warn-on-отражение * true) - и исключите все предупреждения, которые выдает ваш кодпотому что рефлексия сильно снижает производительность.

Следующее должно быть в правильном направлении и, вероятно, даст вам примерно эквивалентную производительность Java:

(def kernel (double-array [0 1 1 2 3 3 0 0 0 0 0 0]))
(def data (double-array [1 5 7 4 8 3 9 5 6 3 2 1 1 7 4 9 3 2 1 8 6 4]))

(defn convolve [^doubles kernel-array ^doubles data-array]
  (let [ks (count kernel-array)
        ds (count data-array)
        output (double-array (+ ks ds))
        factor (/ 1.0 (areduce kernel-array i ret 0.0 (+ ret (aget kernel-array i))))]    
    (dotimes [i (int ds)]
      (dotimes [j (int ks)]
        (let [offset (int (+ i j))]
          (aset output offset (+ (aget output offset) (* factor (* (aget data-array i) (aget kernel-array j))))))))
    output))

(seq (convolve kernel data))
=> (0.0 0.1 0.6 1.4 2.4 4.4 5.5 6.1000000000000005 5.600000000000001 6.200000000000001 5.499999999999999 5.9 4.199999999999999 3.3000000000000003 2.5 2.2 3.3 4.4 5.6000000000000005 4.8 4.8999999999999995 3.1 3.5 4.300000000000001 5.0 3.0 1.2000000000000002 0.0 0.0 0.0 0.0 0.0 0.0 0.0)

У меня нетобрезать выходной массив или делать какие-либо ограничения, так что вам, вероятно, придется немного взломать это решение, чтобы получить именно тот результат, который вы хотите, но, надеюсь, вы поймете идею .....

Некоторые очень грубые тесты производительности:

(time (dotimes [i 1000] (seq (convolve kernel data))))
=> "Elapsed time: 8.174109 msecs"

то есть это около 30 нс для каждой комбинации ядро ​​/ пара данных - я ожидаю, что это в значительной степени выходит за границы доступа к кешированной памяти.

Answer 2

; unused, but left for demonstration
(defn capped+ [a b c]
  (min (+ a b) c))

(defn *+ [a b]
  (reduce + (map * a b)))

(defn slide*i [d k]
  (let [ki (reverse k)
        kl (count k)
        ks (reduce + k)]
    (map #(/ (*+ %1 ki) ks) (partition kl 1 d))))

С partition результаты:

(59/10 21/5 33/10 5/2 11/5 33/10 22/5 28/5 24/5 49/10 31/10)

Но с partition-all вы получите именно то, к чему привело ваше решение:

(59/10 21/5 33/10 5/2 11/5 33/10 22/5 28/5 24/5 49/10 31/10 7/2 43/10 5 3 6/5 0 0 0 0 0 0)

Answer 3

Эффективный способ сделать это - создать класс Java, который выполняет свертку, и вызывать его из clojure, передавая ему массив Java, если это возможно. Внедрение Clojure должно работать и на Java-массивах, если важна эффективность.