稀疏的多维数据表示

Question

我正在研究一种使用四维数据的心脏模拟工具,即3D空间中的几个(3-30)变量.

我现在正在添加一些组织几何图形,它将在要包含的组织外面的容纳3D框中留下超过2/3的点,因此我需要一种方法来有效地存储活动点而不是其他点.

至关重要的是,我需要能够:

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

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

我正在使用C.

Answer 1

您多久添加一次组织,需要多长时间？

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

含义:

1. 保存包含所有相关点及其数据的链接列表
2. 保存哈希以轻松获取此数据:key = coordinates,data =指向链接列表的指针.

操作的实现将是:
添加一个框:遍历完整的链表,并只将相关元素带入"工作"链表
迭代:查看"工作"链表
查找邻居:寻找每个邻居在哈希.

复杂性:
添加:O(n),迭代O(1)用于查找下一个元素,邻居O(1)平均值(由于哈希).