Use sparse dot product by merging indices: only equal coordinate indices can contribute, so merge the two increasing index streams:
def dotProduct(vec1: Node, vec2: Node): Double = {
require(vec1 != null && vec2 != null)
require(vec1.index == vec2.index, "dimension mismatch")
var p = vec1.next
var q = vec2.next
var answer = 0.0
while ((p ne vec1) && (q ne vec2)) {
if (p.index < q.index) p = p.next
else if (q.index < p.index) q = q.next
else {
answer += p.value * q.value
p = p.next
q = q.next
}
}
answer
}The loop invariant states that the accumulator contains all common-coordinate products already passed, while no unprocessed smaller coordinate can acquire a future partner. If one current index is smaller, the other list has no remaining entry at that index, so its product is zero. Equal indices add their product and advance both. Once either list ends, all remaining coordinates of the other have zero partners.
Thus the code computes the dot product in coordinate order, subject to floating-point rounding, using time and constant auxiliary storage. It does not scan implicit zeros or alter either vector, and it also handles both arguments referring to the same header.
Articles by others on the same topic
There are currently no matching articles.