c - 稀疏多维数据表示

Question

我正在开发一种心脏模拟工具，该工具使用 4 维数据，即 3D 空间中多个位置的 (3-30) 个变量。

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

最重要的是，我需要能够:

• 遍历受限 3D 框内的所有事件点(也许是迭代器？)
• 访问一个点后，找到它的正交邻居 (x,y,z) +/- 1。

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

我正在使用 C。

Answer 1

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

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

含义:

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

操作的实现将是:
加框:遍历全链表，只取相关元素进入“work”链表
迭代:遍历“work”链表
查找邻居:在散列中寻找每个邻居。

复杂度:
添加:O(n)，迭代 O(1) 寻找下一个元素，邻居 O(1) 平均(由于散列)。