计算向量之间的距离时如何避免由双重“ for循环”引起的二次计算 [英] How to avoid quadratic computation resulting from double 'for loop' when computing distances between vectors

问题描述

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

Given the following code that computes distances between vectors in list '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()

有没有办法避免double'for循环导致的二次复杂性'？

Is there a way to avoid the quadratic complexity that will result from the double ‘for loop’?

double for循环的计算（二次）== 3X3 = 9

Computation as a result of the double for loop (quadratic) ==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] =

预先感谢您的建议。

推荐答案

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

To avoid duplicate pairs nested loop should go upwards from the index of the outer loop, i.e.:

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

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

Or use a solution provided by the standard library:

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

这篇关于计算向量之间的距离时如何避免由双重“ for循环”引起的二次计算的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！