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

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__ 函数占据了我的 knn 实现的 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 编译（只是 文档中的示例（文件名已更改）），在简单设计的 timeit 基准测试中，它的性能比同等的纯 Python 好近 20 倍。请注意，唯一更改的是 _norm 字段和 __call__ 参数的 cdef。我认为这非常令人印象深刻。

Answer 2

这可能没有多大帮助，但您可以使用嵌套函数重写它：

def SquareErrorDistance(dataSample):
    variance = var(list(dataSample))
    if variance == 0:
        def f(u, v):
            x = u - v
            return x * x
    else:
        norm = 1.0 / (2 * variance)
        def f(u, v):
            x = u - v
            return x * x * norm
    return f