On Thursday, 19 May 2016 at 22:02:53 UTC, Andrei Alexandrescu
wrote:
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?
What if you stomped over an index in a that has as an equal index
in b (it could be anywhere in b). After the loop finishes you
restore the index in a. But how do you address the values for the
stomped over index if needed?
For instance test it on
a = [2]
b = [2,3]
Note the 2 in b could be anywhere.
I think you can check for
if (a[i].idx == sentinelIdx) break;
instead of
if (i == imax || j == jmax) break;
Jens
