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;

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;


Reply via email to