CODEWITHSUNDEEP
clojure
Chris Murphy
Chris Murphy

Reputation: 6509

Speeding up Clojure to avoid timeouts

I've doing a few of the hackerrank challenges and noticing that I seem to not be able to code efficient code, as quite often I get timeouts, even though the answers that do pass the tests are correct. For example for this challenge this is my code:

(let [divisors (fn [n] (into #{n} (into #{1} (filter (comp zero? (partial rem n)) (range 1 n)))))
      str->ints (fn [string]
                  (map #(Integer/parseInt %)
                       (clojure.string/split string #" ")))
      ;lines (line-seq (java.io.BufferedReader. *in*))
      lines ["3"
             "10 4"
             "1 100"
             "288 240"
             ]
      pairs (map str->ints (rest lines))
      first-divs (map divisors (map first pairs))
      second-divs (map divisors (map second pairs))
      intersections (map clojure.set/intersection first-divs second-divs)
      counts (map count intersections)
  ]
  (doseq [v counts]
    (println (str v))))

Note that clojure/set doesn't exist at hackerrank. I just put in here for the sake of brevity.

Upvotes: 0

Views: 87

Answers (1)

leetwinski
leetwinski

Reputation: 17859

in this exact case there is an obvious misuse of map function: although the clojure collections are lazy, operations on them still don't come for free. So when you chain lots of maps, you still have all the intermediate collections (there are 7 here). To avoid this, one would usually use transducers, but in your case you are just mapping every input line to one output line, so it is really enough to do it in one pass over the input collection:

(let [divisors (fn [n] (into #{n} (into #{1} (filter (comp zero? (partial rem n)) (range 1 n)))))
      str->ints (fn [string]
                  (map #(Integer/parseInt %)
                       (clojure.string/split string #" ")))
                       ;lines (line-seq (java.io.BufferedReader. *in*))
      get-counts (fn [pair] (let [d1 (divisors (first pair))
                                  d2 (divisors (second pair))]
                              (count (clojure.set/intersection d1 d2))))
      lines ["3"
             "10 4"
             "1 100"
             "288 240"
             ]
      counts (map (comp get-counts str->ints) (rest lines))]
  (doseq [v counts]
    (println (str v))))

Not talking about the correctness of the whole algorithm here. Maybe it could also be optimized. But as of clojure's mechanics, this change should speed up your code quite notably.

update

as for the algorithm, you would probably want to start with limiting the range from 1..n to 1..(sqrt n), adding both x and n/x into resulting set when x is a divisor of n, that should give you quite a big profit for large numbers:

(defn divisors [n]
  (into #{} (mapcat #(when (zero? (rem n %)) [% (/ n %)])
                    (range 1 (inc (Math/floor (Math/sqrt n)))))))

also i would consider finding all the divisors of the least of two numbers, and then keeping the ones the other number is divisible by. This will eliminate the search of the greater number's divisors.

(defn common-divisors [pair]
  (let [[a b] (sort pair)
        divs (divisors a)]
    (filter #(zero? (rem b %)) divs)))

if that still doesn't manage to pass the test, you should probably look for some nice algorithm for common divisors.

update 2

submitted the updated algorithm to hackerrank and it passes well now

Upvotes: 3

Related Questions