c++ - 您将如何在 Clojure 中编写此 C++ 循环？

Question

虽然我以前用函数式语言做过一些小的编程，但我才刚刚开始使用 Clojure。由于在学习一门新语言时做同样的“Hello World”程序会变得很老，我决定通过 Cinder “你好，Cinder”教程，将其翻译成 Clojure 和 Quil一路上。在 Chapter 5在本教程的最后，您会看到这个 C++ 片段来计算粒子列表的加速度:

void ParticleController::repulseParticles() {
    for( list<Particle>::iterator p1 = mParticles.begin(); p1 != mParticles.end(); ++p1 ) {
        list<Particle>::iterator p2 = p1;
        for( ++p2; p2 != mParticles.end(); ++p2 ) {
            Vec2f dir = p1->mLoc - p2->mLoc;
            float distSqrd = dir.lengthSquared();

            if( distSqrd > 0.0f ){
                dir.normalize();
                float F = 1.0f/distSqrd;

                p1->mAcc += dir * ( F / p1->mMass );
                p2->mAcc -= dir * ( F / p2->mMass );
            }
        }
    }
}

在我看来，这段代码有一个非常重要的特征:它在成对的粒子之间进行比较并更新两个粒子，然后在以后跳过相同的组合。出于性能原因，这非常重要，因为这段代码每帧执行一次，并且在任何给定时间屏幕上可能有数千个粒子(比我更了解大 O 的人可能会告诉你这种方法之间的区别并多次迭代每个组合)。

作为引用，我将展示我的想法。你应该注意到下面的代码一次只更新一个粒子，所以我做了很多“额外”的工作来比较相同的粒子两次。 (注意:为简洁起见省略了一些方法，例如“规范化”):

(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 (> 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))

更新:如果有人感兴趣的话，这是我最终想出的:

(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)))

基本上，这个过程是这样的:

1. 粒子组合:使用组合学“组合”函数计算粒子的所有组合
2. new-accelerations:根据组合列表计算加速度列表
3. new-accelerations-grouped:通过遍历每个粒子并检查组合列表，将每个粒子的加速度(按顺序)分组，构建一个列表列表，其中每个子列表都是所有单独的加速度；还有一个微妙之处是，如果粒子是组合列表中的第一个条目，它会获得原始加速度，但如果是第二个，它会获得相反的加速度。然后过滤掉 nils
4. 将每个加速度子列表缩减为这些加速度的总和

现在的问题是，这是否比我之前做的更快？ (我还没有测试过，但我的初步猜测是不可能的)。

更新 2: 这是我想出的另一个版本。我认为这个版本在所有方面都比我上面发布的版本好得多:它使用 transient 数据结构来提高性能/新列表的易变性，并使用循环/递归。它应该比我上面发布的示例快得多，但我还没有测试验证。

(defn transient-particle-accelerations [particles]
  (let [num-of-particles (count particles)]
    (loop [i 0 new-particles (transient particles)]
      (if (< i (- num-of-particles 1))
        (do 
          (loop [j (inc i)]
            (if (< 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)))))

Answer 1

当你想更新它们时重新def-ing 粒子似乎不太正确——我猜测使用 ref 来存储世界状态，然后更新它循环之间的引用，会更有意义。

归结为算法问题，对我来说这是 clojure.math.combinatorics 的一个用例.类似于以下内容:

(require '[clojure.math.combinatorics :as combinatorics])

(defn update-particles [particles]
  (apply concat
    (for [[p1 p2] (combinatorics/combinations particles 2)
          :let [x-distance-between (- (:x p1) (:x p2))
                y-distance-between (- (:y p1) (:y p2))
                distance-squared (+ (* x-distance-between x-distance-between)
                                    (* y-distance-between y-distance-between))
                normalized-direction (normalize x-distance-between y-distance-between)
                p1-force (if (> distance-squared 0)
                             (/ (/ 1.0 distance-squared) (:mass p1))
                          0)]]
     [{:x (+ (:x (:accel p1)) (* (first normalized-direction) p1-force))
       :y (+ (:y (:accel p1)) (* (first normalized-direction) p1-force))}
      {:x (+ (:x (:accel p2)) (* (first normalized-direction) p2-force))
       :y (+ (:y (:accel p2)) (* (first normalized-direction) p2-force))}]))

...您仍然需要 reduce，但通过这种方式，我们可以将两个粒子的更新值拉出循环。