查找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中的點鄰居

回答

相關問題