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

Question

我想为 创建一个距离邻近矩阵10060 记录/点，其中每个记录/点有 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 可以利用 ndarray 中保存的底层内存数据。以python不能的方式对象。