通過兩個稀疏矩陣迭代

Question

我正在使用boost sparse矩陣來保存bool's並試圖編寫一個比較函數來將它們存儲在地圖中。這是一個非常簡單的比較功能。基本上，這個想法是將矩陣看作一個二進制數（在被平面化成一個向量之後）並根據該數值進行排序。這可以通過這種方式來完成：

for(unsigned int j = 0; j < maxJ; j++) 
{ 
    for(unsigned int i = 0; i < maxI; i++) 
    { 
    if(matrix1(i,j) < matrix2(i,j) return true; 
    else if(matrix1(i,j) > matrix2(i,j) return false; 
    } 
} 
return false; 

然而，這是因爲矩陣的稀疏的低效，我想用迭代器相同的結果。使用迭代器的算法似乎很簡單，即：1）獲取每個矩陣中的第一個非零單元，2）比較兩者的j * maxJ + i，3）如果相等，則抓住每個矩陣中的下一個非零單元並重復。不幸的是，在代碼中這是非常乏味的，我很擔心錯誤。

我想知道的是（a）有沒有更好的方法來做到這一點，（b）是否有一個簡單的方法來獲得兩個矩陣的「下一個非零單元格」？顯然，我不能像循環遍歷一個稀疏矩陣那樣使用嵌套for循環。

感謝您的幫助。

-

因爲它似乎是我上面提出的算法可以在我的特定應用的最佳解決方案，我想我應該張貼我的棘手的部分開發的代碼，讓在下一非零細胞兩個稀疏矩陣。這段代碼並不理想，也不是很清楚，但我不知道如何改進它。如果有人發現了錯誤或者知道如何改進它，我會很感激一些評論。否則，我希望這對其他人有用。

typedef boost::numeric::ublas::mapped_matrix<bool>::const_iterator1 iter1; 
typedef boost::numeric::ublas::mapped_matrix<bool>::const_iterator2 iter2; 

// Grabs the next nonzero cell in a sparse matrix after the cell pointed to by i1, i2. 
std::pair<iter1, iter2> next_cell(iter1 i1, iter2 i2, iter1 end) const 
{ 
    if(i2 == i1.end()) 
    { 
     if (i1 == end) 
      return std::pair<iter1, iter2>(i1, i2); 
     ++i1; 
     i2 = i1.begin(); 
    } 
    else 
    { 
     ++i2; 
    } 

    for(; i1 != end;) 
    { 
     for(; i2 != i1.end(); ++i2) 
     { 
      return std::pair<iter1, iter2>(i1,i2); 
     } 
     ++i1; 
     if(i1 != end) i2 = i1.begin(); 
    } 
    return std::pair<iter1, iter2>(i1, i2); 
} 

Answer 1

（一）我不完全理解你想實現什麼，但如果你想比較，如果兩個矩陣有它足夠使用的elementwise矩陣乘法相同指數相同的值（其應疏實施以及）：

matrix3 = element_prod (matrix1, matrix2); 

這樣，你會得到每個指標：

0 (false) * 1 (true) = 0 (false) 
0*0 = 0 
1*1 = 1 

所以導致matrix3將您的解決方案在同一行:)

Answer 2

在我看來，我們在談論執行按位上的boost :: sparse_matrix的elementwise運營商，因爲如果比較一個向量（或矩陣）是不使用任何標準的矢量規範比另一種更小的特殊要求運營商（或特殊映射/規範）。

據我所知，boost並沒有提供二進制矩陣的特殊運算符（不是說稀疏二進制矩陣）。使用BLAS水平矩陣/矢量代數不可能有任何簡單的解決方案。二進制矩陣在線性代數場中有自己的位置，所以有技巧和定理，但我懷疑這些比你的解決方案更容易。

你的問題可以重新表達爲：我如何有效地排序天文大數字代表一個二維位圖（n = 100所以100x100元素會給你一個像2^10000的數字）。

好問題！

Answer 3

順便說一下，我喜歡這個問題。

讓我僞了什麼，我想你問

declare list of sparse matrices ListA 
declare map MatMAp with a sparse Matrix type mapping to a double, along with a 
`StrictWeakMatrixOrderer` function which takes two sparse matrices. 

Insert ListA into MatMap. 

問題：如何有效地編寫一個StrictWeakMatrixOrderer？

這是一種方法。我在飛行發明了這個....

---

定義一個函數flatten()和預先計算的扁平矩陣，存儲所述扁平載體在載體中（或用隨機索引另一個容器上界）。 flatten()可以像連接每一行（或列）和前一個一樣簡單（如果你有一個常量時間函數來抓取一行/一列，可以在線性時間內完成）。

這產生了一組大小在10^6左右的向量。這是一個折衷 - 保存這些信息而不是實時計算它。如果你一直在做大量的比較，這很有用。記住，零包含信息 - 刪除它們可能會產生兩個彼此相等的向量，而它們的生成矩陣可能不相等。

然後，我們將算法問題從「有序矩陣」轉換爲「有序向量」。 我從來沒有聽說過矩陣的距離度量標準，但我聽說過矢量的距離度量標準。

您可以使用「差異總和」命令又名漢明距離。 （foreach元素不同，加1）。這將是一個O（n）的算法：

for i = 0 to max. 
    if(a[i] != b[i]) 
    distance++ 

return distance 

的漢明距離滿足這些條件

d(a,b) = d(b,a) 
d(a,a) = 0 
d(x, z) <= d(x, y) + d(y, z) 

我們做了一些現成的，袖口分析....

• 矩陣中的元素（或其相應的向量）。
• O(n)距離度量。
  • 但它是O(n)比較。如果每個數組訪問有O(m)時間，那麼您將有一個O(n*(n+n)) = O(n^2)度量。所以你have有< O(n)訪問權限。根據SGI的STL網站，std::vector []運營商提供了「對任意元素進行攤銷的恆定時間訪問」。
• 提供了有足夠的內存來存儲k*2*10^6，其中k是您管理矩陣的數量，這是使用大量內存換來是線性的工作方案。