c++ - 从 Eigen 中的 bool 矩阵采样

Question

我有一个这种形式的矩阵 A:

Eigen::Matrix<bool, n, m> A(n, m)

我想在“真实”的元素中获得一个随机元素。这样做的愚蠢方法是获取“真实”元素的数量 t，生成 1 和 t 之间的随机数并迭代:

//r = random number
int k = 0;
for (int i = 0; i < A.rows(); ++i)
    for (int j = 0; j < A.cols(); ++j)
    {
        if (A(i, j))
            ++k;
        if (k == r)
            std::cout << "(" << i << ", " << j << ")" << std::endl;
    }

当需要多个样本且矩阵很大时，此解决方案非常慢。关于我应该如何处理这件事有什么建议吗？

简而言之:我想找到一种有效的方法来获取上述矩阵的第 i 个“真”元素。

Answer 1

你可以使用 Eigen::SparseMatrix相反。

Eigen::SparseMatrix<bool> A(n, m);

通过其压缩(或非压缩)列/行存储方案，您可以在 O(m)/O(n) 时间或 O(log (m)) 与二进制搜索。

您可以使用 COO格式实用程序 Eigen::Triplet在 O(1) 时间内找到第 r 个非零元素。

std::vector<Eigen::Triplet<bool> > a(num_nonzeros);

是的，因为它是一个 bool 矩阵，所以也不需要存储值。