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
