Recherche dans un vecteur C ++ < custom_class > pour la première / dernière occurrence d'une valeur

Question

J'essaie de déterminer la meilleure méthode pour rechercher un vecteur de type "Tracklet". (une classe que j'ai construite moi-même) pour trouver la première et la dernière occurrence d'une valeur donnée pour l'une de ses variables. Par exemple, j'ai les classes suivantes (simplifiées pour cet exemple):

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

J'ai un vecteur " vecteur < Tracklet > tracklets " et je dois rechercher tous les tracklets ayant une valeur donnée de " t " pour l'heure de fin. Le vecteur est classé en termes d’heure de fin (c.-à-d. tracklet.end- > t ).

Je suis heureux de coder un algorithme de recherche, mais je ne suis pas sûr de la route à suivre. Je ne suis pas sûr que la recherche binaire convienne, car je me souviens bien qu'elle ne trouvera pas nécessairement le premier Je pensais à une méthode dans laquelle j'utilise la recherche binaire pour trouver un index d'un élément avec l'heure correcte, puis itérer en arrière pour trouver le premier et avancer pour trouver le dernier. Je suis sûr qu'il existe un meilleur moyen que cela, car cela gaspille les recherches binaires O (log n) en effectuant une itération.

J'espère que cela a du sens: j'ai eu du mal à l'expliquer un peu! À la vôtre!

Answer 1

Si le vecteur est trié et contient la valeur, std :: lower_bound vous donnera un itérateur pour le premier élément avec une valeur donnée et std :: upper_bound vous donne un itérateur pour un élément passé le dernier contenant la valeur. Comparez la valeur avec l'élément renvoyé pour voir si elle existait dans le vecteur. Ces deux fonctions utilisent la recherche binaire, le temps est donc O (logN).

Pour comparer sur tracklet.end- > t , utilisez:

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

et transmettez compareTracklets en tant que quatrième argument de lower_bound ou upper_bound

Answer 2

Je voudrais simplement utiliser find et find_end , puis faites quelque chose de plus compliqué que si vous testez montré qu'il était trop lent.

Si les performances de recherche vous préoccupent vraiment, vous pouvez envisager une structure de données différente, telle qu'une carte avec horodatage comme clé et un vecteur ou . liste des éléments en tant que valeur.

Answer 3

Une recherche binaire semble être votre meilleure option ici, tant que votre vecteur reste trié. C’est essentiellement la même chose, en termes de performances, que de rechercher une structure arborescente binaire.

Answer 4

Dirkgently a référé à une comparaison d'optimisation douce. Mais je n’utiliserais pas un std :: vector pour cela.

Habituellement, lorsque je décide d'utiliser un conteneur STL, je ne considère pas vraiment l'aspect performance, mais son interface en ce qui concerne le type d'opération que je souhaite utiliser.

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

Vraiment, si vous voulez une séquence ordonnée, en dehors d'une configuration clé / valeur, std :: set est tout simplement plus facile à utiliser que tout autre.

• Vous n'avez pas à vous soucier de l'insertion dans une "mauvaise" position
• Vous n'avez pas de problèmes d'invalidation des itérateurs lors de l'ajout / la suppression d'un élément
• Vous disposez de méthodes intégrées pour la recherche

Bien sûr, vous voulez aussi que votre prédicat de comparaison brille vraiment (espère que le compilateur insère l'implémentation de operator ()), dans tous les cas.

Mais vraiment, si vous n'êtes pas convaincu, essayez une construction avec std :: vector et une insertion / recherche manuelle (à l'aide de l'en-tête < algorithm > ) et essayez une autre construction en utilisant std :: set .

Comparez la taille des implémentations (nombre de lignes de code), comparez le nombre de bogues, comparez la vitesse, puis décidez.

Le plus souvent, l'optimisation que vous visez est en fait une pessimisation , et dans ces rares cas ce n’est pas, c’est tellement compliqué que ça ne vaut pas la peine.

Optimisation :

• Ne pas
• réservé aux experts: non, nous le pensons

Answer 5

  

Le vecteur est ordonné en termes de temps

L'heure de début ou l'heure de fin?

Quel est le problème avec une recherche O (n) naïve? Rappelez-vous que vous ne faites que rechercher et non trier Vous pouvez également utiliser un conteneur trié (si cela ne va pas à l’encontre de la conception de base).