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