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?


Reply via email to