Promedio rápido sin división

Question

Tengo un bucle de búsqueda binaria que se golpea muchas veces en la ruta de ejecución.

Un perfilador muestra que la parte de la división de búsqueda (búsqueda del índice medio teniendo en cuenta los índices altos y bajos de la gama de búsqueda) es en realidad la parte más costosa de la búsqueda, en un factor de aproximadamente 4.

(creo) no es crítico para la búsqueda binaria eficiente encontrar el valor medio exacto, solo un valor cercano al medio que no tiene sesgo en ninguna dirección.

¿Hay algún algoritmo que alterne poco para reemplazar mid = (low + high)/2 con algo mucho más rápido?

Editar: El lenguaje es C#, pero la operación de bit equivalente es válida en cualquier idioma (aunque puede no tener ningún beneficio en el rendimiento), por lo que dejé la etiqueta C# desactivada.

Answer 1

int mid = (low + high) >>> 1; 

tenga en cuenta que el uso de "(bajo + alto)/2" para los cálculos de punto medio won't work correctly cuando desbordamiento de entero se convierte en un problema.

Answer 2

Puede usar el desplazamiento de bits y también superar un posible problema de desbordamiento:

low + ((high-low) >> 1) 

Sin embargo, debo admitir que esperaba que los compiladores modernos e intérpretes que hacer la división por 2 (o división por cualquier otra potencia constante de 2) como un cambio de bit, por lo que no estoy seguro de si realmente ayudará, pruébelo.

Answer 3

Si no recuerdo mal, hay algunos casos donde el uso exacto del medio de la matriz puede ser más lento. La solución es aleatorizar la elección del índice donde se biseca la matriz. Igualmente cierto del algoritmo para determinar la mediana de una matriz.

No recuerdo los detalles precisos, pero recuerdo haber escuchado en la clase 6 del MIT algorithms series en iTunes.

Answer 4

Aquí es una versión poco-hack del medio que no sufren el problema de desbordamiento:

unsigned int average (unsigned int x, unsigned int y) 
{ 
    return (x&y)+((x^y)>>1); 
} 

Answer 5

para ampliar aún más sobre Nils' respuesta Richard Schroeppel inventado esto.

http://www.inwap.com/pdp10/hbaker/hakmem/boolean.html#item23

PUNTO 23 (Schroeppel):

(A y B) + (A o B) = A + B = (A XOR B) + 2 (A y B).

(A + B)/2 = ((A XOR B) + 2(A AND B))/2 
      = (A XOR B)/2 + (A AND B) 
      = (A XOR B)>>1 + (A AND B) 


avg(x,y){return((x^y)>>1)+(x&y);} 

(A AND B) + (A OR B) = A + B porque A AND B da la suma de las potencias compartido (entre A y B) de dos, A OR B da tanto los compartidos y los que no son, por lo tanto:

(A AND B) + (A OR B) = 
    (sum of shared powers of two) + 
    ((sum of shared powers of two) + (sum of unshared powers of two)) = 
    (sum of shared powers of two) + 
    ((sum of shared powers of two) + (sum of powers of two of A only) + 
    (sum of powers of two of B only)) = 
     ((sum of shared powers of two) + (sum of powers of two of A only)) + 
     ((sum of shared powers of two) + (sum of powers of two of B only)) 
= A + B. 

A XOR B da un mapa de esos bits que difieren entre A y B.Por lo tanto,

A XOR B = (sum of powers of two of A only) + (sum of powers of two of B only). 

Y así:

2(A AND B) + (A XOR B) = 
     ((sum of shared powers of two) + (sum of powers of two of A only)) + 
     ((sum of shared powers of two) + (sum of powers of two of B only)) 
= A + B. 

Answer 6

Trate baja + ((alto - bajo)/2)). Esto debería funcionar porque solo está tomando el promedio de dos números. Esto reduciría la cantidad de tiempo que el algoritmo está tomando si la lista de búsqueda binaria es bastante grande, ya que alta - baja es mucho más pequeña que alta + baja.