PYTHON - 列表中最近对之间的距离

Question

你怎么写一个函数，来分析一个列表或者坐标对，找出哪个坐标对是最近的，使用距离公式，然后只返回那个距离d。

下面是一个输入和输出的例子：

>>>function([[x1,y1],[x2,y2],[x3,y3]])
>>>d

Answer 1

这里有一个简单的暴力破解方法，类似于维基百科上Sukrit链接的内容，不过效率稍微提高了一点：

def min_dist(pair_list):
    n = len(pair_list)
    new_min_dist = float('inf')
    for i in xrange(n):
        for j in xrange(i + 1, n):
            new_x_dist = pair_list[i][0] - pair_list[j][0]
            new_y_dist = pair_list[i][1] - pair_list[j][1]
            new_min_dist = min(new_x_dist * new_x_dist + new_y_dist * new_y_dist, new_min_dist)
    return new_min_dist ** 0.5

这里有几个提高效率的小技巧：

• 把平方根的计算放到最后，这样只用计算一次（平方根和幂运算都比较耗费资源）。
• 用 ** 0.5 来代替 math.sqrt，因为对于浮点数来说，幂运算比计算平方根要快。
• 用乘法代替 ** 2，因为幂运算比乘法要耗费更多资源。
• 每对数只考虑一次（维基百科的例子也是这样做的）。
• xrange 占用的内存更少，而且不需要分配内存块，所以在点数少于大约32000个时，它比 range 稍微快一点。（Python 3的语法会有所不同。）

Answer 2

正如我所说，类似的问题在这里被问过。下面是解决方案

a = [(5, 3), (9, 0), (4, 6), (2, 2), (0, 0)]

from math import sqrt


def function(a):
    distances = []
    def compute(fp, sp):
        return sqrt((fp[0]-sp[0])**2 + (fp[1] - sp[1])**2)

    for p in a:
        b = a[:]
        b.remove(p)
        distances.append(compute(p, min(b, key=lambda x: compute(x, p))))

    return min(distances)


print(function(a))

输出结果是：2.8284271247461903，这个值等于sqrt(8)，因为(2-0)²+(2-0)²等于8