나는 간단한 질문이있다. 나는 id와 x, y 좌표를 가진 객체를 필요로하는 프로젝트를 진행하고있다. 이것은 모두 객체에 저장되며 2D 배열에 배치됩니다. 그러나 많은 수의 객체가 만들어지고 저장 될 가능성이 있으므로 배열의 크기가 클 수 있습니다. 데이터를 저장할 수있는 크기와 속도면에서 더 효율적인 것이 있습니까? 나는 이것이 나의 최선의 선택일지도 모른다지도를 사용하는 것에 대해 읽었다.다차원 배열을위한 대체 데이터 구조
대답은 응용 프로그램의 기본 액세스 패턴이 무엇인지에 따라 달라집니다.
기본 액세스 패턴이 특정 X에서 객체를 찾고 있다면, y는 그때는 아마 가장 다음 중 하나에 의해 제공됩니다, 좌표 (현재 가지고있는)
Thing[][]하는 Map<Point, Thing>Map<Integer, Map<Integer, Thing>>. 은 (내가 두 번째 옵션은 임시 Point 객체의 생성에 당신이 데이터 구조에 조회를 할 때마다 결과에 책임이 있기 때문에이 다루는 다른 방법이 있습니다., 3 옵션을 제안하지만, 응용 프로그램을 더 복잡하게 만듭니다.)
2D 배열이 드문 드문 경우 맵 방식을 사용하면 시간을 절약하면서 공간을 절약 할 수 있습니다. 배열이 조밀하게 채워져있는 경우, Map 접근법은 을 사용하여 2D 배열보다 공간을 더 많이 사용하게됩니다.
기본 액세스 패턴이 주어진 x, y 좌표 (또는 지역) 근처의 객체를 찾는 것이라면 쿼드 트리 데이터 구조와 같은 것이 필요할 것입니다.
마지막으로주의해야 할 점은 하나 이상의 매개 변수 유형이 기본 유형 인 경우 특히 표준 콜렉션 유형을 사용하는 데 불가피한 오버 헤드가 있다는 것입니다.
성능 요구 사항이 특히 "어렵다"면 손으로 맞춤 데이터 구조를 설계하고 구현하면 공간과 시간이 절약됩니다. 하지만 작성, 테스트 및 유지 관리 할 수있는 코드가 훨씬 많으며 사용자 지정 데이터 구조가 표준 컬렉션 API와 호환되지 않는다는 단점이 있습니다.
Map<Double, java.awt.Point>
java.awt.Point가 작동하거나 사용자가 x, y 좌표를 보유 할 데이터 유형을 만들 수 있습니다.
이렇게하면 빠른 조회가 가능하지만 직선 배열보다 많은 메모리를 사용합니다 (그다지 많지는 않지만 그다지 나쁜 것은 아닙니다).
또 다른 대안은 3 가지 (ID, x, y)를 결합하여 배열에 저장 한 다음 Arrays.binarySearch을 사용하여 얻을 수있는 것입니다. 배열을 정렬해야합니다.
편집 :
당신이 이중 당신이 할 것으로 Y는 X에서 매핑 할 경우
Map<java.awt.Point, Double>
기본 액세스 패턴은 x, y 좌표입니다. 속도와 공간의 균형이 필요합니다. 현재 나는 많은 양의 데이터를 가지고 테스트를했는데 이것은 좋은 가능성이 있습니다. 2D 배열을 사용하여 Java 힙 크기를 늘려야하고 읽는 데 약 6 분이 걸렸으므로 맵과 쿼드 트리를 모두 살펴볼 것입니다. – intelman
@Stephen, 나는 대부분 동의합니다. 하지만 인덱스가 128보다 크면 정수를 사용하면 새로운 정수가 생성됩니다. 그런 다음 1 개의 새 Point 객체 대신 2 개의 새 객체를 만듭니다. 어쨌든, Java GC는이 경우 Pint 키처럼 매우 짧은 수명의 오브젝트에 대한 최적화를 많이합니다. 그래서 아마도 옵션 2 또는 옵션 3 사이의 선택은 대부분 선호됩니다. – z5h