3D稀疏矩阵实现？

Question

我通过http://www.blackbeltcoder.com/Articles/algorithms/creating-a-sparse-matrix-in-net找到了一个非常好的 C# 稀疏矩阵实现。

但当我在 3d 坐标系中工作时，我需要一个稀疏矩阵实现，我可以用它来映射 3d 坐标系。

详细信息：我在内存中存储大量原始形状数据，例如立方体。我确实有大量的条目（大约 3000 万个），并且有很多空（零）条目。鉴于我的每个条目花费 1 个字节的条目，我想实现一个稀疏矩阵，这样我就可以相当节省内存空间。

注意：快速访问矩阵单元对我来说是一个相当重要的因素，因此我会牺牲速度与内存消耗。

Answer 1

我刚刚提出的一个非常简单的解决方案是这样的：

public class Sparse3DMatrix<T>
{
    Dictionary<Tuple<int,int,int>, T> values = new Dictionary<Tuple<int, int, int>, T>();

    public T this[int x, int y, int z]
    {
        get { return values[new Tuple<int, int, int>(x, y, z)]; }
        set { values[new Tuple<int, int, int>(x, y, z)] = value; }
    }

    public bool ContainsKey(int x, int y, int z)
    {
        return values.ContainsKey(new Tuple<int, int, int>(x, y, z));
    }
}

用法：

var test = new Sparse3DMatrix<float>();
test[1, 1, 1] = 1f;
Console.WriteLine(test[1, 1, 1]);

它可以通过像他的版本所具有的方法以及对x, y, z值的检查等来扩展。

我确信有人对其性能有话要说。除非您确实需要高性能，否则这将是一个不错的实现。这取决于哈希码的实现Tuple和您的具体用法。如果我们假设哈希值是好的，我们就有O(1)查找时间。如果您知道您将有很多元素，则可以使用它new Dictionary<...>(initial capacity)来避免在添加项目时不必要的调整大小。

与他的不同，这只有一个Dictionary包含所有项目的单。他的版本有词典的词典。他的好处是，如果您必须扫描整行，您可以只迭代二级字典（如果您想扫描列，这对您没有帮助），这比单独查找项目更快。但是拥有一个字典意味着更少的内存使用 - 特别是当每行只有很少的项目时。