使用正确的优化算法 C++ 查找 3D 空间中点之间的距离 [英] Finding distance between points in 3D space using correct optimization algorithm C++
问题描述
使用数学公式很容易找到 3D 空间中任意两点之间的距离:√((x2-x1)^2 )+(y2-y1)^2+(z2-z1)^2
It's easy to use the mathematical formula to find distance between any two points in 3D space which is:√((x2-x1)^2 )+(y2-y1)^2+(z2-z1)^2
计算空间中任意两点之间的距离非常容易，其中每个点在 3D 空间中都有 (x, y z) 坐标.
And it's pretty easy to calculate for finding distance between any two points in space where each point has (x, y z) coordinates in 3D-space.
我的问题是，将这个公式扩展到我面临优化问题的大范围.我所做的是创建一个简单的 Vector 类，并使用这个用 C++ 编写的公式来计算距离.
My question, extends this formula to a large scale where I'm facing optimization hiccups. What I did was create a simple Vector class and use this formula coded in C++ to calculate the distance.
如果有1000分怎么办?我该怎么做?我在考虑使用一个简单的 std::vector 来存储这些 3D 点不会是计算这 1000 个点之间距离的优化方式.
What if there are a 1000 points? How do I go about it? I'm thinking using a simple std::vector to store these 3D points won't be optimized way of calculating the distance between these 1000 points.
推荐答案
优化有不同程度，视实际情况而定.
There are different level of optimization, each depends on actual situation.
在实现级别，您希望以对处理器友好的方式布局数据.即.
On implementation level, you want to layout the data in a friendly way to the processor. ie.
- 连续
- 正确对齐
- vector(SSE) 友好(SoA，如果您使用垂直 SSE(通常)，或 AoS 进行水平处理)
- 实际启用矢量化(编译器选项或手工)
这可能会给您带来高达 10% 的提升.
This may give you up to 10% boost.
在算法层面，你可能想再想想为什么你需要核心循环中每个点的距离
On algorithm Level, you may want to think again why do you need distances of every point in core loop
- 您是否需要非常频繁地重新计算它(在模拟)，或者您可以忍受陈旧的值并可能重新计算在后台(例如在游戏中)
- 你能用距离平方来做吗，你可以节省一个平方吗?
- 如果你的数据集不经常变化，如何将它转换为极坐标，你可以缓存每个点的r^2，距离平方公式然后减少到大约一个 cos() 操作:r1^2 + r2^2 - 2r1r2 cos(a1-a2).
Opps 在 3D 空间中复杂度增长到与笛卡尔坐标相同的水平，忽略点 3.
GPU 考虑
虽然 1000 点对于开销来说太少了，但如果您将来有更多点，您仍然可以考虑将工作卸载到 GPU.
While 1000 points are too few to trade for the overhead, you may still consider off-load the work to GPU if you have a lot more points in future.
这篇关于使用正确的优化算法 C++ 查找 3D 空间中点之间的距离的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
