为什么来自 scipy.spatial.distance 的 cdist 如此之快？

Question

我想为 10060 个记录/点创建一个距离邻近矩阵，其中每个 record/point 具有 23 个属性，使用欧氏距离作为度量。我使用嵌套 for 循环编写代码来计算每个点之间的距离（导致 (n(n-1))/2) 计算）。花了很长时间（大约8分钟）。当我使用 cdist 时，它花费的时间少得多（仅 3 秒 !!!）。当我查看源代码时，cdist 还使用嵌套的 for 循环，而且它进行 n^2 计算（这比我的逻辑所做的比较次数要多）。 是什么让 cdist 执行得更快并给出正确的输出？ 请帮助我理解。提前致谢。

Answer 1

你是从哪里读到源代码的？ python code 调用（如果你在默认 metric='euclidean' 情况下一直跟着它）c 代码

static NPY_INLINE int
cdist_seuclidean(const double *XA, const double *XB, const double *var,
                 double *dm, const npy_intp num_rowsA, const npy_intp num_rowsB,
                 const npy_intp num_cols)
{
    npy_intp i, j;

    for (i = 0; i < num_rowsA; ++i) {
        const double *u = XA + (num_cols * i);
        for (j = 0; j < num_rowsB; ++j, ++dm) {
            const double *v = XB + (num_cols * j);
            *dm = seuclidean_distance(var, u, v, num_cols);
        }
    }
    return 0;
}

其中 seuclidean_distance 是

static NPY_INLINE double
seuclidean_distance(const double *var, const double *u, const double *v,
                    const npy_intp n)
{
    double s = 0.0;
    npy_intp i;

    for (i = 0; i < n; ++i) {
        const double d = u[i] - v[i];
        s += (d * d) / var[i];
    }
    return sqrt(s);
}

所以它实际上是一个三重循环，但这是高度优化的 C 代码。 Python for 循环很慢，它们会占用大量开销并且永远不应与 numpy 数组一起使用，因为 scipy/numpy 可以利用 [=15= 中保存的底层内存数据] 以 python 无法做到的方式反对。

为什么来自 scipy.spatial.distance 的 cdist 如此之快？

Why cdist from scipy.spatial.distance is so fast?

python

euclidean-distance

scipy-spatial