title: What are the performance bottlenecks in this code?
body: <p>I have the following Clojure code:</p>
  <pre><code>(ns smallest-sum.core)
  
  (defn next-transformation
    [arr]
    (loop [i 0
           j 0]
      (let [
            arr-len (count arr)
            ]
        (if (and (&lt; i arr-len)
                 (&lt; j arr-len))
          (let [
                  xi (nth arr i)
                  xj (nth arr j)
                  j-plus-1 (+ j 1)
                  i-plus-1 (+ i 1)
                  new-i (if (&lt; j-plus-1 arr-len)
                         i
                         (+ i 1))
                  new-j (if (&lt; j-plus-1 arr-len)
                         (+ j 1)
                         0)
                ]
            (if (&gt; xi xj)
                ;; We found it
                [i j] 
                ;; We haven't found it, recur 
                (recur new-i new-j)
              )
            )
            nil ; We are at the end of the  loop
          ) ; if 
        )
      ) ; loop 
    ) ; defn
  
  (defn solution
    [arr]
    (loop [state {
                  :arr arr 
                  :sum 0
                  }]
        (let [
              cur-arr (get state :arr) 
              trx (next-transformation cur-arr) 
              ]
           ; (println (str &quot;========&quot;))
           ; (println (str &quot;cur-arr: &quot; cur-arr))
           (if (not (= trx nil))
             ;; trx is not nil -- recur
             (let [
                    i (nth trx 0)
                    j (nth trx 1)
                    xi (nth cur-arr i)
                    xj (nth cur-arr j)
                    diff (- xi xj) 
                   ]
                (recur (assoc state :arr (assoc cur-arr
                                                i
                                                diff
                                   )
                             )
                      )            
               )
             ;; Here we need the sum
             (reduce + cur-arr)
             )
          )   
      )
  )
  </code></pre>
  <p>This code must be able to process a large input (example see below) within 120000 milliseconds.</p>
  <p>I assume that one problem are two loops (in <code>solution</code> and <code>next-transformation</code>) which can be unified into one.</p>
  <p><strong>Are there any other performance bottlenecks in this code?</strong></p>
  <p>Here is the test that fails because <code>solution</code> takes more than 120000 milliseconds to run:</p>
  <pre><code>(ns smallest-sum.test
    (:require [smallest-sum.core :refer :all]
              [clojure.test :refer :all]))
              
  (deftest sample-test-cases
    (is (&lt; 0 (solution [
               91293
               38437
               40626
               173
               76990
               17858
               43446
               25050
               10791
               68990
               52403
               21503
               52331
               51909
               73488
               91293
               38437
               40626
               173
               76990
               17858
               43446
               25050
               10791
               68990
               52403
               21503
               52331
               51909
               73488
               91293
               38437
               40626
               173
               76990
               17858
               43446
               25050
               10791
               68990
               52403
               21503
               52331
               51909
               73488
               91293
               38437
               40626
               173
               76990
               17858
               43446
               25050
               10791
               68990
               52403
               21503
               52331
               51909
               73488
                        ])  ))       
  )
  </code></pre>
  <p><strong>Update:</strong> After reading the answers as well as <a href="https://stackoverflow.com/q/16628088/399457">this</a> question I rewrote the code as follows. Now it seems to work (is fast enough).</p>
  <pre><code>(defn gcd
    [a b]
    (if (= b 0)
      a
      (gcd b (mod a b)))
    )
  
  (defn gcd-arr
    [arr]
    (reduce gcd arr) 
    )
  
  (defn solution
    [arr]
    (let [
          greatest-common-divisor (gcd-arr arr)
          arr-len (count arr)
          ]
        (* arr-len greatest-common-divisor) 
      )
    )
  </code></pre>