loops - c++中循环向量的性能

Question

我有一个 100,000 次迭代的 for 循环 - 每次迭代都涉及一些对象位置的简单距离计算。这都是复杂的碰撞检测机制的一部分。

现在太多不必要的迭代效率不高，并且会减慢程序的速度。我想通过使用排序向量来减少计算时间。

因此，或者我考虑通过将引用元素插入到根据“网格”对位置进行排序的 2D 向量中来将迭代次数降至最低。而不是 100,000 次迭代，我可能只有 1000 次迭代具有相同的计算，但现在只涉及特定的“部门”。然而，不利的一面可能是，当对象改变其位置时，需要通过使用 push_back 和擦除来定期更新 2D 矢量与对象网格或扇区位置。

我的问题是关于性能而不是代码。使用 erase 和 push_back 更新向量是否比使用暴力尝试迭代更快？我只需要粗略估计一下是否值得追求这个想法。谢谢。

Answer 1

您正在寻找的是二进制空间分区。这种方式对于任何给定的对象，找到一个碰撞对象是 O(log N )，其中N是对象的数量。这应该会将您的碰撞检测成本从 O(N ² ) 降低到 O( N log N )。

Answer 2

如果您在主要是静态对象之间进行距离计算，则可以使用四叉树来减少检查次数。如果很多对象都在移动，那么“松散四叉树”是一个更好的选择。