3n+1 Programming challenge in clojure. (Clojure is fast!)

Standard

My cousin was solving a programming challenge involving the collatz conjecture. He was implementing his solution using dynamic programming in C++

I thought it would be fun to try and write it in Clojure.

Our solutions are pretty similar, and mine ended up being about 2 times slower than his.

 

 

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

(defn check-len*
  ([l cache] (check-len* l cache 1))
  ([k cache len]
  (loop [k (long k)
         len (long len)]
    (let [val (get cache k)
          is-even (even? k)]
      (if val
        (unchecked-dec (unchecked-add len (long val)))
        (if (== k (long 1)) len
              (recur (long (if is-even
                             (bit-shift-right (long k) (long 1))
                             (unchecked-add (long k) 
                                     (unchecked-add (long 1)
                                     (long (bit-shift-right k 1))))))
                     (long (if is-even
                             (unchecked-inc len)
                             (unchecked-add len (long 2)))))))))))

(defn check-max [a b]
    (loop [i (long a)
           max (long 0)
           cache {}]
      (if (>= i b) max
        (let [val (check-len* i cache)]
          (recur (inc i)
                 (long (if (> val max) val max))
                 (assoc cache i val))))))

(defn go [beg end]
  (time (check-max beg end)))

 

 

As of memory, for the range 1-10,000,000 I am using 1.7gb of heap memory, while the C++ implementation is using 1.2gb.
My implementation is 42% beefier. and 2x slower. But it’s smaller!

Since almost half the time is spent putting and getting values from the clojure map, using a Java HashMap is an improvement, and actually makes the solution faster than the C++ version. (Memory-wise, it settles on less than 1.2gb after the solution, but just before it finishes it reaches 1.4gb)

 

 

(set! *warn-on-reflection* true)
(import '(java.util HashMap))

(defn check-len*
  ([l #^HashMap cache] (check-len* l cache 1))
  ([k #^HashMap cache len]
  (loop [k (long k)
         len (long len)]
    (let [val (. cache get k)
          is-even (even? k)]
      (if val
        (unchecked-dec (unchecked-add len (long val)))
        (if (== k (long 1)) len
              (recur (long (if is-even
                             (bit-shift-right (long k) (long 1))
                             (unchecked-add (long k) 
                                    unchecked-add (long 1)
                                   (long (bit-shift-right k 1))))))
                     (long (if is-even
                             (unchecked-inc len)
                             (unchecked-add len (long 2)))))))))))

(defn check-max [a b]
    (loop [i (long a)
           max (long 0)
           cache (new HashMap)]
      (if (>= i b) max
        (let [val (check-len* i cache)]
          (. cache put i val)
          (recur (inc i)
                 (long (if (> val max) val max))
                 cache)))))

(defn go [beg end]
  (time (check-max beg end)))

An all-around better solution is to use the optimization tips on the wikipedia article for the Collatz Conjecture, which would reduce it to some arithmetic trickery.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s