En algoritmo de búsqueda binaria tenemos dos comparaciones:¿Es posible tener solo una comparación por iteración de un algoritmo de búsqueda binario?
if (key == a[mid]) then found;
else if (key < a[mid]) then binary_search(a[],left,mid-1);
else binary_search(a[],mid+1,right);
¿Hay un camino por el cual puedo tener sólo una comparación en lugar de los dos anteriores.
-
Gracias
Alok.Kr.
Ver:
http://en.wikipedia.org/wiki/Binary_search_algorithm#Single_comparison_per_iteration
Tomado de wiki:
low = 0
high = N
while (low < high) {
mid = low + ((high - low)/2)
if (A[mid] < value)
low = mid + 1;
else
//can't be high = mid-1: here A[mid] >= value,
//so high can't be < mid if A[mid] == value
high = mid;
}
// high == low, using high or low depends on taste
if ((low < N) && (A[low] == value))
return low // found
else
return -1 // not found
ventajas/desventajas de wiki: "Este enfoque renuncia a la posibilidad de terminación temprana del descubrimiento de un partido, por lo tanto, las búsquedas exitosas tienen iteraciones de log2 (N) en lugar de iteraciones esperadas de log2 (N) - 1. Por otro lado, esta implementación hace menos comparaciones: log2 (N) es le ss que el número esperado de comparaciones para las implementaciones de dos pruebas de 1 · 5 (log2 (N) - 1), para N mayor que ocho. "
Me gusta que el artículo vinculado declara pros/contras de esta técnica. –
Sí, lo he incluido para que sea explícito y claro, gracias ... –
Este es un algoritmo recursivo. La primera comparación son los criterios de parada y la segunda búsqueda real, por lo que no puede eliminarlos.
En primer lugar usted pregunta cuando ya ha encontrado el elemento y en segundo lugar en qué parte de la matriz busca el elemento. Entonces no puedes tomar esas decisiones basadas solo en una comparación.
Puede crear una función que compare 'key' y' mid [a] 'y devuelve el signo de la comparación (un' int'). La comparación de este 'int' con valores fijos (' -1', '0' o' 1') costará menos (o, en el peor de los casos, tanto) que comparar 'key' y' mid [a] ', dependiendo de qué' key' y 'mid [a]' son. – ereOn
Sí. Simplemente no elimine mid de la llamada recursiva.
if (left == right) return NULL;
if (left + 1 == right) return key == a[left]? &a[left] : NULL;
mid = left + (right - left/2);
if (key < a[mid]) return binary_search(a[],left,mid-1);
else return binary_search(a[],mid,right); // include `mid` in next round
Solo necesita eliminar la mitad del conjunto con cada recursividad para lograr el rendimiento O (logN). Vas más allá al eliminar la mitad + 1.
Si solo usa < durante la recursión, el algoritmo encontrará el menor elemento que no sea inferior a key (pero puede ser mayor que key). Termine realizando una prueba de igualdad única.
¿No necesitaría otra comparación (llamada precursor) para determinar si está utilizando un solo elemento y decide realizar la prueba de igualdad final? –
@Damien: sí, lo agregué como usted comentó. Pero esa prueba no es una comparación * key *, es una comparación de índices, que presumiblemente tiene una complejidad computacional más simple. – Potatoswatter
En ensamblador, usted podría:
cmp key,a[mid]
beq found
bge else
Así que si su compilador es realmente bueno en optimizaciones de mirilla, es posible que ya lo haga por usted.
El compilador probablemente hará esto porque las mirillas son algo que se puede dar por hecho ... de todos modos, la diferencia es insignificante. La pregunta es importante de todos modos, ya que se aplica a los casos en que la comparación es una función costosa. – Potatoswatter
Si la comparación es costosa, cree una función que devuelva el signo de la comparación para que pueda examinar el signo varias veces. –
No es una opción en C++, donde la búsqueda se lleva a cabo mediante una función genérica que requiere un functor con tipo 'bool'. – Potatoswatter
Lo primero es lo primero: ¿necesita optimizar el programa? ¿Has medido para saber dónde tienes que hacerlo? ¿Está en esta función?
Para tipos primitivos, la segunda comparación es una operación lo más rápida posible. El mayor costo de la comparación es cargar el elemento en el registro apropiado, y eso es necesario para la primera comparación. Una vez que se ejecuta la comparación, el valor ya está en un registro y la segunda operación toma una única instrucción del procesador más el posible costo de la predicción errónea de la bifurcación.
Suponiendo tipos integrales, el costo en el tiempo del procesador del algoritmo es muy probablemente dominado por el costo de las llamadas recursivas si el compilador no puede realizar la optimización de recursión de cola. Si realmente necesita optimizar esto, intente compilar con todos los indicadores de optimización y analizar el ensamblador para identificar si se está aplicando la optimización de recursión de cola. De lo contrario, convierta manualmente el algoritmo de recursivo a iterativo.
Esto tendrá dos efectos: oscurecer el código (evite modificar una solución limpia a menos que realmente lo necesite) y evitar llamadas de función.
si usted está hablando de C++, y el tipo es complejo y los operadores de comparación sobrecargados son caros, el impulso más rápido en el rendimiento está implementando un método compare que devolverá un número negativo para menos-que, 0 por igual y un número positivo si mayor que. Luego, precompute el resultado antes de las comparaciones y luego realice solo las pruebas de enteros. Eso eliminará el costo total del algoritmo para un solo procesamiento de los objetos reales con la costosa comparación y lo retrotraerá a la suposición original.
for (step = 0; step < n; step <<= 1);
for (i = 0; step; step >>= 1)
if (i + step < n && v[i + step] <= x)
i += step;
Ok, esta fue una pregunta de la entrevista en Adobe, y yo estaba tratando de encontrar la manera de hacerlo.
Ahora tengo solución a ella, así que, estoy publicando
void binary_search (int a[] , int low , int high , int key)
{
int mid = (low+high)/2;
if (key == a[mid]) {
printf ("Number Found\n");
return;
}
else {
int sign = Calc_sign (key-a[mid]);
low = low*sign + (1-sign)*mid;
high = mid*sign + (1-sign)*right;
binary_search (a,low,high,key);
}
}
int Calc_sign(int a)
{
return ((a & 80000000) >> 31);
}
Así en el código sólo habrá una comparación para comprobar si el valor clave es eqaul al elemento mediados.
-
Gracias
Alok Kr.
Un posible problema con tales comparaciones basadas en matemática ('key-a [mid]') es que podrían desbordarse. Además, solo funciona con tipos numéricos. – UncleBens
Como siempre: ¿necesita ocultar el algoritmo para el rendimiento? ¿Esto está en la ruta del código crítico? ¿El rendimiento de este método específico afecta el rendimiento del programa en general? ¿Es debido a la comparación adicional? Mi apuesta es que la comparación adicional no tiene ningún efecto en general en el tiempo de ejecución del programa. Si realmente necesita optimizar el algoritmo, mida primero, luego piense en lo que está haciendo. Apuesto a que cambiar de recursivo a iterativo a) lo hará menos legible (así que solo hazlo si realmente lo necesitas) yb) mejorará la velocidad del tiempo de ejecución mucho más que la comparación. –
@David: en este caso, parece una pregunta académica importante de saber, y aplicar la optimización hace que el algoritmo sea más canónico. – Potatoswatter
@ David: Solo quería saber si es posible independientemente de la optimización o complejidad. @ Potatoswatter: la pregunta fue hecha una vez en los documentos de colocación de Adobe. Así que solo quería saber si es posible. Ahora también he publicado una posible solución por mi cuenta, pero todavía tengo curiosidad. Gracias Alok.Kr. –