Я использую форсированные разреженные матрицы, содержащие bool, и пытаюсь написать функцию сравнения для сохранения их на карте. Это очень простая функция сравнения. По сути, идея состоит в том, чтобы смотреть на матрицу как двоичное число (после сглаживания в вектор) и сортировать по значению этого числа. Это можно сделать следующим образом:
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) если равны, возьмите следующие ненулевые ячейки в каждой матрице и повторите. К сожалению, в коде это чрезвычайно утомительно, и я беспокоюсь об ошибках.
Что мне интересно, так это (а) есть ли лучший способ сделать это и (б) есть простой способ получить "следующую ненулевую ячейку" для обеих матриц? Очевидно, что я не могу использовать вложенные циклы 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);
}