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

Reply via email to