My ACCU 2016 keynote video available online

Jens Müller via Digitalmars-d-announce digitalmars-d-announce at puremagic.com
Fri May 20 11:13:10 PDT 2016


On Friday, 20 May 2016 at 14:14:18 UTC, Andrei Alexandrescu wrote:
> 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?

No it doesn't work because you need to break in the last case. 
Consider the case when the last element of a is equal to an 
element in b. Next iteration you overrun a.
But optimizing for similar vectors is interesting.

Jens


More information about the Digitalmars-d-announce mailing list