优化algorithm（嵌套For … Next循环）

我写了下面这个程序，它从XYZ点列表（相应的列2 3和4）中提取给定距离和给定高程差的点对。 问题是它包含一个嵌套for循环，我相信会造成太多的迭代，因此对于大量的点（> 1000），例程会花费不合理的时间来完成。 我能做些什么来优化这个algorithm？

问候，

胺

Sub Test1() Columns("H:K").Select Selection.ClearContents c3 = 2 For c2 = 2 To 10 For c1 = c2 + 1 To 10 If Sqr((Cells(c2, 2) - Cells(c1, 2)) ^ 2 + (Cells(c2, 3) - Cells(c1, 3)) ^ 2) = 1 Then If Abs(Cells(c1, 4) - Cells(c2, 4)) = 10 Then Cells(c3, 8) = Cells(c1, 2) Cells(c3, 9) = Cells(c1, 3) Cells(c3, 10) = Cells(c2, 2) Cells(c3, 11) = Cells(c2, 3) c3 = c3 + 1 End If End If Next c1 Next c2 End Sub 

Answer 1

由于您需要评估每个点之间的距离和高度，因此您没有太多select来优化您的algorithm。

1. 你可以像维克拉姆·巴特（Vikram Bhat）那样做，并用三维树对数据进行sorting，但这意味着需要计算时间来构build树，如果只使用树，我不确定是否会花费很多时间。

2. 您可以通过删除Sqr（）来更快地评估距离。
   （（x2-x1）2 +（y2-y1）2）=（距离）2
   既然你正在寻找一个固定的距离，计算（距离）²会更快一次，然后使用每个if的值。
   在你的情况下（距离= 1，距离= 1），你的testing将变成：

    ((Cells(c2, 2) - Cells(c1, 2)) ^ 2 + (Cells(c2, 3) - Cells(c1, 3)) ^ 2) = 1 

   您也可以使用距离近似algorithm：
   http://en.wikibooks.org/wiki/Algorithms/Distance_approximations

3. 如果在距离之前检查高程，另一个优化将交换两个。 因为这个条件计算速度更快，并且可能避免计算距离，所以对于你的algorithm可能是一个不错的加速。

您修改的代码：

 Sub Test1() Columns("H:K").Select Selection.ClearContents c3 = 2 For c2 = 2 To 10 For c1 = c2 + 1 To 10 If ((Cells(c2, 2) - Cells(c1, 2)) ^ 2 + (Cells(c2, 3) - Cells(c1, 3)) ^ 2) = 1 Then If Abs(Cells(c1, 4) - Cells(c2, 4)) = 10 Then Cells(c3, 8) = Cells(c1, 2) Cells(c3, 9) = Cells(c1, 3) Cells(c3, 10) = Cells(c2, 2) Cells(c3, 11) = Cells(c2, 3) c3 = c3 + 1 End If End If Next c1 Next c2 End Sub 

Answer 2

你应该考虑使用三维树帮助得到最近的邻居在O(logn+k) where k are valid neighbours ，如果超过距离，你可以停止find邻居。 这可以在你的蛮力algorithm给出的O(n(logn + k))而不是O(n^2)中起作用。