Tengo curiosidad por saber si alguien podría explicarme una implementación de búsqueda binaria sin sucursales. Lo vi mencionar en un reciente question pero no puedo imaginar cómo se implementaría. Supongo que podría ser útil para evitar ramas si la cantidad de elementos es bastante grande.Búsqueda binaria sin sucursales
Voy a suponer que estás hablando de la frase "Haz una matriz static const de todos los cuadrados perfectos en el dominio que deseas admitir, y realiza una búsqueda binaria rápida sin ramas". encontrado en this answer.
A "sucursales" búsqueda binaria es básicamente un bucle de búsqueda binaria desenrollado. Esto solo funciona si sabe de antemano la cantidad de elementos en la matriz que está buscando (como lo haría si es static const). Puede escribir un programa para escribir el código desenrollado si es demasiado largo para hacerlo a mano.
Luego, debe punto de referencia su solución para ver si realmente es más rápido que un bucle. Si su código sin sucursales es demasiado grande, no cabe dentro de la memoria caché de instrucciones rápida de la CPU y tardará más tiempo en ejecutarse que el ciclo equivalente.
Si uno tiene una función que devuelve +1, -1 o 0 según la posición del elemento correcto frente al actual, se puede inicializar la posición para listar el tamaño/2, y los pasos a la posición/2, y luego, después de cada comparación, coloque la posición + = dirección * tamaño de los pasos; Stepsize = tamaño de los pasos/2. Itera hasta que el tamaño del paso sea cero.
"Iterar hasta que el tamaño del paso sea cero". ¿Cómo es sin sucursales está haciendo una rama no cero? – rlibby
Si se conoce el valor inicial, se puede desenrollar el ciclo el número de veces requerido. Alternativamente, algunas plataformas de hardware (especialmente DSP) admiten un bucle "DO" al estilo Fortran en hardware; cuando se extrae una instrucción de una dirección que coincide con la dirección del extremo del bucle, el contador del bucle decrecerá y el contador del programa se cargará con la dirección de inicio del bucle. Cero ciclos de sobrecarga para el bucle. – supercat
ramas calculadas son todavía ramas. El despliegue del bucle no tiene ramificaciones (o al menos puede serlo), pero no usa ninguna condición como "hasta que el tamaño del paso sea cero". – rlibby
Ah bien ahora lo entiendo gracias. Supuse que había algunos movimientos extraños para evitar las declaraciones if dentro del ciclo. – GWW
+1 porque esta es de hecho una forma útil de eliminar bucles de bucles, aunque de un comentario posterior sobre esa pregunta parece que R. pretendía los "bits twiddle para evitar ramas condicionales" en su lugar. Al hacer ambas cosas, podrías evitar * todas * las ramas. –
Tal "sucursales" desenrollado de búsqueda aparece en "Perlas de programación" de Bentley, IIRC, donde explica la técnica de fondo –