float 또는 double 필드 알고리즘을 이용한 인덱싱

Question

일부 개체의 필드를 사용하여 엄청난 메모리 내 개체 배열에서 빠른 검색을 수행하는 작업이 있습니다. 몇 가지 기준을 만족하는 객체의 하위 집합을 선택해야합니다.

기준은 부동 소수점 값 또는 이러한 값의 범위 (예 : 2.5..10)로 지정할 수 있습니다.

문제는 검색 할 float 속성이 상당히 균일하게 분포되어 있지 않다는 것입니다. 값 범위가 10-20 (예 :)이고 값이 0-1 인 또 다른 백만 개의 개체가 있고 값이 100-150 인 또 다른 개체가 거의 없을 수 있습니다.

그래서 이러한 개체를 효과적으로 검색하기 위해 색인을 만드는 것이 가능합니까? 코드 샘플은 환영합니다.

Answer 1

나는 값의 분포가 (정확한 중복의 가능한 제외) 인덱스를 구축과 관련이있다을 확인하려면 실패합니다. 데이터가 메모리에 저장되기 때문에 모든 필드를 원래 위치로 추출하여 정렬하고 @MattiLyra가 제안한 바 이진 검색을 사용합니다.

뭔가 빠졌습니까?

Answer 2

메모리 배열이 정렬 된 경우 이진 검색이 내 첫 시도가됩니다. Wikipedia 항목에는 예제 코드도 있습니다.

http://en.wikipedia.org/wiki/Binary_search_algorithm

Answer 3

조회 만 수행하는 경우 단일 이진 및 다중 이진 검색이 적합합니다.

궁극적 인 조회 속도와 더 많은 기능을 원한다면 완벽한 해시 알고리즘을 사용해 볼 수도 있습니다.

조회 만 있으면됩니다. treaps 및 red-black trees를 확인하십시오. 전자는 평균 속도가 빠르며, 후자는 작동 시간 변동이 적은 괜찮은 수행자입니다.

Answer 4

범위 요구 사항에 대해 range tree을 시도해 볼 수 있습니다.