Clojure translate from Java

Question

I'm starting to learn Clojure and have decided that doing some projects on HackerRank is a good way to do that. What I'm finding is that my Clojure solutions are horribly slow. I'm assuming that's because I'm still thinking imperatively or just don't know enough about how Clojure operates. The latest problem I wrote solutions for was Down To Zero II. Here's my Java code

import java.io.BufferedReader;
import java.io.InputStreamReader;

public class Solution {
    private static final int MAX_NUMBER = 1000000;
    private static final BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));

    public static int[] precompute() {
        int[] values = new int[MAX_NUMBER];

        values[0] = 0;
        values[1] = 1;

        for (int i = 1; i < MAX_NUMBER; i += 1) {
            if ((values[i] == 0) || (values[i] > (values[i - 1] + 1))) {
                values[i] = (values[i - 1] + 1);
            }

            for (int j = 1; j <= i && (i * j) < MAX_NUMBER; j += 1) {
                int mult = i * j;

                if ((values[mult] == 0) || (values[mult] > (values[i] + 1))) {
                    values[mult] = values[i] + 1;
                }
            }
        }

        return values;
    }

    public static void main(String[] args) throws Exception {
        int numQueries = Integer.parseInt(reader.readLine());

        int[] values = Solution.precompute();

        for (int loop = 0; loop < numQueries; loop += 1) {
            int query = Integer.parseInt(reader.readLine());
            System.out.println(values[query]);
        }
    }
}

My Clojure implementation is

(def MAX-NUMBER 1000000)

(defn set-i [out i]
(cond
    (= 0 i) (assoc out i 0)
    (= 1 i) (assoc out i 1)
    (or (= 0 (out i))
        (> (out i) (inc (out (dec i)))))
    (assoc out i (inc (out (dec i))))
    :else out))

(defn set-j [out i j]
(let [mult (* i j)]
    (if (or (= 0 (out mult)) (> (out mult) (inc (out i))))
    (assoc out mult (inc (out i)))
    out)))

;--------------------------------------------------
; Precompute the values for all possible inputs
;--------------------------------------------------
(defn precompute []
(loop [i 0 out (vec (repeat MAX-NUMBER 0))]

    (if (< i MAX-NUMBER)
    (recur (inc i) (loop [j 1 new-out (set-i out i)]
                    (if (and (<= j i) (< (* i j) MAX-NUMBER))
                        (recur (inc j) (set-j new-out i j))
                        new-out)))
    out)))

;--------------------------------------------------
; Read the number of queries
;--------------------------------------------------
(def num-queries (Integer/parseInt (read-line)))

;--------------------------------------------------
; Precompute the solutions
;--------------------------------------------------
(def values (precompute))

;--------------------------------------------------
; Read and process each query
;--------------------------------------------------
(loop [iter 0]
(if (< iter num-queries)
    (do
    (println (values (Integer/parseInt (read-line))))
    (recur (inc iter)))))

The Java code runs in about 1/10 of a second on my machine, while the Clojure code takes close to 2 seconds. Since it's the same machine, with the same JVM, it means I'm doing something wrong in Clojure.

How do people go about trying to translate this type of code? What are the gotchas that are causing it to be so much slower?

user_1698485 · Answer

I'm going to do some transformations to your code (which might be slightly outside of what you were originally asking) and then address your more specific questions.

I know it's almost two years later, but after running across your question and spending way too much time fighting with HackerRank and its time limits, I thought I would post an answer. Does achieving a solution within HR's environment and time limits make us better Clojure programmers? I didn't learn the answer to that. But I'll share what I did learn.

I found a slightly slimmer version of your same algorithm. It still has two loops, but the update only happens once in the inner loop, and many of the conditions are handled in a min function. Here is my adaptation of it:

(defn compute
  "Returns a vector of down-to-zero counts for all numbers from 0 to m."
  [m]
  (loop [i 2 out (vec (range (inc m)))]
    (if (<= i m)
      (recur (inc i)
             (loop [j 1 out out]
               (let [ij (* i j)]
                 (if (and (<= j i) (<= ij m))
                   (recur (inc j) 
                          (assoc out ij (min (out ij)               ;; current value
                                             (inc (out (dec ij)))   ;; steps from value just below
                                             (inc (out i)))))       ;; steps from a factor
                   out))))
      out)))

Notice we're still using loop/recur (twice), we're still using a vector to hold the output. But some differences:

We initialize out to incrementing integers. This is the worst case number of steps for every value, and once initialized, we don't have to test that a value equals 0 and we can skip indices 0 and 1 and start the outer loop at index 2. (We also fix a bug in your original and make sure out contains MAX-NUMBER+1 values.)
All three tests happen inside a min function that encapsulates the original logic: a value will be updated only if it's a shorter number of steps from the number just below it, or from one of it's factors.
The tests are now simple enough that we don't need to break them out into separate functions.

This code (along with your original) is fast enough to pass some of the test cases in HR, but not all. Here are some things to speed this up:

Use int-array instead of vec. This means we'll use aset instead of assoc and aget instead of calling out with an index. It also means that loop/recur isn't the best structure anymore (because we are no longer passing around new versions of an immutable vector, but actually mutating a java.util.Array); instead we'll use doseq.
Type hints. This alone makes a huge speed difference. When testing your code, include a form at the top (set! *warn-on-reflection* true) and you'll see where Clojure is having to do extra work to figure out what types it is dealing with.
Use custom I/O functions to read the input. HR's boilerplate I/O code is supposed to let you focus on solving the challenge and not worry about I/O, but it is basically garbage, and often the culprit behind your program timing out.

Below is a version that incorporates the tips above and runs fast enough to pass all test cases. I've included my custom I/O approach that I've been using for all my HR challenges. One nice benefit of using doseq is we can include a :let and a :while clause within the binding form, removing some of the indentation within the body of doseq. Also notice a few strategically placed type hints that really speed up the program.

(ns down-to-zero-int-array)

(set! *warn-on-reflection* true)

(defn compute
  "Returns a vector of down-to-zero counts for all numbers from 0 to m."
  ^ints [m]
  (let [out ^ints (int-array (inc m) (range (inc m)))]
    (doseq [i (range 2 (inc m)) j (range 1 (inc i)) :let [ij (* i j)] :while (<= ij m)]
      (aset out ij (min (aget out ij)
                        (inc (aget out (dec ij)))
                        (inc (aget out i)))))
    out))

(let [tokens ^java.io.StreamTokenizer 
      (doto (java.io.StreamTokenizer. (java.io.BufferedReader. *in*))
        (.parseNumbers))]
  (defn next-int []
    "Read next integer from input. As fast as `read-line` for a single value, 
     and _much_ faster than `read-line`+`split` for multiple values on same line."
    (.nextToken tokens)
    (int (.-nval tokens))))

(def MAX 1000000)

(let [q (next-int)
      down-to-zero (compute MAX)]
  (doseq [n (repeatedly q next-int)]
    (println (aget down-to-zero n))))

Clojure translate from Java

1 Answers