如何优化这个循环？

我正在使用Voronoi创建地图的Java程序。我正在使用生成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是一个多边形类我创建了从0延伸。这些是我测量次数：

沃罗诺伊时间： 283 MS（时间来生成Voronoi图）
多边形搜索时间： 34589 MS（时间来完成用于环路产生的多边形）
多边形填充时间： 390 MS（时间来填充的多边形，并保存到图像，这是可选的）
点数数量： 26527（点数从中维诺产生）
地图生成成品
多边形数量： 26527（多边形的数量，每点）

正如你所看到的比别人时间真的显著，我如何加快for循环？我还有什么其他的选择？非常感谢你提前。

来源

2013-06-12 Andres

为了优化工作代码，您可以考虑http://codereview.stackexchange.com –

谢谢！我可以同时发布两者吗？ – Andres

如果事先知道其最终尺寸，请尝试将列表大小设置为适当的容量。 – assylias

呃，如果性能真的很差，现在是考虑你选择算法的好时机。您已经注意到输入集中每个站点周围都有一个多边形 - 或者换句话说，形成多边形的边具有相同的站点。

因此，一些如下面要解决它很好地简单：

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倍。

来源

2013-06-12 19:17:12 meriton

它大大缩短了时间！从30多岁到200多岁！只是一个问题，我的地图正在被绘制不同，现在看起来像多边形是不一样的。它是代码http://pastebin.com/Yhj8ZcCv。每个列表包含多边形的边缘？ – Andres

这是要走的路。这里不需要特殊的数据结构和微观优化。 – maybeWeCouldStealAVan

解决了！我的错！非常感谢您的帮助令人惊叹的想法:) – Andres

其实，在存储新GPolygon到一个变量for循环，而不是直接将它添加到列表中：

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); 
      } 
     } 
    }

这样你就不必打电话得到的。

来源

2013-06-12 18:40:22

这是我第一个想法，也是我能想到的唯一优化。不幸的是，我认为@默顿是对的;如果性能很差，你将不得不重新考虑整个算法。 –

没错。我想你应该总是看重复的方法调用获取相同的项目。 –

确保polygonsList是ArrayList，而不是LinkedList。

线条：

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

可以通过调用polygonsList.get（N）仅一次simpliefied。

而且可以通过100倍加快 - 1000，如果你有一个非常高的边数，

Store中的边缘基于quadtree水桶，无论是线四叉树或边框四叉树，这是我喜欢）。然后，对于每个搜索点，四叉树将为您提供例如附近的16个边（假定桶大小= 16）。你不必迭代所有10.0000，只能用于16.

来源

2013-06-12 18:41:10 AlexWien

边的数量可以大不相同，但我可以根据边的数量实现不同的算法，通常是10.000边或更多。 – Andres

更新为使用四叉树作为边缘的索引 – AlexWien

真的很好我会调查我不太了解它，例如，使用这个http://goo.gl/9Rdo6，经度和纬度将是我（x， y）坐标？我将不得不将数据从我的ArrayList传递到QuadTree。 – Andres

如何优化这个循环？

回答

相关问题