My ACCU 2016 keynote video available online

[Jens Müller via Digitalmars-d-announce]

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