높이 맵용 최적의 데이터 구조

높이 맵 (부동 소수점 값의 2D 배열)이 있는데이 점을 찾으면지도에서 가장 높은 점을 찾고 그 값과 값을 변경하려고합니다 가까운 모든 지점 중. 가장 높은 지점을 효율적으로 검색하는 데 사용할 최적의 데이터 구조는 무엇입니까?높이 맵용 최적의 데이터 구조

요구 사항 :

이
변경합니다 점의 임의의 집합의 값 세트가 가장 높은 현재 위치, 인근 지점의 부하를 항상 포함됩니다 효율적으로

내 생각은 우선 순위 대기열이므로 O (1)에서 가장 높은 지점을 찾을 수 있으며 O (n log n)에서 값의로드를 변경하고 heapify 할 수 있습니다.

Nb. 저는 이것을 언어에 의존하지 않는 언어와 Lua로 표시했습니다. 왜냐하면 언어 적으로 불가지론적인 질문 이었기 때문에 루아에서 최종 해결책을 구현할 것입니다.

출처

2010-02-24 Martin

메모리가 큰 문제가 아니라면 각 값이 가장 가까운 이웃에 대한 참조와 데이터 값을 갖도록 우선 순위 큐의 각 값을 테이블로 저장합니다. 이런 식으로 : {data = number, neighbors = {...}}.

출처

2010-02-24 20:51:26 ponzao

흠, 그 일을하는 흥미로운 방법처럼 들립니다. 루아에서 우선 순위 큐를 작성하는 것은 재미 있어야합니다 : D – Martin

그것은;) 우선 목록 기반 버전으로 시작한 다음 바이너리 힙 기반으로 이동하는 것이 좋습니다. 그 이유는 목록 기반의 구현이 훨씬 빨라서 올바른 경로인지를 알기 때문입니다. 개체의 비교 메타 메서드를 재정 의하여 우선 순위 큐에서 비교 연산자와 비교할 수 있도록 우선 순위 큐를 쉽게 일반화 할 수 있도록하는 것이 좋습니다. – ponzao

나는 C#으로 구현 된 최소 - 최대 힙을 이미 가지고있어서, 그걸 포팅 했으므로, 그것은 매우 놀랍습니다. D – Martin

우선 순위 큐를 만드는 동안 배열을 검색하고 발견 된 가장 높은 값의 인덱스를 반환하기 만하면됩니다. 그러면 O (1)에서 '근처'배열의 요소에 액세스 할 수 있습니다.

아니면 뭔가 빠졌습니까?

출처

2010-02-24 15:44:49

배열 검색에 O (1)을 어떻게 사용합니까? :/ – Martin

나는 어레이 스캐닝이 O (1)라고 언급하지 않았다. 그러나 배열 요소의 인덱스가 주어지면 액세스 시간은 O (1)입니다. –

사실,하지만 인덱스를 찾는 것은 전체 배열에 대한 스캔을 필요로하는데, 이는 내가 피하려고하는 것입니다. – Martin

높이 맵용 최적의 데이터 구조

답변

관련 문제