.net - 在 .NET 中存储稀疏矩阵的最佳方法

Question

我们有一个存储稀疏矩阵的应用程序。该矩阵的条目主要存在于矩阵的主对角线周围。我想知道是否有任何有效的算法(或现有的库)可以有效地处理这种稀疏矩阵？优选地，这将是通用实现，其中每个矩阵条目可以是用户定义的类型。

针对问题/回复进行编辑:

当我说主要围绕主对角线时，我的意思是大多数矩阵的特征是大多数条目都聚集在主对角线上，但靠近对角线可能有零，并且可能有远离对角线的非零值对角线。我想要一些对“大多数”情况有效的东西。

我将用它做什么？我需要能够有效访问行中的所有值或列中的所有值。存储的值将是 bool 值。一个例子是:

对于一行中的所有真值，对于每一列，一个真值出现在将该列的所有条目设置为某事

对于一行中的所有假值，将条目设置为

这一切以前都是用链表完成的，但实现起来非常困惑。我希望使用稀疏矩阵可以改进算法，但事实证明，找到“正确”类型的稀疏矩阵算法很困难。

附言感谢您到目前为止的答复

Answer 1

您可以使用基于单元格 [row,col] 的索引。由于数据位于对角线上，因此存储行索引和相关列与数据的索引的典型方法不是最佳的。这是您可以用来执行此操作的一些代码:

    public class SparseMatrix<T>
    {
        public int Width { get; private set; }
        public int Height { get; private set; }
        public long Size { get; private set; }

        private Dictionary<long, T> _cells = new Dictionary<long, T>();

        public SparseMatrix(int w, int h)
        {
            this.Width = w;
            this.Height = h;
            this.Size = w * h;
        }

        public bool IsCellEmpty(int row, int col)
        {
            long index = row * Width + col;
            return _cells.ContainsKey(index);
        }

        public T this[int row, int col]
        {
            get
            {
                long index = row * Width + col;
                T result;
                _cells.TryGetValue(index, out result);
                return result;
            }
            set
            {
                long index = row * Width + col;
                _cells[index] = value;
            }
        }
    }

    static void Main()
    {
        var sm = new SparseMatrix<int>(512, 512);
        sm[42, 42] = 42;
        int val1 = sm[13, 13];
        int val2 = sm[42, 42];

        Console.WriteLine("VAL1 = " + val1); // prints out 0
        Console.WriteLine("VAL2 = " + val2); // prints out 42

        Console.ReadLine();
    }

请注意，当 T 是结构体时，您可能必须调用 IsCellEmpty，因为获取单元格的内容不会为空，并且将具有该类型的默认值。您还可以扩展代码以根据 Size 为您提供快速的“SparseRatio”。属性(property)和 _cells.Count .

编辑:

好吧，如果您对速度感兴趣，则可以在空间与速度之间进行权衡。与其只有一本字典，不如拥有三本!它使您的空间增加了三倍，但它使以您想要的任何方式进行枚举变得非常容易。这是一些新代码，表明:

    public class SparseMatrix<T>
    {
        public int Width { get; private set; }
        public int Height { get; private set; }
        public long MaxSize { get; private set; }
        public long Count { get { return _cells.Count; } }

        private Dictionary<long, T> _cells = new Dictionary<long, T>();

        private Dictionary<int, Dictionary<int, T>> _rows = 
            new Dictionary<int, Dictionary<int, T>>();

        private Dictionary<int, Dictionary<int, T>> _columns = 
            new Dictionary<int, Dictionary<int, T>>();

        public SparseMatrix(int w, int h)
        {
            this.Width = w;
            this.Height = h;
            this.MaxSize = w * h;
        }

        public bool IsCellEmpty(int row, int col)
        {
            long index = row * Width + col;
            return _cells.ContainsKey(index);
        }

        public T this[int row, int col]
        {
            get
            {
                long index = row * Width + col;
                T result;
                _cells.TryGetValue(index, out result);
                return result;
            }
            set
            {
                long index = row * Width + col;
                _cells[index] = value;

                UpdateValue(col, row, _columns, value);
                UpdateValue(row, col, _rows, value);
            }
        }

        private void UpdateValue(int index1, int index2, 
            Dictionary<int, Dictionary<int, T>> parent, T value)
        {
            Dictionary<int, T> dict;
            if (!parent.TryGetValue(index1, out dict))
            {
                parent[index2] = dict = new Dictionary<int, T>();
            }
            dict[index2] = value;
        }
    }

如果要遍历所有条目，请使用 _cells .如果您想要给定列的所有行，请使用 _columns .如果您想要给定行中的所有列，请使用 _rows .

如果要按排序顺序进行迭代，可以开始将 LINQ 添加到混合中和/或使用带有封装条目的内部类的排序列表(必须存储行或列并实现 IComparable<T> 进行排序上类)。