Перебор ненулевых элементов разреженной матрицы uBlas

У меня есть следующая разреженная матрица, содержащая элементы O(N)

boost::numeric::ublas::compressed_matrix<int> adjacency (N, N);

Я мог бы написать двойной цикл грубой силы, чтобы просмотреть все записи за O(N^2) времени, как показано ниже, но это будет слишком медленно.

for(int i=0; i<N; ++i)
   for(int j=0; j<N; ++j)
       std::cout << adjacency(i,j) std::endl;

Как я могу перебрать только ненулевые записи за время O(N)? Для каждого ненулевого элемента я хотел бы иметь доступ к его значению и индексам i,j.


c++ boost sparse-matrix ublas
person D R    schedule 25.11.2009    source источник

Ответы (1)


arrow_upward
15
arrow_downward

Вы можете найти ответ в этом FAQ: Как выполнить итерацию по всем ненулевым элементам?

В вашем случае это будет:

typedef boost::numeric::ublas::compressed_matrix<int>::iterator1 it1_t;
typedef boost::numeric::ublas::compressed_matrix<int>::iterator2 it2_t;

for (it1_t it1 = adjacency.begin1(); it1 != adjacency.end1(); it1++)
{
  for (it2_t it2 = it1.begin(); it2 != it1.end(); it2++)
  {
    std::cout << "(" << it2.index1() << "," << it2.index2() << ") = ";
    std::cout << *it2 << std::endl;
  }
}
person Gert    schedule 07.12.2009
comment
Важное примечание, которое я забыл добавить: тип организации хранения, который вы выбираете для сжатой матрицы, имеет значение, потому что он решает, каким будет самый быстрый способ итерации сжатой матрицы. Если у вас есть row_major в качестве типа хранилища, мой пример выше — самый быстрый способ выполнить итерацию. Если вы выберете column_major, вам придется поменять местами внутренний и внешний цикл, т. е. цикл сначала по столбцам будет самым быстрым. - person Gert; 07.12.2009
comment
boost будет повторяться в зависимости от представления хранилища (основной ряд или основной столбец). Таким образом, одни и те же циклы выше будут работать для любого представления. Никаких изменений вносить не нужно. - person user236215; 20.09.2010
comment
Извините, что наткнулся на старый пост. Я не уверен, что этот код действительно работает, см. lists.boost.org/ MailArchives/ublas/2006/11/1516.php. По моему опыту, он будет перебирать каждый элемент. - person Mikhail; 07.07.2011