稀疏向量点积

Question

我试图实现一个稀疏向量(大多数元素为零)点积计算。我的主要想法是将每个稀疏向量表示为一个列表(它只包含非零维)，列表中的每个元素都是二维元组，其中第一维是向量的索引，而二维是它的相关值。

任何关于我的代码改进，错误，等等的评论都是非常感谢的。我还欢迎任何关于如何最好地使用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)

Answer 1

有效。但你的代码很乱。你离原来的传统问题只有一步之遥，这实际上成为你的代码中的一个问题。

你最好用一维数组，然后用二维元组。元组可能是用于解决问题的错误数据类型，以便很好地解决问题本身。

造型说明:这：

def dot_product(v1, v2):
    ...

向我建议v1和v2是向量，不是向量列表，而是改为：

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

默默无闻神奇地消失。

这种注释代码的方法叫做注释，在python中经常使用，我非常喜欢它们。

这个

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

如果：

    ...
    return result


if __name__ == "__main__":
    ...

一个规模更大的模拟解决方案是

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))

函数sparse_vector_dot可以编写为：

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

因为我们从不检查我们不需要检查的内容，所以它的扩展性会更好，我们唯一需要检查的就是在另一个列表中是否有相应的索引(现在是dict)。

Answer 2

文档字符串是很好的实践，在这种情况下，博士考试也是非常合适的。

i1 += 1和i2 += 1语句很乏味。您想要的是第一个元素的交集。dict表示形式将比成对列表更合适。然后，您可以利用set.intersection(…)。

事实上，如果你写的代码很有说服力，你就可以一次很容易地乘以任意数量的向量。

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)
    )