Necesito un algoritmo de búsqueda binaria optimizado en una matriz de números ordenados. Hice esto y descubrí que usar float para almacenar números es más rápido que usar enteros, porque al final debo calcular
(frameNumber-this->frameNumber[imin])/(this->frameNumber[imax]-this->frameNumber[imin]) this->frameNumber[imin] es el frameNumber más grande menos igual que frameNumber y this->frameNumber[imax] es el más pequeño mayor igual que eso. Ese código es para calcular el progreso entre esos dos fotogramas clave. la matriz frameNumber es estática. Sólo tengo que ordenarlo una vez. Pero acceda a él muchas veces con una búsqueda binaria y el código anterior para calcular el progreso.
La conversión de int a float pasó algunos ciclos. Luego descubrí que en el asm hay muchas instrucciones fpu. Me preocupa que puedan ser más lentos que enteros.
Así que aquí está la cuestión. ¿Puedo convertir una matriz de números de punto flotante ordenados en un int* y ejecutar una búsqueda binaria en él?
Eso significa:
void binary_search(float key,float* array,...) { int key_integer=*(int*)&key; int* array_intege(int*)array; binary_search_for_integers(key_integer,array_integer,...); }¿O mi conclusión anterior es incorrecta? (¿Por ejemplo, convertir int en float no es tan costoso, o la comparación entre puntos flotantes es tan rápida como los números enteros?
¡Muchas gracias!
Esto parece una mala idea. El uso de comparaciones de enteros en datos flotantes en realidad dará como resultado una matriz ordenada correctamente de flotantes, como señala @rlbond. (Consulte http://www.h-schmidt.net/FloatConverter/IEEE754.html para jugar con las representaciones binarias de los flotadores). Verifique que sizeof(int32_t) == sizeof(float) antes de usar esto.
Un truco como este no es realmente necesario. La comparación float no es mucho más costosa que la comparación int , en hardware moderno. (Intel Haswell: ucomiss es 1 uop, con un rendimiento de 1 por ciclo. Comparar con un operando de memoria es de 2 uops, sin microfusión, sin embargo. Y no puede macro-fusionarse como cmp/jcc ) Sin embargo, FP add/sub y FP mul tienen latencias más altas que sus equivalentes enteros y menos rendimiento. Parece una tontería convertir una matriz completa para que float mientras escribe en ella solo porque desea hacer algunos cálculos de FP con los valores mínimo y máximo al final.
Una instrucción load-and-convert-int-to-float (x86 cvtsi2ss (signed-integer 2 scalar single)) es casi tan rápida y ocupa el mismo espacio de código que una carga normal ( movss ).
Si sus datos originalmente eran enteros y solo usa algunos de ellos, use int (evitando la conversión de valores que nunca necesitará más adelante). Si accede a todos ellos y solo usa sus datos como flotantes, guárdelos como float . Si lo usa como ambos, probablemente sea mejor almacenarlo como int , por lo que es más rápido cuando lo usa como un número entero y aproximadamente a la misma velocidad cuando lo usa como flotante.
De su muestra de código, ¿solo está usando los valores en las posiciones mínima y máxima? Es mucho más rápido encontrar los valores mínimo y máximo en una matriz que ordenar la matriz completa. min/max incluso vectoriza con instrucciones empaquetadas-min.
Muchas plataformas no tienen un punto flotante tan rápido como las CPU Intel modernas, así que no se exceda con el punto flotante.