遍历两个稀疏矩阵

Question

遍历两个稀疏矩阵

3

我正在使用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);
}

- RandomGuy

为什么要用 < 和 > 来比较布尔值？即使你相信 false < true，"if(matrix1(i,j) < matrix2(i,j))" 会在第一个是 false 而第二个是 true 的情况下返回 true，在所有其他情况下都返回 false。 - Bill

我并不是试图编写一个<运算符来比较单个布尔值，而是尝试将这些数据结构插入到std::map中，这需要一个<运算符进行排序。 - RandomGuy

3个回答

0

（a）我不完全理解你想要实现什么，但如果你想比较两个矩阵在相同索引处是否具有相同的值，使用逐元素矩阵乘法就足够了（这也应该对稀疏矩阵进行实现）。

matrix3 = element_prod (matrix1, matrix2);

这样你就可以为每个索引获取：

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

因此，结果矩阵3将在一行中包含您的解决方案 :)

- count0

这是一个有趣的建议，但我需要对矩阵进行排序。本质上，我需要一种使用稀疏矩阵迭代器计算这些矩阵的XOR并按顺序j*maxJ+i执行XOR的方法，以便在找到XOR中的TRUE时停止计算，知道哪个矩阵是“较小的”。 - RandomGuy

0

在我看来，我们正在讨论在boost::sparse_matrix上实现按位、逐元素运算，因为比较一个向量（或矩阵）是否小于另一个而不使用任何标准向量范数需要特殊的运算符（或特殊的映射/范数）。

据我所知，boost没有为二进制矩阵提供特殊的运算符（更不用说稀疏二进制矩阵了）。使用BLAS级别的矩阵/向量代数解决这个问题不太可能有直接的解决方案。二进制矩阵在线性代数领域有自己的位置，因此有一些技巧和定理，但我怀疑这些方法比你的解决方案更容易。

你的问题可以重新表述为：如何高效地排序由2d位图表示的天文数字（n=100，因此100x100个元素将给出一个像2^10000这样的数字）。

好问题！

- count0

是的，显然没有什么万能的解决方案。矩阵中真实条目数量稀少的事实意味着我们可以通过我提到的算法得到在可接受时间内运行的解决方案。问题在于同时获取两个矩阵的下一个迭代器的代码不一定干净，我想知道是否有一种好的方法来同时迭代两个稀疏的二维矩阵。 - RandomGuy

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Paul Nathan · Accepted Answer

顺便说一下，我喜欢这个问题。

让我用伪代码来描述一下我认为你在问什么。

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的向量。这是一个权衡 - 保存这些信息而不是即时计算它。如果您要进行大量比较，这将非常有用。

记住，零包含信息 - 删除它们可能会产生两个相等的向量，而它们的生成矩阵可能不相等。

然后，我们已经将算法问题从“排序矩阵”转换为“排序向量”。我从未听说过矩阵的距离度量，但我听说过向量的距离度量。

您可以使用“差异总和”排序，也称为汉明距离。（对于每个不同的元素，添加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)

现在进行一些即兴分析...

10^6个矩阵（或其对应的向量）中的元素。
O(n)距离度量。
- 但它是O(n)比较。如果每个数组访问具有O(m)时间，则您将具有O(n*(n+n)) = O(n^2)度量。因此，您必须具有<O(n)访问。事实证明，根据SGI的STL网站，“std::vector []”运算符提供“平摊常数时间访问任意元素”。
只要您有足够的内存来存储k*2*10^6，其中k是您正在管理的矩阵数量，这是一个使用大量内存以换取线性的工作解决方案。