Ricerca in un vettore C ++ < custom_class > per la prima / ultima occorrenza di un valore

Question

Sto cercando di trovare il metodo migliore per cercare un vettore di tipo " Tracklet " (una classe che mi sono costruito) per trovare la prima e l'ultima occorrenza di un dato valore per una delle sue variabili. Ad esempio, ho le seguenti classi (semplificate per questo esempio):

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

Ho un vettore " vettore < Tracklet > tracklets " e ho bisogno di cercare eventuali tracklet con un dato valore di " t " per il punto finale. Il vettore è ordinato in termini di ora di fine (ovvero tracklet.end- > t ).

Sono felice di codificare un algoritmo di ricerca, ma non sono sicuro di quale percorso seguire. Non sono sicuro che la ricerca binaria sia adatta, poiché mi sembra di ricordare che non troverà necessariamente il primo. Stavo pensando a un metodo in cui uso la ricerca binaria per trovare un indice di un elemento con l'ora corretta, quindi riproverò per trovare il primo e in avanti per trovare l'ultimo. Sono sicuro che c'è un modo migliore di quello, dal momento che spreca ricerche binarie O (log n) ripetendo.

Speriamo che abbia un senso: ho faticato a spiegarlo un po '! Cheers!

Answer 1

Se il vettore è ordinato e contiene il valore, std :: lower_bound ti darà un iteratore al primo elemento con un dato valore e std :: upper_bound ti dà un iteratore a un elemento oltre l'ultimo contenente il valore. Confronta il valore con l'elemento restituito per vedere se esisteva nel vettore. Entrambe queste funzioni usano la ricerca binaria, quindi il tempo è O (logN).

Per confrontare su tracklet.end- > t , usa:

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

e passa compareTracklets come quarto argomento a lower_bound o upper_bound

Answer 2

Userei find e find_end e quindi fare qualcosa di più complicato solo se si esegue il test dimostrato che è troppo lento.

Se sei davvero preoccupato per le prestazioni di ricerca, potresti prendere in considerazione una diversa struttura di dati, come una mappa con data e ora come chiave e un vettore o elenca di elementi come valore.

Answer 3

Una ricerca binaria sembra l'opzione migliore qui, purché il tuo vettore rimanga ordinato. È essenzialmente identico, dal punto di vista delle prestazioni, eseguire una ricerca in una struttura ad albero binaria.

Answer 4

riferito indirettamente a un dolce comparativo di ottimizzazione. Ma in realtà non userei un std :: vector per questo.

Di solito, quando decido di usare un contenitore STL, non prendo davvero in considerazione l'aspetto delle prestazioni, ma considero la sua interfaccia per quanto riguarda il tipo di operazione che desidero usare.

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

In realtà, se vuoi una sequenza ordinata, al di fuori di una configurazione chiave / valore, std :: set è semplicemente più facile da usare rispetto a qualsiasi altro.

• Non devi preoccuparti di inserire in una posizione 'cattiva'
• Non si hanno problemi di invalidazione degli iteratori durante l'aggiunta / rimozione di un elemento
• Hai metodi integrati per la ricerca

Ovviamente, vuoi anche che il tuo Predicato di confronto risplenda davvero (spera che il compilatore sia in linea con l'implementazione dell'operatore) in ogni caso.

Ma davvero, se non sei convinto, prova una build con un std :: vector e l'inserimento / ricerca manuale (usando l'intestazione < algoritmo > ) e prova un'altra build usando std :: set .

Confronta le dimensioni delle implementazioni (numero di righe di codice), confronta il numero di bug, confronta la velocità e poi decidi.

Molto spesso, l '"ottimizzazione" a cui aspiri è in realtà un pessimizzazione , e in quei tempi rari non lo è, è così complicato da non valerne la pena.

Ottimizzazione :

• Non
• Solo esperto: non lo intendiamo sul serio

Answer 5

  

Il vettore è ordinato in termini di tempo

L'ora di inizio o l'ora di fine?

Cosa c'è di sbagliato in una ricerca O (n) ingenua? Ricorda che stai solo cercando e non ordinando. Puoi anche usare un contenitore ordinato (se ciò non va contro il design di base).