6
\$\begingroup\$

I'm trying to implement a sparse vector (most elements are zero) dot product calculation. My major idea is to represent each sparse vector as a list (which holds only non-zero dimensions), and each element in the list is a 2-dimensional tuple -- where first dimension is index of vector, and 2nd dimension is its related value.

Any comments about my code improvement, bugs, etc. are appreciated. I also welcome any good advice for in general how to best implement dot product for sparse vector using Python.

def dot_product(v1, v2):
    i1 = 0
    i2 = 0
    result = 0.0
    while i1 < len(v1) and i2 < len(v2):
        if v1[i1][0] == v2[i2][0]:
            result += v1[i1][1] * v2[i2][1]
            i1 += 1
            i2 += 1
        elif v1[i1][0] > v2[i2][0]:
            i2 += 1
        else:
            i1 += 1

    return result
if __name__ == "__main__":
    v1 = [(0, 2), (1, 4), (5, 6)] # (2,4,0,0,0,6)
    v2 = [(1,3),(2,4),(5,7)] #(0,3,4,0,0,7)
    print dot_product(v1, v2)
\$\endgroup\$
4
\$\begingroup\$

Valid. But your code is messy. You are taking one step away from the original traditional problem, and that actually becomes a problem form your code.

Your actually better off with the one dimensional arrays then the two dimensional tuples. Tuples may be the wrong data type to use for your problem to resolve itself nicely.


Styling notes: This:

def dot_product(v1, v2):
    ...

suggest to me that v1 and v2 are vectors, not a list of vectors, but by changing to:

def dot_product1(v1: [()], v2: [()]):
    ...

the obscurity magically disappears.

This method of commenting your code is called annotations and is commonly used in python, I like them a lot.


The

    ...
    return result
if __name__ == "__main__":
    ...

could be more readable if:

    ...
    return result


if __name__ == "__main__":
    ...

An analogue solution which will scale better is

def get_pointers(v: tuple):
    return {key: value for key, value in enumerate(v) if value}


def sparse_vector_dot(a: dict, b: dict):
    result = 0
    for key, value in a.items():
        if key in b:
            result += b[key] * value
    return result


def main():
    a = (2, 4, 0, 0, 0, 6)
    b = (0, 3, 4, 0, 0, 7)
    a, b = get_pointers(a), get_pointers(b)
    print(sparse_vector_dot(a, b))

and the function sparse_vector_dot could be written as:

def sparse_vector_dot_oneliner(a: dict, b: dict):
    return sum(b[key]*value for key, value in a.items() if key in b)

It will scale better since we are never checking what we don't have to check, the only thing we have to check is if there is a corresponding index in the other list (now dict).

| improve this answer | |
\$\endgroup\$
  • \$\begingroup\$ Thanks for your comments and vote up Simon. But do you think store sparse vector in an ordered list (order by index) is a better way in terms of efficiency (merge ordered index, similar to merge sort)? \$\endgroup\$ – Lin Ma Dec 3 '16 at 8:20
  • 1
    \$\begingroup\$ I seem to fail to see why it should be ordered in a list. So seems like a waste of space and operations.. Membership testing in dict is O(n) and mergesort is O(n) so it so seems like the would be as fast, but I don't don't think so. \$\endgroup\$ – Simon Dec 3 '16 at 15:29
  • \$\begingroup\$ Thanks Simon, for your comments, "so seems like the would be as fast" which one do you think faster? I see you said both dict and mergesort are of O(n)? \$\endgroup\$ – Lin Ma Dec 4 '16 at 18:29
2
\$\begingroup\$

Docstrings are good practice, and in this case, a doctest would be very appropriate as well.

The i1 += 1 and i2 += 1 statements are tedious. What you want is the intersection of the first elements. A dict representation would be more appropriate than a list of pairs. Then you can take advantage of set.intersection(…).

In fact, if you write the code eloquently, you can just as easily multiply any number of vectors at once.

from operator import mul

def dot_product(*vectors):
    """
    Compute the dot product of sparse vectors, where each vector is
    represented as a list of (index, value) tuples.

    >>> v1 = [(0, 2), (1, 4), (5, 6)]       # (2, 4, 0, 0, 0, 6)
    >>> v2 = [(1, 3), (2, 4), (5, 7)]       # (0, 3, 4, 0, 0, 7)
    >>> dot_product(v1, v2)
    54
    """
    vectors = [dict(v) for v in vectors]
    indices = (set(v.iterkeys()) for v in vectors)
    return sum(
        reduce(mul, (v[i] for v in vectors)) for i in set.intersection(*indices)
    )
| improve this answer | |
\$\endgroup\$
  • \$\begingroup\$ Thanks for the advice 200_success, vote up for your reply. One more comments, do you think there is benefit leveraging ordered index (increasing index number) -- you can refer to my original code. Comparing to brute force dictionary look-up as your implementation? If there is or there does not have benefit, could you elaborate a bit more? Thanks. \$\endgroup\$ – Lin Ma Dec 12 '16 at 3:53
  • \$\begingroup\$ Your solution is likely slightly faster, but requires the indices to be monotonically increasing. The dictionary-based solution is O(|v1| + |v2|), which is the same as complexity as your original solution. Therefore, I would still consider it to be efficient and not "brute-force". \$\endgroup\$ – 200_success Dec 12 '16 at 6:18

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.