虽然我之前用函数式语言进行过少量编程,但我才刚刚开始使用 Clojure。由于在学习一门新语言时执行相同类型的“Hello World”程序会变得陈旧,因此我决定阅读Cinder “Hello, Cinder”教程,并将其翻译成 Clojure 和Quil。在本教程的第 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 );
}
}
}
}
在我看来,这段代码有一个非常重要的特点:它在粒子对之间进行比较并更新两个粒子,然后在未来跳过相同的组合。出于性能原因,这非常重要,因为这段代码每帧执行一次,并且在任何给定时间屏幕上都可能有数千个粒子(比我更了解 big 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)))
本质上,这个过程是这样的:
- 粒子组合:使用组合“组合”函数计算粒子的所有组合
- new-accelerations:根据组合列表计算加速度列表
- new-accelerations-grouped:通过循环遍历每个粒子并检查组合列表,将每个粒子的加速度(按顺序)分组,构建一个列表列表,其中每个子列表是所有单独的加速度;还有一个微妙之处是,如果粒子是组合列表中的第一个条目,它会获得原始加速度,但如果是第二个,它会获得相反的加速度。然后过滤掉 nil
- 将加速度的每个子列表减少到这些加速度的总和
现在的问题是,这比我以前做的更快吗?(我还没有测试过,但我最初的猜测是不可能的)。
更新 2: 这是我想出的另一个版本。我认为这个版本在各方面都比我上面发布的版本要好得多:它使用瞬态数据结构来提高新列表的性能/易于可变性,并使用循环/递归。它应该比我上面发布的示例快得多,但我还没有测试验证。
(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)))))