직사각형 기반 점 검색 최적화

Question

직사각형 (x, y, 너비, 높이) 또는 점 목록 (x, y)으로 변환 할 수있는 실과 구절 집합이 있습니다. Room 및 Passage은 모두 Pointable 인터페이스를 확장합니다.
나는 주어진 Point가 속한 Pointable를 식별해야 다음 getPoints() 메소드는

public Set<Point> getPoints() { 
    Set<Point> array = new HashSet<Point>(); 
    for (int i = 0; i < width; i++) { 
     for (int j = 0; j < height; j++) { 
      array.add(new Point(x + i, y + j)); 
     } 
    } 
    return array; 
} 

문제점으로 객실 클래스에 구현됩니다. 방이 교차하지 않습니다. 원래는 HashMap<Point,Pointable>을 사용하여 Point을 Pointable에 연결 시켰습니다. O (n) 시간에 신속하게 답변에 액세스 할 수있었습니다. 그러나 이제 수준 생성시 여러 번 HashMap을 다시 계산해야합니다.

이 시점에서 (생성 및 액세스를 고려하여) HashMap을 사용하는 것이 더 효율적입니까? 아니면 2 차원 간격 트리 집합 같은 다른 방법을 사용해야합니까? 이때

Answer 1

이러한 2-D 구간 나무의 세트로서, 이는 (생성 및 액세스 고려)를 해시 MAP 사용하는 것이보다 효율적 여전히 또는 다른 방법이 사용되어야 하는가?

측정을 한 사람 외에는 아무도 말할 수 없습니다. 데이터를 업데이트해야하는 빈도, 변경 빈도 및 쿼리 빈도에 따라 다릅니다.

또한 크기는 Room입니다. 몇 가지 점을 제외하면 일반적인 시나리오에서는 HashMap이 우승하며 그 중 수 천 명이 넘기 때문에 점수를 업데이트하는 오버 헤드가 지배적입니다.

---

모두 Point에 배열을 사용할 수 없습니까? 그렇다면 확실한 방법으로 더 빨리 HashMap이 될 것이며, 특히 업데이트가 필요하지 않은 경우에는 더욱 그렇습니다.

---

이것은 유용 할 수도 있고 그렇지 않을 수도 있습니다.

사실뿐만 아니라, 각 Room 일부 Point S를 가지며, 또한 각 Point은 할 수있는 하나 Room (N : 1). 구현 방법은 다른 질문입니다.

이렇게하면 표준적인 문제가 있습니다. 양방향으로 연결하는 경우 두 링크를 동기화 상태로 유지해야합니다. 가장 간단한 해결책은 가능한 한 개인으로 세터 ("가산기"/ "제거제")를 확인하는 것입니다 만

void link(Room room, Point point) { 
    Room oldRoom = point.getRoom(); 
    if (oldRoom!=null) oldRoom.removePoint(point); 
    room.addPoint(point); 
    point.setRoom(room); 
} 

Point에서 Room에 대한 귀하의 연결이 외부에 있지만, 거의 아무것도 변경되지 않습니다 (방법에서 그들에게 전화 Point을 작고 더 깨끗하게 유지하고 각 액세스에 HashMap의 작은 오버 헤드를 추가하는 것을 제외하고는).

일반적으로 대개 업데이트보다 훨씬 많은 쿼리가 있기 때문에 가장 빠릅니다. 문제는 업데이트 비용이 Room 크기로 조정됩니다. 우리에게 어떤 수치를 말하지 않고도 예상 할 수 없습니다.너무 많은 포인트를 너무 많이 변화하지 크기의 객실

---

, 당신은 포인트가 일부 n의 여러 좌표 반올림 그리드 교차 모든 객실의 집합을 잡고 배열을 유지할 수 있습니다. 이전과 같이 진행할 수 있지만 업데이트 오버 헤드는 룸 영역 (*) 및 검색 오버 헤드가 높을수록 낮아질 수 있습니다. 세트에서 실제 일치하는 룸 (있는 경우)을 선택해야합니다.

(*) 그리드에 정렬되지 않은 객실의 경우, 교차하는 사각형의 수가 분명히 많습니다.