Python:更快地计算两个字典的余弦相似度

Question

我有两个命令:

d1 = {1234: 4, 125: 7, ...}
d2 = {1234: 8, 1288: 5, ...}

字典的长度从 10 到 40000 不等。为了计算余弦相似度，我使用这个函数:

from scipy.linalg import norm
def simple_cosine_sim(a, b):
    if len(b) < len(a):
        a, b = b, a

    res = 0
    for key, a_value in a.iteritems():
        res += a_value * b.get(key, 0)
    if res == 0:
        return 0

    try:
        res = res / norm(a.values()) / norm(b.values())
    except ZeroDivisionError:
        res = 0
    return res 

是否可以更快地计算相似度？

UPD:使用 Cython 重写代码速度提高 15%。感谢@Davidmh

from scipy.linalg import norm

def fast_cosine_sim(a, b):
    if len(b) < len(a):
        a, b = b, a

    cdef long up, key
    cdef int a_value, b_value

    up = 0
    for key, a_value in a.iteritems():
        b_value = b.get(key, 0)
        up += a_value * b_value
    if up == 0:
        return 0
    return up / norm(a.values()) / norm(b.values())

Answer 1

如果索引不太高，您可以将每个字典转换为数组。如果它们很大，您可以使用稀疏数组。然后，余弦相似度只会将它们相乘。如果您必须重复使用同一字典进行多次计算，则此方法效果最佳。

如果这不是一个选项，Cython 应该相当快，只要您注释 a_value 和 b_value。

编辑:看看你的 Cython 重写，我看到了一些改进。第一件事是执行 cython -a 生成编译的 HTML 报告，并查看哪些内容已加速，哪些内容未加速。首先，您将“up”定义为 long，但您正在对整数求和。另外，在您的示例中，键是整数，但您将它们声明为 double 。另一件简单的事情是将输入键入为字典。

此外，检查 C 代码，似乎存在一些无检查，您可以使用 @cython.nonechecks(False) 禁用这些检查。

实际上，字典的实现非常高效，因此在一般情况下，您可能不会得到比这更好的结果。如果您需要充分利用代码，也许值得用 C API 替换一些调用:http://docs.python.org/2/c-api/dict.html

cpython.PyDict_GetItem(a, key)

但是，您将负责引用计数以及从 PyObject * 到 int 的转换，以获得可疑的性能提升。

无论如何，代码的开头看起来像这样:

cimport cython

@cython.nonecheck(False)
@cython.cdivision(True)
def fast_cosine_sim(dict a, dict b):
    if len(b) < len(a):
        a, b = b, a

    cdef int up, key
    cdef int a_value, b_value

还有一个问题:你的词典很大吗？因为如果不是，范数的计算实际上可能是一个重要的开销。

编辑2:另一种可能的方法是只查看必要的键。说:

from scipy.linalg import norm
cimport cython

@cython.nonecheck(False)
@cython.cdivision(True)
def fast_cosine_sim(dict a, dict b):
    cdef int up, key
    cdef int a_value, b_value

    up = 0
    for key in set(a.keys()).intersection(b.keys()):
        a_value = a[key]
        b_value = b[key]
        up += a_value * b_value
    if up == 0:
        return 0
    return up / norm(a.values()) / norm(b.values())

这在 Cython 中非常有效。实际性能可能取决于按键之间有多少重叠。