在.NET中存儲稀疏矩陣的最佳方式

Question

我們有一個存儲稀疏矩陣的應用程序。該矩陣的條目主要存在於矩陣的主對角線周圍。我想知道是否有有效的算法（或現有的庫）可以有效地處理這種稀疏矩陣？優選地，這將是通用實現，其中每個矩陣條目可以是用戶定義的類型。

編輯在回答記者提問/回答：

當我說主要是圍繞主對角線我的意思是大多數矩陣的特徵將是最多的元素都集中在主對角線的關閉，但有可能是接近對角線的零，並且可能存在遠離對角線的非零值。我想在這裏爲'大多數'案例提高效率。

我將如何使用它？我需要能夠有效地訪問一行中的所有值或一列中的所有值。存儲的值將是布爾值。一個例子是：

1. 對於行中的所有真值的foreach列一個真正的出現在設置所有列項的東西
2. 對於行中的所有假值，設置入口的東西

以前都是用鏈表完成的，但是實現起來很混亂。我希望用一個稀疏矩陣可以改進算法，但找到「正確」類型的稀疏矩陣算法已證明很困難。

p.s.感謝迄今的迴應

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屬性和_cells.Count爲您提供快速「SparseRatio」。

編輯：

好吧，如果你有興趣的是速度，你可以做的空間權衡VS速度。而不是隻有一本字典，有三個！它將你的空間增加了三倍，但它讓你以任何想要的方式枚舉真正簡單。下面是一些新的代碼表明：

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>爲了排序工作）。

Answer 2

我沒有使用它，但Nmath Matrix處理這些（不免費）。

另外，Extreme Optimization Numerical Libraries for .NET（不免費）。

這裏有一個免費的：Math.NET Project（特別MathNet.Numerics.LinearAlgebra.Sparse namespace）

Answer 3

我猜Dictionary<int, Dictionary<int, object >>就足夠了。

Answer 4

我認爲這可以通過使用一個保存普通數組的類來完成，它保存在矩陣行之間應用的水平偏移並定義一行的條帶，例如，有效條目的數量。因此，對於僅定義了對角線和兩個相鄰元素的大型矩陣，您將創建一個3 *行數的數組，並將3存儲爲條帶寬度。偏移量取決於矩陣的大小。

我不知道有什麼免費的，這已經這樣做。

Answer 5

以下是一般的data structure schemas的列表。每種方法都有其優點和缺點，並且適用於稀疏矩陣出現時稍有不同的問題。您可能希望在現有的數據結構之上實現它們，例如List <>和Dictionary <>。

Answer 6

這裏有兩個問題：

• 「主要是圍繞主對角線」的說法太含糊。如果元素位於樂隊中，則使用樂隊本身的條帶存儲，如向量偏離主對角線。如果元素隨機散佈在主對角線的附近，則可以使用可能包含波段中的零點的帶狀表單，或者使用純粹的稀疏表單來存儲陣列中的元素及其位置。

• 你將如何處理矩陣？如果您的目標僅僅是高效的存儲空間，那麼綁定的表單將很有效率，並且可以快速訪問任何元素。如果你將矩陣做線性代數，但不超過矩陣矢量乘法，那麼帶狀形式仍然會出色地工作。如果您使用矩陣乘法或矩陣分解（其中填充成爲問題），則純稀疏形式可能更合適。例如，兩個帶狀矩陣的乘積會有更多的帶，所以兩個三對角矩陣的乘積將是五邊形。對於分解，重新排序有時會有助於減少填充。 （AMD是一種選擇，近似最小度置換，但還有其他方案。）