我正在使用boost稀疏矩阵来保存布尔值,并尝试编写一个比较函数,以便将它们存储在映射中。这是一个非常简单的比较函数。基本上,想法是将矩阵视为二进制数(在被压缩成向量后),并根据该数字的值进行排序。可以通过以下方式实现:
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);
}