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

Reply via email to