3

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

3 回答 3

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()并预先计算展平矩阵，将展平向量存储在一个向量（或另一个具有随机索引上限的容器）中。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)

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

  • 10^6矩阵（或其对应的向量）中的元素。
  • 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您正在管理的矩阵的数量在哪里，这是一个使用大量内存来换取线性的工作解决方案。
于 2009-08-28T19:56:06.980 回答
0

（a）我不完全理解您要完成的工作，但是如果您想比较两个矩阵在同一索引处是否具有相同的值，则使用元素矩阵乘法就足够了（也应该为稀疏实现） ):

matrix3 = element_prod (matrix1, matrix2);

这样，您将获得每个索引：

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

因此，生成的 matrix3 将在一行中提供您的解决方案:)

于 2009-08-27T14:53:34.637 回答
0

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

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

您的问题可以重新表述为：我如何有效地对由 2d 位图表示的天文大数字进行排序（n = 100，因此 100x100 元素会给您一个像 2^10000 这样的数字）。

好问题 ！

于 2009-08-28T17:52:57.163 回答