在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序列和向量很漂亮,但它们带来了您可能希望避免的真正性能关键代码的开销
• 双原语,因为它们提供了更快的数学.
• aset/aget/areduce - 这些是为数组设计的极其快速的操作,基本上为您提供与纯Java等价物相同的字节码.
• 命令式的风格 - 尽管它在Clojure中是单一的,它可以获得最快的结果(主要是因为你可以避免内存分配,装箱和函数调用的开销).一个例子是使用dotimes进行快速命令循环.
• (设置!*warn-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"

即每个内核/数据对组合大约30ns - 我希望它几乎达到了缓存内存访问的范围.