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