查找ArrayList中的点邻居

我最近开始学习Java，虽然做了一个“Conway's Game of Life”风格的程序将是一件好事。一切工作正常，但我有这个部分的一些严重的性能问题：迭代ArrayListcoordList充满点和检查每个元素有多少邻居有当查找ArrayList中的点邻居

static List<Point> coordList = new ArrayList<Point>(); 

public int neighbors(int x, int y){ 

    int n = 0; 

    Point[] tempArray = { new Point(x-1, y-1), new Point(x, y-1), new Point(x+1, y-1), 
          new Point(x-1, y ),     new Point(x+1, y ), 
          new Point(x-1, y+1), new Point(x, y+1), new Point(x+1, y+1)}; 
    for (Point p : tempArray) { 
     if (coordList.contains(p)) 
      n++; 
     } 

    return n; 
}

的方法被使用。当列表大小达到大约10000时积分每个周期大约需要1秒，对于20000个积分需要7秒。

我的问题是，什么会是一个更有效的方法来做到这一点？我知道还有其他几种这样的源代码可用的程序，但我不会尽我所能地做我自己的事情，因为项目的关键是我学习Java。另外，由于局限性，我不想使用常规数组。

来源

2012-11-22 fredrol

如果你的观点是独特的，你可以将它们存储在a HashSet而不是ArrayList。然后，contains方法将在您当前的设置中成为O（1）操作与O（n）操作。这应该会显着加快该部分的速度。

除了声明之外，您的代码应该保持大部分不变，因为它们都实现了Collection接口，除非您调用列表特定的方法，例如get(i)。

来源

2012-11-22 11:13:59 assylias

我会试试看，谢谢！关于HashSet的一个问题;它中的元素的索引是否保持不变？我计划在未来通过另外一个索引链接列表来扩展这个程序。但也许这不是做这种事的正确方法？ – fredrol

这些点必须是唯一的，否则代码'coordList.contains（p）'不会给出正确数量的邻居。 – Peter

哈希集在内部使用索引，但索引在哈希集调整大小且索引未由api公开时会更改。 – Peter

在性能方面，我认为你最好的选择是拥有一个代表网格的普通数字（有效的布尔）数组。由于这是一个学习练习，我将从一个简单的单元素单元数组开始，然后可能会将八个相邻单元打包到单个字节中。

“限制”的含义并不完全清楚。

下面有一些有趣的指针：在二次方式O(n^2)Optimizing Conway's 'Game of Life'

来源

2012-11-22 11:16:36 NPE

感谢您的回复！有限制的意思是数组的可伸缩性。如果我没有弄错，阵列的大小是固定的，我希望细胞的数量和坐标能够没有限制地增长。 – fredrol

您当前密码秤。你只给了部分程序。如果你看看你的整个程序，会有一个循环调用neighbors()，你会看到neighbors()被调用n次。此外，该操作包含（）在n中是线性的，因此时间与其产品n*n成比例。

二次缩放是一个常见问题，但通常可以通过使用索引数据结构（如HashSet）将其缩减为线性。

来源

2012-11-22 11:24:35

谢谢您的回复！正如所建议的，我改变了一个HashSet，事情效果很好。 – fredrol

查找ArrayList中的点邻居

回答

相关问题