c - 稀疏多维数据表示

Question

我正在研究使用 4 维数据的心脏模拟工具，即 3D 空间中位置的几个 (3-30) 变量。

我现在添加了一些组织几何结构，这将使包含的 3D 框中超过 2/3 的点留在要模拟的组织之外，因此我需要一种有效存储活动点而不是其他点的方法。

至关重要的是，我需要能够：

• 迭代受约束的 3D 框内的所有活动点（也许是迭代器？）
• 访问一个点后，找到它的正交邻居 (x,y,z) +/- 1。

这可能不止一个问题！我主要关心的是如何有效地表示稀疏数据。

我正在使用 C。

Answer 1

您多久添加一次纸巾，需要多长时间？

一个简单的解决方案是使用一个链表+散列和一个指向另一个的指针。

意义：

1. 保存包含所有相关点及其数据的链接列表
2. 保存哈希以轻松获取此数据：键 = 坐标，数据 = 指向链表的指针。

操作的实现将是：
添加一个框：遍历整个链表，并且只将相关元素放入“工作”链表中
迭代：遍历“工作”链表
查找邻居：寻找每个邻居在哈希中。

复杂性：
添加：O(n)，迭代 O(1) 以查找下一个元素，邻居 O(1) 平均（由于散列）。

Answer 2

如果要使用普通数组索引，可以使用 mmap() 在 POSIX 系统上创建稀疏数组：

float (*a)[500][500];

a = mmap(0, (size_t)500 * sizeof a[0], PROT_READ | PROT_WRITE,
    MAP_PRIVATE | MAP_ANONYMOUS, -1, 0);

if (a && (void *)a != MAP_FAILED)
{
    /* a is now 500 x 500 x 500 sparse array of floats */

You can then just access a[x][y][z] as you like, and it will only actually allocate real memory for each page that's touched. The array will be initialised to zero bytes.

If your system doesn't have MAP_ANONYMOUS you can achieve the same effect by mapping from /dev/zero.

Note that on many systems, swap space will be reserved (though not used) for the whole array.

Answer 3

First off, I think it's worth considering what your real requirement is. I suspect that it's not just "store the active points and none of the others in as space-efficient a manner as possible", but also a certain amount of "store adjacent points in nearby memory locations so that you get good caching behavior" and "store points in a manner for which lookups can be done efficiently".

话虽如此，这就是我的建议。将完整的 3D 区域分成大小相同的立方体块。对于每个块，将块中的所有点存储在密集数组中，包括一个布尔 isTissue 数组，用于判断每个点是否在组织区域中。仅分配其中有点的块。制作一个（密集）指向块的指针数组，对于未分配的块使用 NULL 指针。

因此，要找到 (i,j) 处的点，首先计算 ii=i/blockside, jj=j/blocksize，然后查看 (ii,jj) 处的块指针表以找到包含你的观点。如果该指针为 NULL，则您的点不在组织中。如果它不为空，则查看该块中的 (i mod blocksize, j mod blocksize) ，并且存在您的 (i,j) 点。您可以检查它的 isTissue 标志以查看它是否是“当前”点。

您需要选择块大小作为在最小化跨块边界的相邻点计算次数和最小化块中但不在组织区域中的点数之间的平衡。我猜你至少希望块的一行是一个高速缓存行。可能最佳值要大得多，尽管它至少在某种程度上取决于您的几何形状。

要遍历 3D 框中的所有点，您可以只查找每个点，或者（更有效地）找出框接触的块，然后遍历框内这些块中的区域，跳过isTissue 为假的那些。

如果您正在对块进行大量释放和重新分配，您可能希望通过将块放入“未使用”池中来“释放”块，然后将块从该池中拉出而不是重新分配它们。这还有一个好处是这些块已经将它们的所有点设置为“不存在”（因为这就是你释放块的原因），所以你不需要初始化它们。

有经验的读者可能会认识到这与为并行计算布置数据的方式之间的相似之处；如果您有一个非常大的模拟，您可以轻松地将块分布在多个节点上，并且您只需要为跨块计算进行跨节点通信。对于那种应用程序，您可能会发现执行嵌套级别的块很有用，其中您有包含较小块（用于几何）的元块（用于跨节点通信）。