title: How Would You Write This C++ Loop in Clojure?
body: <p>Although I've done some small amount of programming in functional languages before, I've just started playing with Clojure. Since doing the same kind of "Hello World" programs gets old when learning a new language, I decided to go through the <a href="http://libcinder.org/" rel="nofollow">Cinder</a> "Hello, Cinder" tutorial, translating it to Clojure and <a href="https://github.com/quil/quil" rel="nofollow">Quil</a> along the way. In <a href="http://libcinder.org/docs/v0.8.2/hello_cinder_chapter5.html" rel="nofollow">Chapter 5</a> of the tutorial, you come across this C++ snippet to calculate acceleration for a list of particles:</p>
  
  <pre class="lang-cpp prettyprint-override"><code>void ParticleController::repulseParticles() {
      for( list&lt;Particle&gt;::iterator p1 = mParticles.begin(); p1 != mParticles.end(); ++p1 ) {
          list&lt;Particle&gt;::iterator p2 = p1;
          for( ++p2; p2 != mParticles.end(); ++p2 ) {
              Vec2f dir = p1-&gt;mLoc - p2-&gt;mLoc;
              float distSqrd = dir.lengthSquared();
  
              if( distSqrd &gt; 0.0f ){
                  dir.normalize();
                  float F = 1.0f/distSqrd;
  
                  p1-&gt;mAcc += dir * ( F / p1-&gt;mMass );
                  p2-&gt;mAcc -= dir * ( F / p2-&gt;mMass );
              }
          }
      }
  }
  </code></pre>
  
  <p>In my eyes, this code has one very important characteristic: it is doing comparisons between pairs of particles and updating both particles and then skipping the same combination in the future. This is very important for performance reasons, since this piece of code is executed once every frame and there are potentially thousands of particles on screen at any given time (someone who understands big O better than I do can probably tell you the difference between this method and iterating over every combination multiple times).</p>
  
  <p>For reference, I'll show what I came up with. You should notice that the code below only updates one particle at a time, so I'm doing a lot of "extra" work comparing the same particles twice. (Note: some methods left out for brevity, such as "normalize"):</p>
  
  <pre class="lang-lisp prettyprint-override"><code>(defn calculate-acceleration [particle1 particle2]
    (let [x-distance-between (- (:x particle1) (:x particle2))
          y-distance-between (- (:y particle1) (:y particle2))
          distance-squared (+ (* x-distance-between x-distance-between) (* y-distance-between y-distance-between))
          normalized-direction (normalize x-distance-between y-distance-between)
          force (if (&gt; distance-squared 0) (/ (/ 1.0 distance-squared) (:mass particle1)) 0)]
      {:x (+ (:x (:accel particle1)) (* (first normalized-direction) force)) :y (+ (:y (:accel particle1)) (* (second normalized-direction) force))}))
  
  (defn update-acceleration [particle particles]
    (assoc particle :accel (reduce #(do {:x (+ (:x %) (:x %2)) :y (+ (:y %) (:y %2))}) {:x 0 :y 0} (for [p particles :when (not= particle p)] (calculate-acceleration particle p)))))
  
  (def particles (map #(update-acceleration % particles) particles))
  </code></pre>
  
  <p><strong>Update</strong>: So here's what I ultimately came up with, in case anyone is interested:</p>
  
  <pre class="lang-lisp prettyprint-override"><code>(defn get-new-accelerations [particles]
    (let [particle-combinations (combinations particles 2)
          new-accelerations (map #(calculate-acceleration (first %) (second %)) particle-combinations)
          new-accelerations-grouped (for [p particles]
                                      (filter #(not (nil? %)) 
                                              (map 
                                                #(cond (= (first %) p) %2
                                                       (= (second %) p) (vec-scale %2 -1))
                                                particle-combinations new-accelerations)))]
      (map #(reduce (fn [accum accel] (if (not (nil? accel)) (vec-add accel accum))) {:x 0 :y 0} %) 
           new-accelerations-grouped)))
  </code></pre>
  
  <p>Essentially, the process goes something like this:</p>
  
  <ol>
  <li>particle-combinations: Calculate all combinations of particles using the combinatorics "combinations" function</li>
  <li>new-accelerations: Calculate a list of accelerations based on the list of combinations</li>
  <li>new-accelerations-grouped: Group up the accelerations for each particle (in order) by looping over every particle and checking the list of combinations, building a list of lists where each sub-list is all of the individual accelerations; there's also the subtlety that if the particle is the first entry in the combination list, it gets the original acceleration, but if it's the second, it gets the opposite acceleration. It then filters out nils</li>
  <li>Reduce each sub-list of accelerations to the sum of those accelerations</li>
  </ol>
  
  <p>The question now is, is this any faster than what I was doing before? (I haven't tested it yet, but my initial guess is no way).</p>
  
  <p><strong>Update 2:</strong>
  Here's another version I came up with. I think this version is much better in all respects than the one I posted above: it uses a transient data structure for performance/easy mutability of the new list, and uses loop/recur. It should be much faster than the example I posted above but I haven't tested yet to verify.</p>
  
  <pre class="lang-lisp prettyprint-override"><code>(defn transient-particle-accelerations [particles]
    (let [num-of-particles (count particles)]
      (loop [i 0 new-particles (transient particles)]
        (if (&lt; i (- num-of-particles 1))
          (do 
            (loop [j (inc i)]
              (if (&lt; j num-of-particles)
                (let [p1 (nth particles i)
                      p2 (nth particles j)
                      new-p1 (nth new-particles i)
                      new-p2 (nth new-particles j)
                      new-acceleration (calculate-acceleration p1 p2)]
                  (assoc! new-particles i (assoc new-p1 :accel (vec-add (:accel new-p1) new-acceleration)))
                  (assoc! new-particles j (assoc new-p2 :accel (vec-add (:accel new-p2) (vec-scale new-acceleration -1))))
                  (recur (inc j)))))
            (recur (inc i) new-particles))
          (persistent! new-particles)))))
  </code></pre>