c# - 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值(value)观等

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

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