좌표 점 (x, y)에 10 000 점이 있다고 말합니다. 이제 새로운 점이 test query say (p, q)로 주어질 때. 나는 좌표 points.if에서 x 축 좌표를 확인해야만한다. 온라인 검색에서 PY 나는 Rmq- 범위 최소/최대 쿼리 데이터 구조를 알 수 있었지만 어떻게해야할지 모르겠다. .. 어떤 사람이 나를 도와 줄 수있는 방법 .. 내가 할 수있는 일 ... C++의 모든 참조 또는 코드 도움말은 도움이 될 것입니다. 감사합니다.범위 최소값/최대 값 조회
목표가 데이터 세트에 존재하는지 확인하는 것이 목표라면 는 데이터를 보관하는 데 사용할 수있는 많은 유용한 데이터 구조로, 각 데이터는 매우 효율적인 조회를 지원합니다.
처음에 포인트가 있는지 여부를 알아야 할 경우 표준 해시 테이블 또는 균형 이진 검색 트리에 모든 포인트를 저장할 수 있습니다. 이것은 각각 O (1) 또는 O (log n) 검색 시간을 제공합니다. 게다가 이러한 구조는 대부분의 프로그래밍 언어에서 사용 가능합니다.
한편, 일부 테스트 포인트에서 가장 가까운 데이터 세트에서 k 포인트를 검색하거나 일부 경계에서 모든 포인트를 찾으려는 경우와 같이 데이터에 대한 더 복잡한 작업을 수행하려는 경우 영역 인 경우 kd-tree 또는 quadtree을 사용하는 것이 좋습니다. 표준 바이너리 검색의 이러한 변형은 빠른 조회 (O (log n) 시간)를 제공합니다. kd-tree는 또한 매우 빠르게 k-nearest-neighbor searches을 지원하고 바운딩 볼륨을 검색합니다. 또한, 표준 바이너리 검색 트리를 구현 한 경험이 있다면 kd-tree를 구현하는 것이 놀랍도록 쉽습니다.
희망이 도움이됩니다.
당신이 무엇을 요구하고 있는지 명확히 할 수 있습니까? 테스트 포인트로 무엇을하고 싶습니까? 가장 가까운 지점을 찾으려고합니까? 포인트가 데이터 세트에 있는지 확인하려고합니까? – templatetypedef
포인트가 데이터 세트 –
에서 더 빠져 나오면 찾으려는 것입니다. 제가 접미어 배열 범위를 입력 텍스트로 가져 오려고하면 접미어 배열 범위를 얻으 려합니다. 그 다음 접미사를 모두 묶는 범위를 제공합니다. 이제는 입력 텍스트의 접미사 배열에 대한 접미어 범위의 텍스트를 얻을 수있었습니다. 이제 입력 텍스트의 접미사 범위가 테스트 문자열의 접두어인지 확인하려고합니다. 이것을 테스트하기 위해 rmq 나 좋은 데이터 구조를 사용하여 시간 효율성을 확인하십시오. –