ArrayList의 포인트에 이웃을 찾는

Question

저는 최근에 Java 학습을 시작했습니다. 그리고 "Conway's Game of Life"스타일 프로그램을 시작하는 것이 좋은 방법입니다. 모든 것이 잘 작동하지만 난이 부분에 심각한 성능 문제에 봉착 : 포인트 가득 ArrayListcoordList을 반복하고 그들이 얼마나 많은 이웃들 모든 요소를 ​​검사 할 때

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 초가 걸립니다.

내 질문은 무엇이 더 효과적인 방법일까요? 내가 사용할 수있는 소스 코드와 함께 이런 종류의 다른 프로그램이 몇 가지있다는 것을 알고 있지만, 프로젝트의 시점부터 자바를 배우는 것이기 때문에 나는 할 수있는 한 많이하지 않는다. 또한 제한 때문에 일반 배열을 사용하고 싶지 않습니다.

Answer 1

점수가 유일한 경우 ArrayList 대신 a HashSet에 저장할 수 있습니다. contains 메서드는 현재 설정에서 O (1) 작업 대 O (n) 작업이됩니다. 그러면 해당 섹션의 속도가 상당히 빨라집니다.

예를 들어 get(i)과 같은 List 관련 메서드를 호출하지 않는 한 선언과 별도로 코드는 대부분 Collection 인터페이스를 구현하므로 변경되지 않습니다.

Answer 2

성능 측면에서 가장 좋은 방법은 그리드를 나타내는 일반 숫자 (효과적으로 부울) 배열을 갖는 것입니다. 이것은 학습 연습이므로 간단한 셀당 요소 배열로 시작한 다음 인접한 8 개의 셀을 단일 바이트로 패킹하는 과정으로 진행할 것입니다.

"제한 사항"이 의미하는 것이 완전히 명확하지 않습니다. 이차 방식 O(n^2)에서 Optimizing Conway's 'Game of Life'

Answer 3

현재 코드 스케일 :

다음은 몇 가지 흥미로운 포인터를 가지고있다. 당신은 프로그램의 일부만을주었습니다. 전체 프로그램을 보면 neighbors()을 호출하는 루프가 있고 neighbors()은 n 번 호출됩니다. 또한() 안의 연산은 n에서 선형이므로 시간은 그들의 곱인 n*n에 비례합니다.

2 차 스케일링은 일반적인 문제이지만 HashSet과 같은 인덱싱 된 데이터 구조를 사용하여 종종 선형으로 줄일 수 있습니다.