我正在尝试从数字上解三维的一组偏微分方程组。在每个等式中，一个点中未知数的下一个值取决于最近点中每个未知数的当前值。

为了编写高效的代码，我需要在(一维)内存空间中保持三个维度上的点接近，以便每个值仅从内存中调用一次。

我当时在考虑使用八叉树，但我想知道是否有人知道更好的方法。

解决方案

回答

八叉树是要走的路。我们将数组细分为8个八分圆：

1 2
3 4

---

5 6
7 8

然后按照上述顺序将它们按1、2、3、4、5、6、7、8的顺序放置在内存中。我们可以在每个八分圆内递归地重复此操作，直到达到基本大小(大约128个字节左右)为止(这只是一个猜测-请确保通过分析确定最佳截止点)。与朴素的布局相比，它具有更好得多的缓存一致性和引用的局部性。

回答

《多维和度量数据结构基础》一书可确定哪种数据结构是范围查询最快的：八叉树，kd树，R树，...
它还描述了将内存中的各个点保持在一起的数据布局。

回答

一种替代树方法的方法：使用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空间中也接近。如果我们经常访问彼此接近的值，则由于缓存位置方面的morton顺序编码是最佳的，因此也会获得非常好的加速。

对于morton3，最好不要使用上面的代码。使用一张小桌子一次查找4或者8位，并将它们组合在一起。

希望能帮助到你，
尼尔斯