Buscando un vector de C ++ < custom_class > para la primera / última aparición de un valor

Question

Estoy tratando de encontrar el mejor método para buscar un vector de tipo " Tracklet " (una clase que he construido yo mismo) para encontrar la primera y última aparición de un valor dado para una de sus variables. Por ejemplo, tengo las siguientes clases (simplificadas para este ejemplo):

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

Tengo un vector " vector < Tracklet > tracklets " y necesito buscar cualquier tracklet con un valor dado de & t; t " para el punto final de tiempo. El vector se ordena en términos de tiempo de finalización (es decir, tracklet.end- > t ).

Estoy feliz de codificar un algoritmo de búsqueda, pero no estoy seguro de qué ruta tomar con él. No estoy seguro de que la búsqueda binaria sea adecuada, ya que parece recordar que no necesariamente encontrará la primera. Estaba pensando en un método en el que utilizo la búsqueda binaria para encontrar un índice de un elemento con el tiempo correcto, luego itero hacia atrás para encontrar el primero y hacia adelante para encontrar el último. Estoy seguro de que hay una mejor manera que eso, ya que desperdicia las búsquedas binarias O (log n) iterando.

Espero que tenga sentido: ¡luché por explicarlo un poco! ¡Saludos!

Answer 1

Si el vector está ordenado y contiene el valor, std :: lower_bound le dará un iterador al primer elemento con un valor dado y std :: upper_bound darle un iterador a un elemento más allá del último que contiene el valor. Compare el valor con el elemento devuelto para ver si existía en el vector. Ambas funciones utilizan la búsqueda binaria, por lo que el tiempo es O (logN).

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

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

y pase compareTracklets como el cuarto argumento para lower_bound o upper_bound

Answer 2

Simplemente usaría find y find_end , y luego haga algo más complicado solo si realiza la prueba demostró que es demasiado lento.

Si realmente le preocupa el rendimiento de la búsqueda, podría considerar una estructura de datos diferente, como un mapa con marca de tiempo como clave y un vector o lista de elementos como el valor.

Answer 3

Una búsqueda binaria parece ser su mejor opción aquí, siempre que su vector permanezca ordenado. Es esencialmente idéntico, en cuanto al rendimiento, realizar una búsqueda en una estructura de árbol binaria.

Answer 4

dirkgently referido a una dulce optimización comparativa. Pero, de hecho, no usaría un std :: vector para esto.

Por lo general, cuando decido usar un contenedor STL, realmente no considero el aspecto del rendimiento, pero sí considero su interfaz con respecto al tipo de operación que deseo usar.

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

Realmente, si desea una secuencia ordenada, fuera de una configuración de clave / valor, std :: set es más fácil de usar que cualquier otra.

• No tiene que preocuparse por insertar en una posición 'mala'
• No tiene problemas de invalidación de iteradores al agregar / eliminar un elemento
• Tiene métodos incorporados para buscar

Por supuesto, también desea que su predicado de comparación realmente brille (espera que el compilador incorpore la implementación del operador ()), en todos los casos.

Pero realmente, si no está convencido, intente una compilación con un std :: vector e inserción / búsqueda manual (utilizando el encabezado < Algoritmo > ) y intente otra compilación usando std :: set .

Compare el tamaño de las implementaciones (número de líneas de código), compare el número de errores, compare la velocidad y luego decida.

Muy a menudo, la 'optimización' que busca es en realidad una pesimismo , y en esos raros momentos no lo es, es tan complicado que no vale la pena.

Optimización :

• Don't
• Solo expertos: no, lo decimos en serio

Answer 5

  

El vector está ordenado en términos de tiempo

¿La hora de inicio o la hora de finalización?

¿Qué tiene de malo una ingenua búsqueda de O (n)? Recuerde que solo está buscando y no ordenando. También podría usar un contenedor ordenado (si eso no va en contra del diseño básico).