python - 有没有办法让这个 Python kNN 函数更高效？

Question

在遇到 MATLAB 问题之后我决定试试 Python:

我编写了一个函数，当样本属于我自己的类时使用我自己的距离函数计算 kNN:

def closestK(sample, otherSamples, distFunc, k):
"Returns the closest k samples to sample based on distFunc"
    n = len(otherSamples)
    d = [distFunc(sample, otherSamples[i]) for i in range(0,n)]
    idx  = sorted(range(0,len(d)), key=lambda k: d[k])
    return idx[1:(k+1)]

def kNN(samples, distFunc, k):
    return [[closestK(samples[i], samples, distFunc, k)] for i in range(len(samples))]

这是距离函数:

@staticmethod    
def distanceRepr(c1, c2):
    r1 = c1.repr
    r2 = c2.repr
    # because cdist needs 2D array
    if r1.ndim == 1:
        r1 = np.vstack([r1,r1])
    if r2.ndim == 1:
        r2 = np.vstack([r2,r2])

    return scipy.spatial.distance.cdist(r1, r2, 'euclidean').min()

但与“普通”kNN 函数相比，即使使用“粗暴”算法，它的运行速度仍然慢得惊人。我做错了什么吗？

更新

我正在添加类的构造函数。属性 repr 包含一组向量(从 1 到任意值)，距离计算为两组 repr 之间的最小欧氏距离。

class myCluster:
    def __init__(self, index = -1, P = np.array([])):
        if index ==-1 :
            self.repr = np.array([])
            self.IDs = np.array([])
            self.n = 0
            self.center = np.array([])
        else:
            self.repr = np.array(P)
            self.IDs = np.array(index)
            self.n = 1
            self.center = np.array(P)

和其余相关代码(X 是一个矩阵，其行是样本，列是变量):

level = [myCluster(i, X[i,:]) for i in range(0,n)]
kNN(level, myCluster.distanceRepr, 3)

更新 2

我做了一些测量，花费大部分时间的线是

d = [distFunc(sample, otherSamples[i]) for i in range(0,n)]

所以 distFunc 有一些东西。当我将其更改为返回时

np.linalg.norm(c1.repr-c2.repr)

即“正常”向量计算，无排序，运行时间保持不变。所以问题出在这个函数的调用上。使用类将运行时间改变 60 倍有意义吗？

Answer 1

您只是遇到了 Python 的缓慢问题(或者更确切地说，我猜应该是 CPython 解释器)。来自 wikipedia :

NumPy targets the CPython reference implementation of Python, which is a non-optimizing bytecode compiler/interpreter. Mathematical algorithms written for this version of Python often run much slower than compiled equivalents. NumPy seeks to address this problem by providing multidimensional arrays and functions and operators that operate efficiently on arrays. Thus any algorithm that can be expressed primarily as operations on arrays and matrices can run almost as quickly as the equivalent C code.

并且来自 Scipy FAQ:

Python’s lists are efficient general-purpose containers. They support (fairly) efficient insertion, deletion, appending, and concatenation, and Python’s list comprehensions make them easy to construct and manipulate. However, they have certain limitations: they don’t support “vectorized” operations like elementwise addition and multiplication, and the fact that they can contain objects of differing types mean that Python must store type information for every element, and must execute type dispatching code when operating on each element. This also means that very few list operations can be carried out by efficient C loops – each iteration would require type checks and other Python API bookkeeping.

_{注意这不仅仅涉及 Python；有关更多背景，请参见例如this和 this question在 SO 上。}

由于动态类型系统和解释器的开销，如果 Python 不能利用各种编译的 C 和 Fortran 库(例如 Numpy ).此外，还有 Numba 和 PyPy 等 JIT 编译器，它们试图让 Python 代码的执行速度更接近静态类型的编译代码。

底线:与卸载到快速 C 代码的工作相比，您在普通 Python 中所做的工作更多。我想您需要采用更像是“面向数组”的编码风格而不是面向对象的编码风格，以便使用 Numpy 实现良好的性能(MATLAB 在这方面非常相似)。另一方面，如果您使用更高效的算法(请参阅 Ara 的回答)，那么 Python 的速度慢可能就不是问题。