Tengo una serie de flotadores, ordenados de menor a mayor, y necesito poder elegir el flotador más cercano mayor o menor que un valor de entrada pasado. Este valor de entrada no está necesariamente presente como un valor en la matriz.
Un enfoque ingenuo sería hacer una búsqueda lineal simple a través de la matriz. Eso podría verse así:
void FindClosestFloatsInArray( float input, std::vector<float> array,
float *min_out, float *max_out )
{
assert( input >= array[0] && input < array[ array.size()-1 ] );
for( int i = 1; i < array.size(); i++ )
{
if ( array[i] >= input )
{
*min = array[i-1];
*max = array[i];
}
}
}
Pero obviamente, a medida que la matriz se hace más grande, esto se volverá más y más lento.
¿Alguien tiene una idea sobre un algoritmo que me permita encontrar estos datos de manera más óptima? Ya cambié a una búsqueda binaria, que mejoró un poco las cosas, pero sigue siendo mucho más lenta de lo que me gustaría, y como en realidad no estoy buscando un valor específico que exista en la matriz, nunca puede terminar temprano.
Más información: Los valores de coma flotante en la matriz no se distribuyen necesariamente de manera uniforme (es decir, la matriz podría consistir en los valores "1.f, 2.f, 3.f, 4.f, 100.f, 1200.f , 1203.f, 1400.f ".
Estoy haciendo esta operación cientos de miles de veces, pero puedo hacer cualquier cantidad de preprocesamiento en la matriz de flotadores, si mejora el tiempo de búsqueda. Absolutamente puedo cambiar para usar algo que no sea un vector para almacenarlos, si eso ayuda.
fuente
Respuestas:
El código en la pregunta (una búsqueda lineal), como señala correctamente, se volverá lento para las grandes matrices flotantes. Técnicamente es O (n) donde n es el número de valores flotantes en su matriz.
En general, lo mejor que puede hacer para encontrar un valor en una matriz ordenada es una búsqueda de árbol recursiva de algún tipo (por ejemplo, búsqueda binaria), en cuyo caso puede lograr un tiempo de búsqueda O (log n) en el número de elementos en tu matriz O (log n) es mucho mejor que O (n) para valores grandes de n.
Por lo tanto, mi enfoque sugerido sería una simple búsqueda binaria de la matriz , es decir:
Este es un algoritmo O (log n) que debería ser lo suficientemente rápido para casi todas las situaciones. Intuitivamente, funciona reduciendo a la mitad el rango que se buscará en cada paso hasta que encuentre el valor correcto.
Es realmente difícil superar la búsqueda binaria simple, por lo que si ya ha implementado esto correctamente, entonces puede estar bastante cerca del óptimo. Sin embargo, si conoce las distribuciones de los datos y / o tiene un rango limitado de valores de búsqueda (x), todavía hay otros trucos más avanzados que puede probar:
Sin embargo, a menos que se encuentre en una situación muy especial, probablemente le recomiende seguir con la búsqueda binaria simple. Razones:
fuente
Esto parece bastante simple:
Haga una búsqueda binaria para el flotante que desea vincular: tiempo O (log n).
Entonces el elemento a la izquierda es el límite inferior, y el elemento a la derecha es el límite superior.
fuente
La respuesta obvia es almacenar las carrozas en un árbol . Las operaciones de soporte 'anteriores' y 'siguientes' son triviales en un árbol. Así que solo haga un 'siguiente' en su valor, y luego haga un 'anterior' en el valor que encuentre en el primer paso.
fuente
Este artículo ("búsqueda sublogarítmica sin multiplicaciones") podría ser de interés; Incluso contiene algo de código fuente. Para fines de comparación, puede tratar un número flotante como un entero con el mismo patrón de bits; Este fue uno de los objetivos de diseño del estándar de coma flotante IEEE.
fuente