My ACCU 2016 keynote video available online

[Andrei Alexandrescu via Digitalmars-d-announce]

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