Pesquisando um C ++ Vector pela primeira última ocorrência / de um valor

Question

Eu estou tentando descobrir o melhor método para procurar um vetor do tipo "Tracklet" (uma classe eu me construído) para encontrar a primeira e última ocorrência de um determinado valor para uma de suas variáveis. Por exemplo, eu tenho as seguintes classes (simplificado para este exemplo):

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   
};

Eu tenho um vector "vector<Tracklet> tracklets" e eu preciso procurar qualquer tracklets com um dado valor de "t" para o ponto no tempo final. O vector é ordenada, em termos de tempo de fim (isto é tracklet.end->t).

Estou feliz de código se um algoritmo de busca, mas tenho certeza de qual caminho a tomar com ele. Eu não tenho certeza de busca binária seria adequado, como eu me lembro de ele não vai necessariamente encontrar o primeiro. Eu estava pensando em um método onde eu usar a pesquisa binária para encontrar um índice de um elemento com o tempo correto, então iterate volta para encontrar a primeira e para a frente para encontrar o último. Eu tenho certeza que há uma maneira melhor do que isso, uma vez que desperdiça binário pesquisas O (log n) por iteração.

Esperemos que isso faz sentido: eu lutava para explicar um pouco! Felicidades!

Answer 1

Se o vector for ordenada e contém o valor, std::lower_bound lhe dará um iterador para o primeiro elemento com um determinado valor e std::upper_bound lhe dará um iterador para um elemento passado o último contendo o valor. Comparar o valor com o elemento retornado para ver se ele existia no vector. Ambas as funções usam busca binária, assim que o tempo é O (log N).

Para comparar on tracklet.end->t, use:

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

e passar compareTracklets como o quarto argumento para lower_bound ou upper_bound

Answer 2

Eu tinha acabado de usar find e find_end , e, em seguida, fazer algo mais complicado somente se os testes mostraram que ele seja muito lento.

Se você está realmente preocupado com o desempenho de pesquisa, você pode considerar uma estrutura de dados diferente, como um map com timestamp como a chave e uma vector ou list de elementos como o valor.

Answer 3

A busca binária parece ser a sua melhor opção aqui, contanto que seus restos vetor ordenado. É essencialmente idêntica, em termos de performance, a realização de uma pesquisa em uma estrutura de árvore binária.

Answer 4

dirkgently referido a uma comparativa otimização doce. Mas eu na verdade não usar um std::vector para isso.

Normalmente, quando decidir usar um recipiente STL, eu realmente não considerar o aspecto de performance, mas eu considero sua interface quanto ao tipo de operação gostaria de uso.

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

Realmente, se você quiser uma seqüência ordenada, fora de uma configuração de chave / valor, std::set é apenas mais fácil de usar do que qualquer outro.

• Você não tem que se preocupar com a inserção em uma posição 'ruim'
• Você não tem problemas de iterators invalidação ao adicionar / remover um elemento
• Você tem built-in métodos para pesquisar

É claro, você também quer que seu Comparação Predicado para realmente brilhar (espera os inlines compilador o operador () implementação), em cada caso.

Mas realmente, se você não está convencido, tente uma compilação com um std::vector e inserção manual / busca (usando o cabeçalho <algorithm>) e tente outra compilação usando std::set.

Compare o tamanho das implementações (número de linhas de código), compare o número de bugs, comparar a velocidade, e depois decidir.

Na maioria das vezes, a 'optimização' você apontar para é realmente um pessimization , e nesses raros momentos não é, isso é tão complicado que não vale a pena.

Otimização :

• NÃO
• perito só: Não, nós queremos dizer isto

Answer 5

O vector é ordenada em termos de tempo

A hora de início ou fim do tempo?

O que é errado com um O ingênuo (n) procurar? Lembre-se você está apenas à procura e não a classificação. Você pode usar um recipiente ordenada, bem como (se isso não vai contra o projeto básico).