0

给定以下代码计算列表“vect”中向量之间的距离：

import numpy as np
vect=([0.123, 0.345, 0.789], [0.234, 0.456, 0.567],[0.134, 0.246, 0.831])
def kn():
    for j in vect:
        c=np.array(j)
        for z in vect:
            p=np.array(z)
            space = np.linalg.norm(c-p)
            print space
kn()

有没有办法避免双重“for循环”导致的二次复杂性？

双 for 循环的计算结果（二次）==3X3=9

Ideal computation (what I want) should be (3):
[0.123, 0.345, 0.789] and [0.234, 0.456, 0.567] =
[0.123, 0.345, 0.789] and [0.134, 0.246, 0.831] =
[0.234, 0.456, 0.567] and [0.134, 0.246, 0.831] =

提前感谢您的建议。

4

2 回答 2

2

为了避免重复对嵌套循环应该从外部循环的索引向上，即：

for i, v1 in enumerate(vect):
    for j in xrange(i + 1, len(vect)):
        a = np.array(v1)
        b = np.array(vect[j])
        space = np.linalg.norm(b - a)
        print space

或者使用标准库提供的解决方案：

import itertools

for v1, v2 in itertools.combinations(vect, 2):
    a = np.array(v1)
    b = np.array(v2)
    space = np.linalg.norm(b - a)
    print space
于 2013-08-02T10:48:47.350 回答
2

其他人指出，您无法避免二次复杂度。但是如果你关心的是性能，你可以通过使用来大大加快速度scipy.spatial.distance.pdist，这将使所有的循环和函数调用都发生在 C 中，而不是 Python。以下代码返回一个方形对称数组，但它只进行n *(n-1)/2计算：

from scipy.spatial.distance import pdist

pairwise_distances = pdist(vect, metric='euclidean', p=2)

如果您想要一个只有唯一的非对角线值的扁平数组，您可以使用scipy.spatial.distance.squareform：

from scipy.spatial.distance import pdist, squareform

pairwise_distances = squareform(pdist(vect, metric='euclidean', p=2))

在您的情况下，pairwise_distances将是一个 3 元素长数组。

于 2013-08-02T12:49:26.490 回答