I am implementing a certain algorithm that works like this:

  1. Create a closed contour (list) of elements in a matrix, where closed means that the last element is adjacent (by row, column) to the first.
  2. Weight (multiply) each of the elements addressed by the contour by a scalar associated with the element's position in the matrix (i.e., lookup in a (sparse) matrix of equal dimension), except
    1. If the next element in the contour has a different weight, reweight both elements by an (averaging) funuction of the two element's weights.
  3. Sum the weighted elements.

If I want to keep this general, I see two ways of doing it:

  1. As I create the contour, check and see if the next element in the contour has a different associated weight, and mark it in another list/dict for processing in 2.1, or
  2. Compute the first difference in all four directions (2D matrix case) for the whole matrix, and just look up the difference based on the direction of the contour (in terms of elements) at that point.

Some problems with approach (1) are; that every step in building the contour has to look at one of the values used in the next step, and it mixes responsibilities as well (possible to obviate by multiple iteration passes in code). It does only compute the data it needs for the job.

On the other hand, approach (2) creates four copies of the matrix, which could be huge. It's much easier to program for, however.

I'm leaning toward approach (1), but I would like to know if (2) could actually be more efficient, or if there's another approach I haven't considered.

  • Usually a sparse matrix is better handled as list of coordinates. But there are so many dependencies that likely nobody can give a general advise. YMMV, you know. – qwerty_so Nov 15 '16 at 22:05

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.