C 中计算高效的三维数组
-
09-06-2019 - |
题
我正在尝试以数值方式求解一组三维偏微分方程。在每个方程中,点中未知数的下一个值取决于最近点中每个未知数的当前值。
为了编写有效的代码,我需要使三个维度中的点在(一维)内存空间中接近,以便每个值仅从内存中调用一次。
我正在考虑使用八叉树,但我想知道是否有人知道更好的方法。
解决方案
八叉树是必经之路。将数组细分为 8 个八分圆:
1 2 3 4 --- 5 6 7 8
然后将它们按照上面的1、2、3、4、5、6、7、8的顺序排列在内存中。您在每个八分圆内递归地重复此操作,直到达到某个基本大小,可能约为 128 字节左右(这只是一个猜测 - 确保进行分析以确定最佳截止点)。与简单的布局相比,这具有更好的缓存一致性和引用局部性。
其他提示
树方法的一种替代方法:使用 Morton-Order 对数据进行编码。
在三维空间中,它是这样的:取坐标分量并将每个位交错两个零位。这里以二进制显示:11111b 变为 1001001001b
执行此操作的 C 函数如下所示(为清楚起见,仅显示 11 位):
int morton3 (int a)
{
int result = 0;
int i;
for (i=0; i<11; i++)
{
// check if the i'th bit is set.
int bit = a&(1<<i);
if (bit)
{
// if so set the 3*i'th bit in the result:
result |= 1<<(i*3);
}
}
return result;
}
您可以使用此功能来组合您的仓位,如下所示:
index = morton3 (position.x) +
morton3 (position.y)*2 +
morton3 (position.z)*4;
这会将您的三维索引变成一维索引。其中最好的部分:在 3D 空间中接近的值在 1D 空间中也接近。如果您经常访问彼此接近的值,您还将获得非常好的加速,因为莫顿顺序编码在缓存局部性方面是最佳的。
对于 morton3,你最好不要使用上面的代码。使用一个小表一次查找 4 或 8 位并将它们组合在一起。
希望它有帮助,尼尔
这本书 多维和度量数据结构的基础 可以帮助您决定哪种数据结构对于范围查询最快:八叉树、kd 树、R 树、...它还描述了将点保存在内存中的数据布局。
不隶属于 StackOverflow