On 05/19/2016 05:36 PM, Jens Müller wrote:
I'm not seeing it. Let me explain.
Consider the input a = [1] and b = [2, 3] (I only write the indices).
The smallest back index is 1, i.e., a.back is the chosen sentinel.
Nonono, you stamp the largest index over the smaller index. So you
overwrite a = [3] and you leave b = [2, 3] as it is.
Now you know that you're multiplying two correct sparse vectors in which
_definitely_ the last elements have equal indexes. So the inner loop is:
if (a[i].idx < b[j].idx) {
i++; // no check needed
} else if (a[i].idx > b[j].idx) {
j++; // no check needed
} else {
// check needed
r += a[i].val * b[j].val;
if (i == imax || j == jmax) break;
++i;
++j;
}
At the end you need a fixup to make sure you account for the last index
that you overwrote (which of course you need to save first).
Makes sense?
Andrei