C ++ 벡터 검색 값의 첫 번째/마지막 발생.

StackOverflow https://stackoverflow.com/questions/1649139

문제

나는 변수 중 하나에 대한 주어진 값의 첫 번째 및 마지막 발생을 찾기 위해 "트랙 렛"(내가 구축 한 클래스)의 벡터를 검색하는 최상의 방법을 해결하려고합니다. 예를 들어, 다음 수업이 있습니다 (이 예제에 대해 단순화 됨).

class Tracklet {
    TimePoint *start;
    TimePoint *end;
    int angle;

    public:
        Tracklet(CvPoint*, CvPoint*, int, int);
}

class TimePoint {
    int x, y, t;

    public:
        TimePoint(int, int, int);
        TimePoint(CvPoint*, int);
        // Relevant getters and setters exist here   
};

나는 벡터가있다 "vector<Tracklet> tracklets"그리고 나는 끝 시점에 대해"t "값이 주어진 트랙 클릿을 검색해야한다. 벡터는 종료 시간으로 주문된다 (즉 tracklet.end->t).

검색 알고리즘을 코딩하게되어 기쁩니다. 그러나 어느 경로를 사용할지 확신 할 수 없습니다. 바이너리 검색이 적합 할 것이라고 확신하지 못합니다. 반드시 첫 번째를 찾을 수는 없다는 것을 기억하는 것 같습니다. 나는 이진 검색을 사용하여 올바른 시간의 요소 색인을 찾은 다음 반대하여 마지막을 찾아 마지막을 찾을 수있는 방법을 생각하고있었습니다. 반복하여 바이너리 검색 O (log n)를 폐기하기 때문에 그보다 더 나은 방법이 있다고 확신합니다.

잘만되면 그것은 말이되기를 바랍니다 : 나는 그것을 조금 설명하기 위해 고군분투했다! 건배!

도움이 되었습니까?

해결책

벡터가 정렬되고 값이 포함 된 경우 std::lower_bound 주어진 값을 가진 첫 번째 요소에 반복자를 제공하고 std::upper_bound 값이 포함 된 마지막 요소를지나 한 요소에 반복자를 제공합니다. 반환 된 요소와 값을 비교하여 벡터에 존재하는지 확인하십시오. 이 두 기능 모두 이진 검색을 사용하므로 시간은 O (logn)입니다.

비교합니다 tracklet.end->t, 사용:

bool compareTracklets(const Tracklet &tr1, const Tracklet &tr2) {
    return (tr1.end->t < tr2.end->t);
}

그리고 네 번째 인수로서 비교 신도를 통과하십시오 lower_bound 또는 upper_bound

다른 팁

그냥 사용해요 find 그리고 find_end, 그리고 테스트가 너무 느린 것으로 보인 경우에만 더 복잡한 일을하십시오.

조회 성능에 대해 정말로 우려하고 있다면 다른 데이터 구조를 고려할 수 있습니다. map 키로 타임 스탬프를 사용하고 a vector 또는 list 값으로 요소의.

이진 검색은 벡터가 정렬되어있는 한 여기에서 최선의 선택처럼 보입니다. 이진 트리 구조에서 조회를 수행하는 것은 본질적으로 동일하고 성능 측면입니다.

더러워지게 참조되었습니다 달콤한 최적화 비교. 그러나 나는 실제로 사용하지 않을 것이다 std::vector 이것을 위해.

일반적으로 STL 컨테이너를 사용하기로 결정할 때 실제로 성능 측면을 고려하지는 않지만 사용하려는 작동 유형과 관련하여 인터페이스를 고려합니다.

std::set<T>::find
std::set<T>::lower_bound
std::set<T>::upper_bound
std::set<T>::equal_range

실제로 키/값 설정 외에 순서 시퀀스를 원한다면 std::set 다른 것보다 사용하기가 더 쉽습니다.

  • '나쁜'위치에 삽입하는 것에 대해 걱정할 필요가 없습니다.
  • 요소를 추가 / 제거 할 때 반복자 무효화 문제가 없습니다.
  • 검색 방법이 내장되어 있습니다

물론, 당신은 또한 당신의 비교 술어가 실제로 빛나기를 원합니다 (컴파일러가 Operator () 구현을 상인하기를 희망합니다).

그러나 실제로, 당신이 확신이 없다면, std::vector 및 수동 삽입 / 검색 (사용 사용 <algorithm> 헤더) 및 다른 빌드를 사용해보십시오 std::set.

구현 크기 (코드 줄 수)를 비교하고 버그 수를 비교하고 속도를 비교 한 다음 결정하십시오.

가장 자주, 당신이 목표로하는 '최적화'는 실제로 비관적, 그리고 그 희귀 한 시대에는 그렇지 않습니다. 너무 복잡하여 그만한 가치가 없습니다.

최적화:

  • 하지 않다
  • 전문가 전용 :하지 마세요, 우리는 그것을 의미합니다

벡터는 시간 측면에서 주문됩니다

시작 시간 또는 종료 시간?

순진한 o (n) 검색에 어떤 문제가 있습니까? 당신은 단지 검색하고 정렬하지 않는다는 것을 기억하십시오. 정렬 된 컨테이너도 사용할 수 있습니다 (기본 설계에 반대하지 않는 경우).

라이센스 : CC-BY-SA ~와 함께 속성
제휴하지 않습니다 StackOverflow
scroll top