가장 빠른 검색 알고리즘은 무엇입니까

Question

정수가 주어지면 작은 세트에서 일치하는 항목을 찾아야합니다. 정수는 거의 항상 이 아니며이 세트에 포함됩니다. 대부분의 검색 알고리즘에서 최악의 경우입니다 (가장 오래 걸림). 그러나이 응용 프로그램의 경우 검색 시간은 검색 실패의 속도에 의해 결정됩니다. 그래서 가장 좋은 경우 알고리즘은 '찾을 수 없습니다'.

그런 것이 있습니까?

정수는 배열 색인 인 - 0..10k (15 비트)와는 거리가 멀습니다. 이 집합에는 0..7 정수가 포함되며 이는 단순 선형 검색에 충분합니다. 그러나 그것은 거의 모든 경우에서 최악의 경우입니다.

제가 생각할 수있는 유일한 것은 블룸 필터입니다. 그것은 다음과 같이 동작 할 것입니다. Define F (int) = Set Bit (i AND 1Fh) (1 비트가 설정된 32 비트 정수). 각각의 세트로 F (각 요소)의 합계 값 (n 개의 요소에 대해 설정된 최대 n 비트의 32 비트 정수)을 OR로 저장합니다. 그러면 검색은 IF (F (i) AND F (set))> 0이되고 선형 검색을 수행합니다.

따라서 적어도 하나의 세트 요소가 테스트 정수 i와 동일한 하위 5 비트를 갖지 않는 한 검색이 수행되지 않습니다. 다음으로 낮은 5 비트를 기반으로 두 번째 테스트를 추가 할 수 있습니다.

더 나은 아이디어 누구?

Answer 1

내가 성공할 수있는 가장 빠른 알고리즘은 즉시 성공하거나 실패 할 수 있습니다. 부울의 최대 배열은 0..MaxInt이며, 배열 [Set Member]에서 True를 제외한 모든 False입니다. 검색은 단순한 배열 검색 일 것입니다 :

Found = Array[Test] 

그러나 메모리 풋 프린트는 어리석은 것입니다. 일반적인 최적화는 Hash Array입니다.

테스트에서는 Set 멤버의 비트를 사용하여 Perfect Hash를 구현했습니다. 함수 PHash (int)는 정수 0..15를 반환합니다.이 인덱스는이있는 경우 일치가 발견되는 배열 인덱스 입니다. 검색은 다음과 같습니다

IF Array[PHash(Test)] = Test 
    THEN Found at Index PHash(Test) 
    ELSE Not Found 

그것은 아마도 프로파일 링 프로그램이 선형 검색보다 느릴 수 아무도 놀라게하지 않습니다. (한숨)

물론 단일 해시는 15 비트 정수를 다른 4 비트 정수로 줄일 수 없습니다. 나는 많은 다른 해쉬 함수를 사용한다. Set을 생성하기 위해 어떤 함수가 해당 Set에 대해 고유 한 4 비트 해시를 생성 한 다음 Set에 해시 함수 포인터와 16 요소 배열을 저장합니다. 각 Array 요소는 X 또는 하나의 Set Member입니다. 여기서 X는 설정된 범위에 없습니다. (완벽한 해시를 찾지 못하면 예외가 발생하지만 아직 발생하지는 않았습니다.)이 오버 헤드는 프로그램 시작시 한 번만 수행되므로 프로파일 링에서 중요하지 않습니다.

Set에서 Test 정수를 찾으려면 Set.HashFunction (Test)를 호출 한 다음 Test를 해당 Set.Array 요소와 비교하십시오. 최종 비교는 선형 검색의 각 단계와 동일합니다. 더 빠르려면 해시 함수가 선형 검색의 나머지 비교보다 빠릅니다. 따라서이 은이 더 빠른 알고리즘 일 수 있지만 크기가 충분히 큰 경우에만 해당됩니다.

나는 그 세트 크기를 찾기 위해 실험하지 않았습니다. 어쨌든 그것은 각 해시 함수의 속도에 달려 있습니다.