c++ - 遍历两个稀疏矩阵

Question

我正在使用包含 bool 值的 boost 稀疏矩阵并尝试编写一个比较函数以将它们存储在 map 中。这是一个非常简单的比较函数。基本上，这个想法是将矩阵视为一个二进制数(在被展平为一个 vector 之后)并根据该数字的值进行排序。这可以通过以下方式完成:

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

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

让我伪代码弄清楚我认为你在问什么

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()并预先计算展平矩阵，将展平 vector 存储在 vector (或具有随机索引上限的另一个容器)中。 flatten()可以像将每一行(或列)与前一行连接一样简单(如果你有一个恒定时间函数来获取一行/列，这可以在线性时间内完成)。

这会产生一组大小约为 10^6 的 vector 。这是一种权衡——保存这些信息而不是即时计算它。如果您要在进行过程中进行大量比较，这将很有用。

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

那么，我们就把算法题从“序矩阵”变成了“序 vector ”。我从未听说过矩阵的距离度量，但我听说过 vector 的距离度量。

您可以使用又名汉明距离的“差异之和”排序。 (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) 

现在做一些即兴分析....

• 10^6矩阵中的元素(或其对应的 vector )。
• O(n)距离度量。
  • 但它是O(n)比较。如果每个数组访问都有 O(m)时间，那么你会得到一个 O(n*(n+n)) = O(n^2)公制。所以你have有 < O(n)使用权。结果是 std::vector []根据 SGI 的 STL 站点，运算符提供“对任意元素的分摊常数时间访问”。
• 如果您有足够的内存来存储 k*2*10^6 , 其中k是您管理的矩阵的数量，这是一个有效的解决方案，它使用大量内存来换取线性。