특정 알고리즘을 테스트하는 효율적인 알고리즘은 특정 숫자가

Question

에 속합니다. [0..5], [10..20], [7..13], [- 1. .37]) 그리고 내가 좋아하는 데이터 구조로 그 세트를 배열 할 수있다. 가장 효율적인 방법은 무엇인가 은 특정 test_number가 속한 것을 설정 하는가?

저수준 세트를 기반으로 밸런스 이진 트리에 세트를 저장하는 것에 대해 생각해 보았습니다. 각 노드는 세트 수가 가장 적은 모든 세트를 보유하게됩니다. 이렇게하면 집합에 대해 테스트중인 test_number가 집합의 가장 작은 숫자보다 작은 지 여부를 기반으로 집합 수를 효율적으로 제거 할 수 있습니다. 그런 다음 해당 노드와 모든 노드를 해당 노드의 오른쪽으로 잘라냅니다 (test_number보다 큰 범위에서 낮은 수를 가짐). 나는 이것이 집합의 약 25 %를 평균적으로 정리할 것이라고 생각하지만, test_number가 그 집합에 속하는지 여부를 결정하기 위해 이진 트리의 나머지 노드를 모두 선형으로 조사해야 할 것입니다. (어떤 노드의 집합 목록을 집합에서 가장 높은 수로 정렬하여 더 최적화 할 수 있습니다. 특정 목록 내에서 이진 검색을 수행하여 어떤 집합에 test_number가 포함되어 있는지 결정할 수 있습니다. 불행히도 대부분의 경우 다루는 세트 중 겹치는 세트 경계는 없습니다.)

이 모델은 전체 모델의 폴리곤이 효율적으로 테스트 할 수있는 방법을 찾았 기 때문에 그래픽 처리에서이 문제가 해결되었다고 생각합니다. 특정 픽셀,하지만 그 알고리즘의 유형의 용어를 모르겠다.

Answer 1

그래픽에 대한 귀하의 문제의 관련성에 대한 귀하의 직감은 정확합니다. segment tree 작성 및 질의를 고려하십시오. 원하는 카운팅 쿼리에 특히 적합합니다. 그것의 description in Computational Geometry을 또한보십시오.

Answer 2

나는 MediaWiki가 페이지를 색인하는 것과 동일한 방법으로 그들을 구성 할 것이라고 생각합니다 - bucket sort. 나는 그것이 가장 효율적인 알고리즘이라는 것을 알지 못하지만, 빠르며, 구현하기가 쉽다. (심지어 내가 관리해 봤지만, SQL에서 !!).

기본적으로 정렬하는 알고리즘이

For Each SetOfNumbers 
    For Each NumberInSet 
     Put SetOfNumbers into Bin(NumberInSet) 

그런 다음, 당신은 단지 빈 (MyNumber)의 항목 수를 셀 수 쿼리하는 것입니다

당신의 SetOfNumbers가 거의 변경되지 않는 경우이 방식이 잘 작동합니다, 규칙적으로 변경하는 경우에도 Bins를 업데이트하는 것이 일반적으로 어렵지 않습니다. 가장 큰 단점은 매우 빠른 쿼리를 위해 공간과 초기 정렬 시간을 교환한다는 것입니다.

알고리즘에서 범위를 SetsOfNumbers로 확장했습니다. 주어진 범위의 모든 숫자를 열거합니다.

Answer 3

나무 구조를 만들면 상당히 많은 것을 얻을 수 있다고 생각합니다. 초기 비용에 비해 가치가 있는지 충분한 수와 숫자가 있는지 확인하십시오. 이진 트리 대신 삼중 트리 여야합니다. 각 노드에는 왼쪽, 중간 및 오른쪽 노드가 있어야합니다. 왼쪽 노드에는 노드 집합보다 엄격하게 설정된 집합이 포함되고 오른쪽은 엄격히 커지고 가운데는 겹칩니다.

   Set1 
      /| \ 
      / | \ 
      / | \ 
     Set2 Set3 Set4 

주문에 최소값과 최대 값을 비교하기 만하면되므로 세트에 겹침이 있는지 여부를 빠르고 쉽게 알 수 있습니다. 위의 간단한 경우 Set2 [max] < Set1 [min], Set4 [min]> Set1 [Max] 및 Set1 및 Set3 중 일부 오버랩이 있습니다.검색중인 번호가 Set1에 있으면 Set2 또는 Set4에 없기 때문에 검색을 빠르게 할 수 있으므로 검색 할 필요가 없습니다.

단지이 같은 구성표를 사용하면 설정 한 것보다 확인해야 할 숫자가 더 많을 경우 모든 세트를 순진하게 구현하는 데 시간을 절약 할 수 있다는 점을 지적하고자합니다.