Выборка из булевой матрицы в Eigen
У меня есть матрица А этой формы:
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-й «истинный» элемент вышеуказанной матрицы.
Решение
Вы могли бы использовать Eigen::SparseMatrix вместо.
Eigen::SparseMatrix<bool> A(n, m);
С его сжатой (или нет) схемой хранения столбцов / строк, вы можете найти r-ный ненулевой элемент за время O (m) / O (n) или O (log (m)) с двоичным поиском.
Вы могли бы использовать COO утилита форматирования Eigen::Triplet найти r-ный ненулевой элемент в O (1) времени.
std::vector<Eigen::Triplet<bool> > a(num_nonzeros);
И да, так как это матрица bool, хранить значения тоже не нужно.
Другие решения
Других решений пока нет …