3D稀疏矩阵实现？

Question

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

但当我在 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<...>（初始容量）来避免添加项目时不必要的大小调整。

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

Answer 2

Lasse Espeholt 的解决方案很实用，但可以通过在元素“归零”或为空时删除元素来改进。如果不这样做，矩阵或数组可能会失去稀疏性。这是一个替代解决方案，假设如果尚未插入某种类型的元素，则它是该类型的默认元素。例如，对于double 表示0.0，对于string 表示null。

public class Sparse3DArray<T>
{
  private Dictionary<Tuple<int, int, int>, T> data = new Dictionary<Tuple<int, int, int>, T>();

  public int Nnz { get { return data.Count; } }

  public T this[int x, int y, int z]
  {
    get
    {
      var key = new Tuple<int, int, int>(x, y, z);
      T value;
      data.TryGetValue(key, out value);
      return value;
    }

    set
    {
      var key = new Tuple<int, int, int>(x, y, z);
      if (null == value)
        data.Remove(key);
      else if (value.Equals(default(T)))
        data.Remove(key);
      else
       data[key] = value;
     }
   }
}

Answer 3

事实上，您在 3D 坐标系中工作并不会改变您是否可以使用此数据结构。 3D空间的矩阵可以使用与2D矩阵相同的稀疏矩阵来包含；只是条目发生了变化。

对于具有大量零条目的大型矩阵，您可以使用稀疏矩阵。这在来自有限差分和有限元方法的物理问题的离散表示中是典型的。它们具有聚集在对角线周围的非零条目带；对角带之外的条目通常为零。稀疏矩阵不会存储这些；必须编写像 LU 和 QR 这样的分解才能知道如何处理稀疏性。

这些矩阵可以描述 2D 或 3D 空间中的问题。

如果您认为需要另一种数据结构，我相信您是错误的。

Answer 4

为什么不使用 KD-Tree 或类似的数据结构（例如八叉树）？
有一些很棒的 C++ 实现，例如： FLANN

Answer 5

我会使用字典，但您可以使用单个 long 作为键并使用它来存储坐标（前提是它们是短裤）。这将减少您的内存占用，甚至可能提高性能。

private Dictionary<long, T> data = new Dictionary<long, T>();
private long GetKey(short x, short y, short z)
{
   return (x * 10000 + y) * 10000 + z;
}