c++ - 使用正确的优化算法 C++ 查找 3D 空间中点之间的距离

Question

使用数学公式很容易找到 3D 空间中任意两点之间的距离:√((x2-x1)^2 )+(y2-y1)^2+(z2-z1) ^2

计算空间中任意两点之间的距离非常容易，其中每个点在 3D 空间中都有 (x, y z) 坐标。

我的问题是，将此公式扩展到我面临优化问题的大规模范围内。我所做的是创建一个简单的 Vector 类，并使用这个用 C++ 编写的公式来计算距离。

如果有1000分怎么办？我该怎么做？我在考虑使用简单的 std::vector 来存储这些 3D 点不会是计算这 1000 个点之间距离的优化方式。

Answer 1

有不同程度的优化，具体视实际情况而定。

在实现层面，您希望以对处理器友好的方式布置数据。即。

1. 连续
2. 正确对齐
3. vector (SSE) 友好(SoA，如果你使用垂直 SSE(通常)，或 AoS 用于水平处理)
4. 实际启用矢量化(编译器选项，或手工制作)

这可能会给您带来高达 10% 的提升。

在算法层面，你可能又要思考为什么需要核心循环中每个点的距离

1. 你是否需要非常频繁地重新计算它(需要在模拟)，或者您可以接受过时的值并可能重新计算在后台(例如在游戏中)
2. 你能用距离的平方来做吗，你可以节省一个 sqrt？
3. 如果你的数据集不经常变化，如何将它转换为极坐标，你可以缓存每个点的 r^2，距离平方公式然后减少到大约一个 cos() 操作:r1^2 + r2^2 - 2r1r2 cos(a1-a2)。

编辑:Opps 在 3D 空间中，复杂性增长到与笛卡尔坐标相同的水平，忽略点 3。

GPU 考虑

虽然 1000 点数不足以换取开销，但如果您将来有更多点数，您仍可以考虑将工作卸载到 GPU。