擅长:python、mysql、java
<p>作为优化,如果在距离0处找到一个点,则可以利用已找到最近点的事实,并利用使距离平方最小的点使距离最小的事实:</p>
<pre><code>def sdist(p,q):
return (p[0]-q[0])**2 + (p[1]-q[1])**2
def closestPoint(p,points):
candidate = points[0]
currentMin = sdist(p,candidate)
for q in points[1:]:
d = sdist(p,q)
if d == 0: return q
if d < currentMin:
currentMin = d
candidate = q
return candidate
def closestPoints(pointsA,pointsB):
return [(p,closestPoint(p,pointsB)) for p in pointsA]
</code></pre>
<p>要测试它:</p>
<pre><code>from random import randint
ListA = [(randint(0,1000),randint(0,1000)) for i in range(5000)]
ListB = [(randint(0,1000),randint(0,1000)) for i in range(5000)]
</code></pre>
<p>那么</p>
<pre><code>pairs = closestPoints(ListA,ListB)
</code></pre>
<p>在我2岁的笔记本电脑上大约需要18秒</p>