Clojure 中的碰撞检查迭代是如何用时间 n^2/2 完成的？

Question

我对检测碰撞不感兴趣

我习惯了使用 java 在两个 for 循环中使用两个计数器的方法，就像这样：

第一个循环解析所有对象并包含第二个循环。它的计数器是针对所有其他对象检查的当前对象的索引。

第二个 for 循环解析所有未检查的对象。它的计数器是当前正在检查的未检查对象与第一个循环正在查看的对象的索引。

伪代码：

for(i++)
  for(int j = i, j++)
   collides(objects[i], objects[j)

这在 Clojure 中是如何实现的？

我很习惯使用像map这样没有计数器的命令，我想知道这种方法是否真的需要一个计数器。如果有一种方法可以在没有计数器的情况下执行此操作，那将是更可取的。

我也想说明一下，我不希望随时间实施n^2。相反，我想要时间 n^2/2 方法，它只检查未检查的对象是否发生碰撞。

Answer 1

您可以通过 for:

执行相同的代码

(for [i (range (count objs))
      j (range i (count objs))
      :when (collide? (nth objs i) (nth objs j))]
    ...do stuff...)

如果您使用 loop，它会运行更快，但它可能看起来不太好。

Answer 2

至select所有不使用计数器碰撞的对：

(defn select-pairs [collide? objects]
  (for [tail (iterate rest objects) :while (seq tail)
        :let [x (first tail)], y tail :when (collide? x y)]
    [x y]))

例如，

(select-pairs < (range 4))
;([0 1] [0 2] [0 3] [1 2] [1 3] [2 3])

这适用于任何序列，甚至是无穷无尽的序列。
collide? 只是 select 对的标准名称。

Clojure 中的碰撞检查迭代是如何用时间 n^2/2 完成的？

How is iteration for collision checks in Clojure done with time n^2/2?

clojure

collision