В clojure, каков эффективный способ свертки вектора с помощью ядра?

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)) 

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

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

Answer 1

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

Для достижения максимальной производительности цифрового кода в Clojure вы хотите использовать:

• массивы, потому что вы хотите изменяемое хранение с очень быстрой записью и поиском. Clojure последовательности и векторы красивы, но они приходят с накладными расходами, которые вы, вероятно, хотите избежать для действительно критически важного кода
• double примитивы, потому что они предлагают гораздо более быструю математику.
• aset/aget/areduce - это чрезвычайно быстрые операции, предназначенные для массивов, и в основном дают вам тот же байт-код, что и чистые эквиваленты Java.
• императивный стиль - хотя он является унииоматическим в Clojure, он получает самые быстрые результаты (главным образом потому, что вы можете избежать накладных расходов из распределения памяти, бокса и вызовов функций). Примером может служить dotimes для быстрого императивного цикла.
• (set! * Warning-on-reflection * 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

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

Answer 3

 
; 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)