Performance of vector and array in Clojure

Question

I am trying to solve the Maximum subarray problem on hacker rank. This is a standard DP problem and I write an O(n) solution:

(defn dp
  [v]
  (let [n (count v)]
    (loop [i 1 f (v 0) best f]
      (if (< i n) 
        (let [fi (max (v i) (+ f (v i)))]
          (recur (inc i) fi (max fi best)))
        best))))


(defn positive-only
  [v]
  (reduce + (filterv #(> % 0) v)))


(defn line->ints
  [line]
  (->> 
   (clojure.string/split line #" ")
   (map #(Integer. %))
   (into [])
   ))


(let [T (Integer. (read-line))]
  (loop [test 0]
    (when (< test T)
      (let [_ (read-line)
            x (read-line)
            v (line->ints x)
            a (dp-array v)
            b (let [p (positive-only v)]
                (if (= p 0) (reduce max v) p))]
        (printf "%d %d\n" a b))
      (recur (inc test)))))

To my surprise, I got time-limited-exceed for a large test case. I downloaded the input file, and found that the above version needs about 3 seconds to run.

I thought the bottleneck is in (v i) (getting the i-th element in vector v). So I changed the data structure from vector to an array:

(defn dp-array
  [v0]
  (let [v (into-array v0)
        n (int (alength v))]
    (loop [i 1
           f (aget v 0)
           best f]
      (if (< i n) 
        (let [fi (max (aget v i) (+ f (aget v i)))]
          (recur (inc i) fi (max fi best)))
        best))))

This array version is even slower. On the same input, it costs 33 seconds, much slower than the vector version. I think the slowness is due to boxing and unboxing. I tried to add type hints, but encountered run-time errors. Could anyone help me improve dp-array function? Thanks!

Also, great appreciate if anyone knows how to improve the vector version.

UPDATE:

Finally I managed to get my clojure program accepted, not by optimizing over the dynamic programming function, but by changing (Integer. str) to (Integer/parseInt str). In this way, reflection is avoided in converting from string to integer.

I also replace into-array by int-array. But the speed of both versions are still on par with each other. I would expect the array version be faster than the vector version.

a better definition for positive-only: #(apply + (filter pos? %)) — noisesmith
– noisesmith, Commented Apr 6, 2015 at 17:20
You may see better performance from dp-array if you explicitly make an int-array for v, otherwise you'll end up with boxed and generic math that could be specialized for int. — noisesmith
– noisesmith, Commented Apr 6, 2015 at 17:24
I suspect your problem is with reflection, not with boxing/unboxing. — Alex
– Alex, Commented Apr 6, 2015 at 17:26
@Alex if the array isn't hinted, you'll see both reflection and boxing/unboxing, and the fix for reflection also fixes the boxing issue. — noisesmith
– noisesmith, Commented Apr 6, 2015 at 17:40

tnoda · Accepted Answer · 2015-04-07 08:36:16Z

2

The Clojure compiler can't infer the type of v in the array version of the dp-array function whose argument v0 has unknown type. This causes costs to reflections when evaluating the following alength and aget. In order to avoid these unnecessary reflections, you have to replace into-array with long-array.

answered Apr 7, 2015 at 8:36

tnoda

1,5349 silver badges18 bronze badges

Sign up to request clarification or add additional context in comments.

Collectives™ on Stack Overflow

Performance of vector and array in Clojure

1 Answer 1

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

Comments

Your Answer

Sign up or log in

Post as a guest

Related