numbers - weighted quick union

gistfile1.clj

; attempt 4 - using weighted quick union, always puts the smaller tree under the bigger tree to reduce depth

(def nodes (atom {}))
(def sizes (atom {}))

(defn find-root [i] 
  (let [v (get @nodes i)] 
    (loop [i v]
      (if (= i v) 
        v
        (recur v)))))

(defn values-not-nil? [x y]
  (and (not (nil? x)) (not (nil? y))))

(defn connected? [x y] 
  (let [n @nodes 
        xv (get n x) 
        yv (get n y)] 
    (and (values-not-nil? xv yv) (= xv yv))))

(defn connect! [x y]
  (let [n @nodes 
        xv (get n x) 
        yv (get n y)]
    (when (values-not-nil? xv yv)
      (let [sx (get @sizes x)
            sy (get @sizes y)]
        (if (> sx sy)
          ((swap! nodes assoc x yv)
           (swap! sizes assoc x (+ sx sy)))
          ((swap! nodes assoc y xv)
           (swap! sizes assoc y (+ sy sx))))))))

(defn connect-roots! [x y]
  (let [root-x (find-root x)
        root-y (find-root y)]
    (connect! root-y root-x)))

(defn roots-connected? [x y]
  (let [root-x (find-root x)
        root-y (find-root y)]
    (connected? root-x root-y)))

(defn add-node-to-map! [x]
  (swap! nodes assoc x x)
  (swap! sizes assoc x 1))

 (defn add-node! [x]
   (add-node-to-map! x)
   (connect-roots! x (- x 1))
   (connect-roots! x (+ x 1))
   (roots-connected? 1 x))

; reset the state before running a test
((reset! nodes {}) (reset! sizes {}))

; test for 1 million entries
(map add-node! (shuffle (range 1 1000000)))

; timing functions

(defn tidy-output [x]
  (let [output (clojure.string/replace x "\"Elapsed time: " "")
        output (clojure.string/replace output " msecs\"\n" "")]
    (Double/parseDouble output)))

 (defn time-for-entries [num-entries] 
  (tidy-output (with-out-str (time (doall (for [x (shuffle (range 1 num-entries))] (add-node! x)))))))

; example of running timing function
(time-for-entries 50000)