如何高效存储大型稀疏阵列

Question

我正在跟踪粒子到三维晶格中。每个晶格元素都有一个对应于展开的3D数组的索引

  S = x + WIDTH * (y + DEPTH * z)

我对从S1单元到S2单元的过渡感兴趣。由此产生的过渡矩阵M（S1，S2）人口稀少，因为粒子只能在细胞附近到达。不幸的是，使用几何上接近的展开3D阵列单元的索引可能会在索引上有很大差异。例如，位于彼此顶部（例如z和z 1处）的单元格的索引将按宽度*深度移动。因此，如果我尝试累积得到的2D矩阵M（S1，S2），S1和S2将非常不同，即使细胞是相邻的。这是一个重要的问题，因为我不能使用通常的稀疏矩阵存储。

开始时，我尝试以坐标格式存储矩阵：

  I , J VALUE

不幸的是，我需要循环整个索引集以找到合适的S1，S2并存储累积的M（S1，S2）。

异常稀疏的矩阵有一些底层结构，因此索引非常简单。然而，在这种情况下，我很难弄清楚如何为我的细胞建立索引。

谢谢你的帮助提前谢谢，

Answer 1

有几种方法。哪种最好取决于需要在矩阵上执行的操作。

一个好的通用方法是使用哈希表，其中键是索引元组，在您的情况下（i， j）。

如果相邻的（欧几里德意义上的）矩阵元素必须是可发现的，那么另一种策略是使用莫顿顺序键的平衡树。密钥（i，j）的莫顿阶值就是位交错的整数i和j。您应该很快就会看到，在索引2-空间中彼此接近的索引元组也以线性莫顿顺序接近。

当然，如果您一次构建矩阵，之后它是不可变的，那么您可以在数组中构建键值对，而不是哈希表或平衡树，对它们进行排序（对（i，j）对进行字典化，对莫顿键进行线性排序），然后通过简单的二进制搜索进行读取。