Re: [Algorithms] Sparse matrix combination

[Ash H. <hen...@gm...>]

If you're using std::map you're using std::pair already, why not use
them as keys too? They have operator< defined something like:
// l < r
l.first < r.first || !(r.first < l.first) && l.second < r.second

|1 0 0 0 0 0 0 0 0 0|
|0 0 0 0 0 2 0 0 0 3|
|0 0 0 0 0 0 0 0 0 0|
|0 0 0 0 4 0 0 0 0 0|

typedef std::map<std::pair<unsigned int, unsigned int>,
your_numerical_type> sparse_matrix;
sparse_matrix a, b, c; // c for result

a[make_pair(0,0)] =3D 1;
a[make_pair(1,5)] =3D 2;
a[make_pair(1,9)] =3D 3;
a[make_pair(3,4)] =3D 4;

// ... and so on for b

That should work for any M x N matrix I would hope, so it could be far
from optimal if you've got more constraints to work with, I'm not
sure. Probably far from optimal regardless, but I'm not claiming to be
a database fellow (I expect I'd be saying 'tuple' a lot more by now,
if I were). At the very least I'd hope it to be a bit better than a
map of maps.

I can't see that you've said whether the two matrices you're lerping
will have elements in the same places or not (not sure if the
alternative makes sense in your context). If so lerping would be a
nice iteration over the two input maps.

If you need to preserve the matrices a and b, copy a to c before
lerping and use that as the result, otherwise just use a. As you've
already got identical binary trees constructed in a and b why spend
time constructing another, I say, just copy the thing. You might even
be able to speed up the creation of the input matrices this way too?
Thinking about it, if your situation fits it, you could map a pair to
a pair, and have the value of the map be the pair of inputs, which
makes using an STL algorithm do your lerping much easier (you've only
got one map to iterate over then). I'll ignore that idea for now and
finish off the example I was running with.

sparse_matrix c; // c for result if you're keeping a around
c =3D a;
sparse_matrix::iterator ia =3D c.begin();
sparse_matrix::const_iterator ib =3D b.begin();
sparse_matrix::const_iterator lasta =3D c.end();
// if you're sure the matrices are the same size no need to check b.last()

while(ia !=3D lasta)
{
  // depending on you're calling convention you might
  // get faster results with the lerp arguments swapped about?
  (*ia).second =3D  your_lerp(lerp_amount, (*ia).second, (*ib).second);
  ++ia;
  ++ib;
}

I couldn't think of an STL algorithm off the top of my head that would
get what I wanted there, but with a couple of functors you could
probably adapt something.

I'd actually be severely tempted to go with the map of index pair to
input pair if you can swing it. Not sure if any of this is going to be
any help to you, it's got severe limitations, but like I said, if
you're planning on using nested maps this might be an alternative :)

Cheers.

--  Ash