如何存儲稀疏矩陣？

Question

我需要實現兩種類型在C++中存儲稀疏矩陣：

• 鏈表
• 陣列（有效途徑）

空間複雜度是非常重要的位置。最有效的方法是什麼？

Answer 1

nnz：非零數字稀疏矩陣的
row_size：矩陣行數
column_size：矩陣列數
方法有很多種，它們的空間複雜度：

• 壓縮稀疏行（CSR） ：2*nnz + row_size內存數量
• 壓縮稀疏列（CSC）：2*nnz + column_size內存數量
• 座標格式（COO）：3*nnz數量的存儲器

對於空間複雜度：
如果row_size > column_size，使用CSC格式，否則，使用CSR格式。

時間複雜度：
對於CSR格式，行會O(1)時間進行索引，列將O(log(k))時間進行索引，通過二進制搜索列，k是該行的非零元素的數量。所以價值將被索引O(log(k))時間。
對於COO格式，值將在O(1)時間索引。

格式細節
[1] https://en.wikipedia.org/wiki/Sparse_matrix
[2] https://software.intel.com/en-us/node/471374

Answer 2

由於矩陣是稀疏的，因此您只需要存儲填充的單元格。應該進行簡單的座標值查找。理想情況下，您應該使用快速查找的方式，如地圖O（log n）或unordered_map O（1）。

Answer 3

一種有效的方法是使用哈希映射（對於每行）哈希映射（按列索引存儲每行中的元素）。然後將能夠訪問O（1）時間的任何元素。

您可以實現所有數值算法，如加法和乘法僅通過非零元素進行迭代，這會給您更好的複雜度，然後O（N * M）其中N和M是矩陣中的列和行數。