Отбора проб из булевой матрицы в Эйгене

Question

У меня есть матрица А эта форма:

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

и я хочу, чтобы получить случайный элемент среди тех, которые «истины». Глупый способ сделать это было бы, чтобы получить число «истинного» элементы т, генерировать случайное число в диапазоне от 1 до т и итерации:

//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); 

С его сжатым (или нет) схемы хранения столбца/строки, можно найти r -й ненулевой элемент в O (M)/O (п), или O (журнал (м)) с бинарным поиском.

Вы можете использовать утилиту COOEigen::Triplet, чтобы найти r -й ненулевой элемент в O (1) раз.

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

И да, так как это матрица bool, хранение значений также необязательно.