关于如何加快距离计算的建议

Question

考虑以下课程:

class SquareErrorDistance(object):
    def __init__(self, dataSample):
        variance = var(list(dataSample))
        if variance == 0:
            self._norm = 1.0
        else:
            self._norm = 1.0 / (2 * variance)

    def __call__(self, u, v): # u and v are floats
        return (u - v) ** 2 * self._norm

我用它来计算矢量的两个元素之间的距离.我基本上为使用此距离度量的向量的每个维度创建该类的一个实例(存在使用其他距离度量的维度).分析表明,__call__这个类的功能占我实现的90%的运行时间(谁会想到).我认为没有任何纯Python方法可以加快速度,但是如果我用C实现它呢？

如果我运行一个简单的C程序,只使用上面的公式计算随机值的距离,它比Python快几个数量级.所以我尝试使用ctypes并调用一个执行计算的C函数,但显然参数和返回值的转换非常昂贵,因为生成的代码要慢得多.

我当然可以在C中实现整个knn并且只是调用它,但问题是,就像我描述的那样,我对向量的某些维度使用不同的距离函数,并且将这些函数转换为C将是太多的工作.

那么我有什么选择呢？使用Python C-API编写C函数会消除开销吗？有没有其他方法可以加快计算速度？

Answer 1

以下 cython 代码（我意识到第一行__init__是不同的，我用随机的东西替换了它，因为我不知道var，而且因为无论如何它并不重要 - 你说的__call__是瓶颈）：

cdef class SquareErrorDistance:
    cdef double _norm

    def __init__(self, dataSample):
        variance = round(sum(dataSample)/len(dataSample))
        if variance == 0:
            self._norm = 1.0
        else:
            self._norm = 1.0 / (2 * variance)

    def __call__(self, double u, double v): # u and v are floats
        return (u - v) ** 2 * self._norm

通过简单的 setup.py 进行编译（只是文档中更改了文件名的示例），在简单设计的基准测试中，它的性能比等效的纯 python 好近 20 倍timeit。请注意，唯一更改的是字段和参数cdef的 s 。我认为这非常令人印象深刻。_norm__call__