在C语言中高效地处理三维数组

Question

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

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

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

- Doctor P

Answer 1

一种替代树状结构的方法是：使用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位，并将它们组合在一起。

希望能帮到你， 尼尔斯

- Nils

---

这似乎是八叉树的一个很好的替代方案，但在我的特定情况下，我认为我会坚持使用树的简单性。无论如何，感谢您的回答，我不知道这种方法！ - Coffee on Mars

Answer 2

Octtrees是一种很好的选择。你可以将数组细分为8个八分体：

1 2
3 4
---
5 6
7 8

然后按照上面的顺序在内存中排列它们，即1、2、3、4、5、6、7、8。在每个八分体内部递归地重复此过程，直到达到某个基本大小，大约为128字节左右（这只是一个猜测，请务必进行性能测试以确定最佳截止点）。这种布局比朴素布局具有更好的缓存协同性和引用局部性。

- Adam Rosenfield

Answer 3

这本书 《多维和度量数据结构基础》 可以帮助你决定哪种数据结构在范围查询方面最快：八叉树、kd树、R树等。它还描述了在内存中保持点聚合的数据布局。

- palm3D