CODEWITHSUNDEEP
clojure
dagda1
dagda1

Reputation: 28770

clojure performance on badly performing code

I have completed this problem on hackerrank and my solution passes most test cases but it is not fast enough for 4 out of the 11 test cases.

My solution looks like this:

(ns scratch.core
  (require [clojure.string :as str :only (split-lines join split)]))

(defn ascii [char]
  (int (.charAt (str char) 0)))

(defn process [text]
  (let [parts (split-at (int (Math/floor (/ (count text) 2))) text)
        left (first parts)
        right (if (> (count (last parts)) (count (first parts)))
                (rest (last parts))
                (last parts))]

    (reduce (fn [acc i]
              (let [a (ascii (nth left i))
                    b (ascii (nth (reverse right) i))]
                (if (> a b)
                  (+ acc (- a b))
                  (+ acc (- b a))))
              ) 0 (range (count left)))))

(defn print-result [[x & xs]]
  (prn x)
  (if (seq xs)
    (recur xs)))

(let [input (slurp "/Users/paulcowan/Downloads/input10.txt")
      inputs (str/split-lines input)
      length (read-string (first inputs))
      texts (rest inputs)]
  (time (print-result (map process texts))))

Can anyone give me any advice about what I should look at to make this faster?

Would using recursion instead of reduce be faster or maybe this line is expensive:

right (if (> (count (last parts)) (count (first parts)))
                (rest (last parts))
                (last parts))

Because I am getting a count twice.

Upvotes: 1

Views: 85

Answers (1)

noisesmith
noisesmith

Reputation: 20194

You are redundantly calling reverse on every iteration of the reduce:

user=> (let [c [1 2 3]
             noisey-reverse #(doto (reverse %) println)]
         (reduce (fn [acc e] (conj acc (noisey-reverse c) e))
                 []
                 [:a :b :c]))
(3 2 1)
(3 2 1)
(3 2 1)
[(3 2 1) :a (3 2 1) :b (3 2 1) :c]

The reversed value could be calculated inside the containing let, and would then only need to be calculated once.

Also, due to the way your parts is defined, you are doing linear time lookups with each call to nth. It would be better to put parts in a vector and do indexed lookup. In fact you wouldn't need a reversed parts, and could do arithmetic based on the count of the vector to find the item to look up.

Upvotes: 3

Related Questions