Dot product of sparse vectors

Hello,

I have a simple sparse vector implementation

pub struct Vector<T> {
    values: Vec<T>,
    positions: Vec<usize>,
}

where the 1 0 0 2 vector would be represented with values = vec![1, 2] and positions = vec![0, 3]. That is, I store only the value and position of non zero elements.

I want to compute the dot product of two such vectors. So far, this is my implementation

https://play.rust-lang.org/?version=stable&mode=debug&edition=2018&gist=29bfb2bfff8bce0be0ff4e944e6cabec

Is it possible to rewrite this algorithm using iterators?

Also, I'm not sure why I need to specify the output type of the Mul trait and to had the Clone trait. I basically did those two things because the compiler told me to.

1 Like

Please share your via playground to make it easier to edit and help you!

It looks like you have a bug in your code, self.values()[i].clone() * self.values()[j].clone() should get the values from Vector::position, right? Not use i and j directly.


While it is possible to rewrite this in terms of iterators, it won't be worth doing so. The main loop heavily depends on the state and history of i and j. That doesn't translate well to iterators.

You can rewrite it a bit to consolidate some checks, but I'm not sure if I like it better.

There was indeed a bug in the line you pointed out, but it is because it should be other.values() and not self.values() in the right side of the product. However to logic is good.

I did not about the playground before. Thank you for tips. I will try to use it in the future. I added a main function with a small example to the link you provide.

https://play.rust-lang.org/?version=stable&mode=debug&edition=2018&gist=29bfb2bfff8bce0be0ff4e944e6cabec

I believe that you are right regarding iterators.

However, I'm still confused about why I need Mul<Output = T>, but only Add in the trait list. Also, why do I need to clone the values?

The multiplication operator can be overloaded to return a different type from either of the inputs, so you need to specify which output type you need. You do this by Mul<Output = T>. If you don't, then the compiler can't know that the output type will always be T, so it rejects your code.

You need clone because the indexing operator works based off of references, so you can't move out of them. So to get owned values of T, you need to clone the items from the Vector.

I see, I misinterpreted how the sparse vec worked. Oops :sweat_smile:.

1 Like

You need Mul<Output = T> because the type outputted by self.values()[i].clone() * other.values()[j].clone() is never made explicit; the only information the compiler gets is that it's the same type that can be added to T.

You have to clone the values because Mul takes its arguments by value - a * b moves a and b. You could reference them, but then you'd need &T: Mul.

trait Zero: Add<Self, Output = Self>
You didn't need to have the Add bound at all as it's implied by theZero` trait.

2 Likes

Thanks, I was able to figure something using &T: Mul. This is the behavior I wanted to achieve since T could be expensive to clone.

Good to know!