Function Execution in Clojure 1.3

Question

I was wondering if anyone could help me with the execution of this piece of code in Clojure 1.3. I am trying to implement a simple function that takes two vectors and makes a sum of products.

So, let the vectors X (the size of 10000 elements) and B (the elements of size 3), and the sum of the products is stored in the vector Y, mathematically it looks like this:

Y0 = B0 * X2 + B1 * X1 + B2 * X0

Y1 = B0 * X3 + B1 * X2 + B2 * X1

Y2 = B0 * X4 + B1 * X3 + B2 * X2

etc.

In this example, the size of Y will be 9997, which corresponds to (10,000 - 3). I set a function to accept any size X and B.

Here's the code: it basically takes elements (count b) at a time from X, changes it, maps * to B, and summarizes the contents of the resulting sequence to create an element from Y.

 (defn filt [b-vec x-vec] (loop [n 0 sig x-vec result []] (if (= n (- (count x-vec) (count b-vec))) result (recur (inc n) (rest sig) (conj result (->> sig (take (count b-vec)) (reverse) (map * b-vec) (apply +))))))) 

After X is (vec (range 1 10001)) and B is [1 2 3] , it takes about 6 seconds to complete this function. I was hoping that someone could suggest runtime improvements, be they algorithmic or possibly language details, which I could abuse.

Thanks!

PS I did (set! *warn-on-reflection* true) , but did not receive any warning messages about the reflection.

Answer 1

You use an account many times unnecessary. Only count the counter below once.

 (defn filt [b-vec x-vec] (let [bc (count b-vec) xc (count x-vec)] (loop [n 0 sig x-vec result []] (if (= n (- xc bc)) result (recur (inc n) (rest sig) (conj result (->> sig (take bc) (reverse) (map * b-vec) (apply +)))))))) (time (def b (filt [1 2 3] (range 10000)))) => "Elapsed time: 50.892536 msecs" 

Answer 2

If you really need high performance for this calculation, you should use arrays, not vectors. Arrays have several advantages:

• They support O (1) indexed search and records - marginally better than vectors that are O (log32 n)
• They are mutable, so you do not need to create new arrays all the time - you can just create one array that will serve as the output buffer.
• They are represented as Java arrays under the hood, so use the various array optimizations built into the JVM
• You can use primitive arrays (like Java doubles), which are much faster than if you use objects with box numbers

The code will look something like this:

 (defn filt [^doubles b-arr ^doubles x-arr] (let [bc (count b-arr) xc (count x-arr) rc (inc (- xc bc)) result ^doubles (double-array rc)] (dotimes [i rc] (dotimes [j bc] (aset result i (+ (aget result i) (* (aget x-arr (+ ij)) (aget b-arr j)))))) result)) 

Answer 3

To keep track of Ankur's excellent answer, you can also avoid repeated calls to the callback function, which gives us even more performance.

 (defn filt [b-vec x-vec] (let [bc (count b-vec) xc (count x-vec) bb-vec (reverse b-vec)] (loop [n 0 sig x-vec result []] (if (= n (- xc bc)) result (recur (inc n) (rest sig) (conj result (->> sig (take bc) (map * bb-vec) (apply +))))))))