如何在元素填充過程中經濟地存儲稀疏矩陣？

Question

我知道有很多好方法可以存儲稀疏矩陣而不佔用太多內存。 但我想知道是否有一個很好的方法來存儲一個稀疏矩陣的過程中呢？下面是更詳細的場景：程序通過計算每次迭代中非零值的位置來構造一個稀疏矩陣;並且由於非零值的座標直到運行時纔會被知道，所以它們是完全隨機且不可預知的。

我使用C++進行編程。那麼有沒有一種方法可以在C++中實現這一點？其他語言的解決方案也受到讚賞。

Answer 1

std :: map可能是你正在尋找的東西，它是一個鍵 - >值映射類型。將它與std :: set相結合，這是一個獨特的元素集合。所以，你可以使用地圖的std ::一集，像這樣：

std::map<int, std::set<int> > sparseMatrix; 

// Add some edges. 
sparseMatrix[0].insert(1); // Add an edge from vertex 0 to 1. 
sparseMatrix[4].insert(2); // Add an edge from vertex 4 to 2. 
sparseMatrix[0].insert(1); // Edge already exists, no data added to the set. 

這表示可以讓你代表有向圖，它類似於一個邊列表。一個集合的行爲還可以防止你有兩個「相同」的邊（a-> b和c-> d，其中a = b和c = d），這很好，你會得到一個行爲使用了一個鄰接矩陣。可以遍歷人喜歡邊這麼：

for(std::map<int, std::set<int> >::const_iterator i = sparseMatrix.begin(); 
    i != sparseMatrix.end(); 
    ++i) 
{ 
    for(std::set<int>::const_iterator j = i->second.begin(); 
     j != i->second.end(); 
     ++j) 
    { 
     std::cout << "An edge exists from " << i->first << " to " << *j << "."; 
    } 
} 

一些鏈接：

• Set documentation
• Map documentation

Answer 2

你可以有3個平行列表和存儲行ID於一體，列在另一個id中，在第三個值中。一旦你完成了所有的條目，你可以根據需要重新組織，例如。按行和列排序。

在你的問題中沒有描述什麼是你最終需要/想要表示稀疏矩陣？你需要用它來做什麼？這會影響表示