稀疏矩陣時間計算

Question

如果我將一個稠密矩陣存儲爲一個座標明智的稀疏矩陣而不是n×n二維數組，那麼時間效率是多少？如果我將它作爲稀疏矩陣存儲，顯然這將是不好的。

Answer 1

您應該考慮您感興趣的操作，因爲各種操作的效率因存儲格式不同而不同。請參閱Scipy Sparse中的各種格式（和典型用例）。

通常情況下，'稀疏矩陣'被定義爲一個矩陣，您可以通過利用許多元素爲零的事實獲得一些性能優勢。因此，以稀疏格式存儲稀疏矩陣應該有優勢。

座標格式（COO）的空間需求爲3 * nnzs。所以只要3 * nnzs < N^2（您的矩陣順序）可以節省存儲空間。其他格式（如CSR）在空間方面效率更高（2 * nnzs + N），並且還有效地支持常用操作（例如稀疏矩陣向量乘法）。