목록에서 x보다 큰 첫 번째 값을 얻는 효율적인 방법은 무엇입니까?

Question

두 개의 정렬 된 배열 Haystack 및 Needles이 있습니다. Needles을 반복해야하고 다음 단계를 수행하기 위해 매번 Haystack의 첫 번째 점을 Needle보다 큰 값으로 찾습니다. 예를 들어

:

double [] dHaystack = { 1.2, 2.6, 7.0, 9.3, 19.4 } 
double [] dNeedles = { 1.4, 6.4, 6.5, 7.0, 10.3 } 

// expected indices  0 1 1 2 3  

그래서이 받아야 인덱스 바늘 값 이하인 제 인덱스이다.

명백한 방법은 각 바늘에 대한 건초 더미의 시작부터 반복하거나 마지막으로 발견 된 색인부터 반복하는 것입니다 (바늘도 정렬 됨).

하지만 내 머리의 일부가 "이분법"이라고 외치고 있습니다. 컴파일러가 간단한 블록 읽기 및 반복보다 최적화하기가 더 쉽기 때문에 이분법이 실제로 더 빨라질까요? 그것이 가치가 있기 위해서는 엄청나게 긴 건초 더미가 필요한가요? 그들 중 누구도

UPPER_BOUND 시작과 끝, 끝의 끝을지나 하나되는 대한 반복자를 취 적용하지 않는 경우

Answer 1

당신은 시나리오,

n 개의 *의 LG 전자 (m) < N + m,

n은 바늘과 m의 크기

는 건초 더미의 크기를 고려해야합니다.

따라서 n 및 m 값의 다양한 조합에 따라 달라집니다.

Answer 2

표준은 :: UPPER_BOUND는 당신에게 첫 번째 요소에 대한 반복자 엄격하게 크거나 컬렉션의 "끝"을 줄 것이다 컬렉션. 증가하는 검색 값 목록을 반복하는 경우 물론 전체 컬렉션을 실행할 필요는 없지만 "시작"은 더 오른쪽으로 이동할 수 있습니다.

물론 5 원소의 건초 더미가 있으면 어떤 검색 알고리즘을 사용하든 상관 없지만 매우 커지면 선형 검색을 사용하는 것이 잠재적으로 매우 느릴 수 있습니다. 특히 바늘이 거의 없다면 더욱 그렇습니다.

이 두 가지 크기가 정말로 중요한 것은 상황입니다. 예를 들어 검색 공간 N이 크지 만 검색되는 항목 수 (M)가 작 으면 O (M log N)은 실제로 훨씬 더 작습니다. 이 경우 16K 인 O (M + N)과 비교하여 (예 : M = 20, N = 16K, N = 15 로그 및 M 로그 N은 300). M이 N과 대략 같은 크기라면 O (M log N)은 O (N)보다 훨씬 더 나 빠진다.

따라서 컬렉션의 크기에 따라 사용할 알고리즘을 선택할 수 있습니다.

Answer 3

분명한 방법은 마지막으로 발견 된 색인부터 반복하는 것입니다 (바늘도 정렬 됨).

예.

하지만 내 머리의 일부가 "이분법"이라고 외칩니다. 컴파일러가 간단한 블록 읽기 및 반복보다 최적화하기가 더 쉽기 때문에 이분법이 실제로 더 빨라질까요? 그것이 가치가 있기 위해서는 엄청나게 긴 건초 더미가 필요한가요?

필자는 컴파일러 최적화가 실제로 내재 된 필요한 작업의 양만큼이나 많은 불필요한 작업을 제거하지 않는다고 생각하지 않습니다. 두 세트의 크기가 비슷하다면 명백한 접근법을 고수 할 것입니다. 건초 더미가 설정된 바늘보다 대용량이라면 이분법 또는 보간법이 약간 더 나은 성능을 낼 수 있습니다.이것이 앱에 매우 중요하지 않다면 차이점을 알아 채지 않을 것입니다. 특히 벤치 마크해야한다면, 아마도 std::set과 상한선 또는 하한선을 사용하여 신속하게 작동중인 구현을 얻을 수있을 것입니다. 필요하면 - 자주 사용하지 마십시오.) 라이브러리가 지원하는 경우 시작 위치의 힌트로 마지막 위치를 사용하는 것이 좋습니다.

Answer 4

랜덤 액세스 반복자에 대해 O (log n) 인 std :: upper_bound를 사용하고 가장 짧고 간단한 코드에서 필요한 것을 정확히 제공합니다.

미세한 성능에 대해 걱정하기 전에 현재 코드를 테스트하십시오 (대안을 테스트 할 수도 있음) instead of making assumptions. 특히 각 반복에서 마지막으로 찾은 색인에서 검색을 시작할 수 있습니다 (upper_bound에 대한 첫 번째 매개 변수).

// Available in Boost, C++0x, and many other places. Implementation copied 
// here for the sake of the example. 
template<class T, int N> 
T* end(T (&a)[N]) { 
    return a + N; 
} 

void example() { 
    double haystack[] = {1.2, 2.6, 7.0, 9.3, 19.4}; 
    double needles[] = {1.4, 6.4, 6.5, 7.0, 10.3}; 
    double *begin = haystack; 
    for (double *n = needles; n != end(needles); ++n) { 
    double *found = std::upper_bound(begin, end(haystack), *n); 
    if (found == end(haystack)) break; 
    std::cout << *n << " at index " << (found - haystack) << '\n'; 
    begin = found; 
    } 
}