My ACCU 2016 keynote video available online

[Andrei Alexandrescu via Digitalmars-d-announce]

On 05/19/2016 06:50 PM, Jens Müller wrote:
> What if you stomped over an index in a that has as an equal index in b
> (it could be anywhere in b).

Hmmm, you're right. So that doesn't work, or at least not efficiently 
(the fixup would entail a binary search in b).

How about this idea: arrange things such that a.back.idx <= b.back.idx 
(i.e. swap them if not so). Then stomp b.back.idx with size_t.max. Your 
kernel is:

if (a[i].idx < b[j].idx) {
   if (i == imax) break; // check needed
   i++;
} else if (a[i].idx > b[j].idx) {
   j++; // no check needed
} else {
   // no check needed
   r += a[i++].val * b[j++].val;
}

The fixup needs only to account for the case a.back.idx == b.back.idx. 
In fact I like this a lot better than others because it works real fast 
for identical vector (taking the norm) or similar vectors (often the 
case). Works?


Andrei