使用数学公式很容易找到 3D 空间中任意两点之间的距离:√((x2-x1)^2 )+(y2-y1)^2+(z2-z1) ^2
计算空间中任意两点之间的距离非常容易,其中每个点在 3D 空间中都有 (x, y z) 坐标。
我的问题是,将此公式扩展到我面临优化问题的大规模范围内。我所做的是创建一个简单的 Vector
类,并使用这个用 C++ 编写的公式来计算距离。
如果有1000分怎么办?我该怎么做?我在考虑使用简单的 std::vector
来存储这些 3D 点不会是计算这 1000 个点之间距离的优化方式。
最佳答案
有不同程度的优化,具体视实际情况而定。
在实现层面,您希望以对处理器友好的方式布置数据。 即。
- 连续
- 正确对齐
- vector (SSE) 友好(SoA,如果你使用垂直 SSE(通常),或 AoS 用于水平处理)
- 实际启用矢量化(编译器选项,或手工制作)
这可能会给您带来高达 10% 的提升。
在算法层面,你可能又要思考为什么需要核心循环中每个点的距离
- 你是否需要非常频繁地重新计算它(需要在 模拟),或者您可以接受过时的值并可能重新计算 在后台(例如在游戏中)
- 你能用距离的平方来做吗,你可以节省一个 sqrt?
- 如果你的数据集不经常变化,如何将它转换为极坐标,你可以缓存每个点的 r^2, 距离平方公式然后减少到大约一个 cos() 操作: r1^2 + r2^2 - 2r1r2 cos(a1-a2)。
编辑:Opps 在 3D 空间中,复杂性增长到与笛卡尔坐标相同的水平,忽略点 3。
GPU 考虑
虽然 1000 点数不足以换取开销,但如果您将来有更多点数,您仍可以考虑将工作卸载到 GPU。
关于c++ - 使用正确的优化算法 C++ 查找 3D 空间中点之间的距离,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/31485068/