如何优化这个循环？

Question

我正在编写一个Java程序，它使用Voronoi创建一个地图。我使用的是一个生成Voronoi的Java库，它非常快(http://sourceforge.net/projects/simplevoronoi/)。

我面临的问题是，然后，我必须扫描每个Voronoi边缘，以知道哪一点在左边和右边的边缘，以创建多边形，其中包含每个点。这个类包含了所有Voronoi边缘：

public class GraphEdge
{
    public double x1, y1, x2, y2;

    public int site1;
    public int site2;
}

坐标x1, y1, x2, y2是边的起始坐标和结束坐标，site1和site2是边的左边和右边点的索引。因此，要创建包含每一点的多边形，我执行以下操作：

for(int n = 0; n < xValues.length; ++n){
        polygonsList.add(new GPolygon());
        for(GraphEdge mGraphEdge : edgesList){
            if( (xValues[mGraphEdge.site1] == xValues[n] || xValues[mGraphEdge.site2] == xValues[n])
                && (yValues[mGraphEdge.site1] == yValues[n] || yValues[mGraphEdge.site2] == yValues[n]) ){
                polygonsList.get(n).addPoint((int)mGraphEdge.x1, (int)mGraphEdge.y1);
                polygonsList.get(n).addPoint((int)mGraphEdge.x2, (int)mGraphEdge.y2);
            }
        }
    }

其中，xValues和yValues是生成Voronoi图的点坐标，而GPolygon是我创建的从java.awt.Polygon扩展的多边形类。这是我测量的时间：

• Voronoi时间： 283 mS (生成Voronoi图的时间)
• 多边形搜索时间： 34589 mS (完成生成多边形的for循环的时间)
• 多边形填充时间： 390 mS (填充多边形并保存到图像的时间，这是可选的)
• 点数量： 26527 (产生Voronoi的点数)
• 地图生成完成
• 多边形数量： 26527 (多边形数，每点一个)

正如您所看到的，与其他时间相比，时间是非常重要的，我如何能够加快for循环？我还有别的选择吗？先谢谢你。

Answer 1

呃，如果性能真的很差的话，现在是考虑算法选择的好时候了。您已经注意到，在输入集中的每个站点周围都有一个多边形--或者不同地放置，形成多边形的边缘有一个相同的位置。

因此，下面这样简单的内容应该可以很好地解决这个问题：

Map<Integer, List<GraphEdge>> edgesByPolygon = new HashMap<>();
for (GraphEdge edge : edgesList) {
    List<GraphEdge> list = edgesByPolygon.get(edge.site1);
    if (list == null) {
        list = new ArrayList<>();
        edgesByPolygon.put(edge.site1, list);
    }
    list.add(edge);

    list = edgesByPolygon.get(edge.site2);
    if (list == null) {
        list = new ArrayList<>();
        edgesByPolygon.put(edge.site2, list);
    }
    list.add(edge);
}

for (List<GraphEdge> list : edgesByPolygon.valueSet()) {
    // order the edges by adjacency and construct the polygon instance
    // (a naive algorithm will do, as the average number of edges is small)
}

这是一个接近O(n)算法(而不是O(n^2))，我估计它应该快1000倍。

Answer 2

实际上，在for循环期间将新的GPolygon存储到变量中，而不是直接将其添加到列表中：

    for(int n = 0; n < xValues.length; ++n){
        GPolygon polygon = new GPolygon();
        polygonsList.add(polygon);
        for(GraphEdge mGraphEdge : edgesList){
            if( (xValues[mGraphEdge.site1] == xValues[n] || xValues[mGraphEdge.site2] == xValues[n])
                && (yValues[mGraphEdge.site1] == yValues[n] || yValues[mGraphEdge.site2] == yValues[n]) ){
                polygon.addPoint((int)mGraphEdge.x1, (int)mGraphEdge.y1);
                polygon.addPoint((int)mGraphEdge.x2, (int)mGraphEdge.y2);
            }
        }
    }

这样你就不用打电话给get了。

Answer 3

• 确保polygonsList是ArrayList，而不是LinkedList。

台词：

polygonsList.get(n).addPoint((int)mGraphEdge.x1, (int)mGraphEdge.y1);
polygonsList.get(n).addPoint

可以通过只调用一次polygonsList.get(n)来简化。

此外，如果你有很高的边缘，你可以提高100 - 1000倍的速度，

将您的边缘存储在基于桶的四叉树中，要么是行四叉树，要么是边框四叉树，我更喜欢)。然后，对于每个搜索点，四叉树会给出附近的16条边(平均桶大小= 16)。您不必对所有10.0000进行迭代，只迭代16次。