Diferencias

Muestra las diferencias entre dos versiones de la página.

--- algoritmos-oia:busqueda-binaria-separadora [2018/01/19 02:31]
santo
+++ algoritmos-oia:busqueda-binaria-separadora [2018/01/19 15:02] (actual)
santo [Búsqueda binaria separadora]
@@ Línea 1: / Línea 1: @@
 ====== Búsqueda binaria separadora ======
+En este artículo, se discute un uso avanzado de la búsqueda binaria, para una situación muy particular. Es requisito entender bien la [[algoritmos-oia:busqueda-binaria|búsqueda binaria]] usual. Las ideas desarrolladas pueden servir también en otros problemas.
 ==== Situación ====
@@ Línea 31: / Línea 33: @@
 Un claro caso malo para la idea anterior, sería que todas las búsquedas binarias operen sobre un rango muy grande, es decir, que la optimización casi no logre reducir el tamaño de los rangos buscados. Para que esto ocurra, casi todas las fronteras estarán **muy cerca** entre sí, de modo que "saltar" a la siguiente presente muy poco ahorro. Entonces, el problema a subsanar es que si el corte se encuentra muy cerca del comienzo, igual nuestra búsqueda binaria siempre tarda $\lg N$ pasos hasta llegar allí, porque siempre comienza por el medio.
-Una manera de subsanar esto es comenzar siempre desde el principio del rango, pero probando sucesivamente "saltos" de tamaños potencia de 2, cada vez más grandes. Es decir, si $a$ es la posición "base" donde encontramos el corte anterior (de modo que sabemos que el corte de este paso está más adelante), comenzamos evaluando $f$ en las posiciones $a+1$, $a+2$, $a+4$, $a+8$, $a+16$, y así siguiendo hasta que alguna cumpla $f(x) \geq t$, siendo $t$ el valor que buscamos para el corte actual((Si ninguna cumple y saltamos fuera del rango posible, lo consideramos como que funcionó la primera posición fuera de rango)).
+Una manera de subsanar esto es comenzar siempre desde el principio del rango, pero probando sucesivamente "saltos" de tamaños potencia de 2, cada vez más grandes. Es decir, si $a+1$ es la posición "base" donde encontramos el corte anterior (de modo que sabemos que el corte de este paso está más adelante que $a$), comenzamos evaluando $f$ en las posiciones $a+1$, $a+2$, $a+4$, $a+8$, $a+16$, y así siguiendo hasta que alguna cumpla $f(x) \geq t$, siendo $t$ el valor que buscamos para el corte actual((Si ninguna cumple y saltamos fuera del rango posible, lo consideramos como que funcionó la primera posición fuera de rango)).
 Luego, sabremos que el corte debe aparecer dentro del último "salto", y podemos buscarlo allí con una búsqueda binaria usual: por ejemplo, si $f(a+8) < t$, pero $f(a+16) \geq t$, descubrimos que el corte está entre $a+8$ y $a+16$, así que allí lo buscamos con búsqueda binaria.
@@ Línea 47: / Línea 49: @@
 Entonces, lo que haremos en esta versión del algoritmo será **siempre preguntar por el elemento central**. La idea quizás es menos clara ahora, pues en lugar de ir incrementalmente "corte por corte", para aprovechar siempre toda la información que tenemos y no repetir preguntas innecesarias, lo que conviene es calcular **todos los cortes** en la misma función recursiva.
-Supongamos por ejemplo, que tenemos $K=10$ y comenzamos consultando el elemento central, y es $f(c) = 7$. ¿Qué nos dice esto? Nos dice inmediatamente que las primeras apariciones de $8$ y $9$ estarán **a la derecha de $c$**, mientras que las primeras apariciones de $0$,$1$,$2$,$\dots$,$7$ estarán entre $0$ y $c$ inclusive. En otras palabras, el rango de $10$ cortes a analizar que teníamos se nos **separa** en dos: 8 cortes deben ser analizados del lado izquierdo, y 9 cortes deben ser analizados del lado derecho. Lo que hacemos es, recursivamente, analizar cada una de estas mitadas de la misma forma, pero sabiendo que allí la función solamente puede tomar valores en un **subrango** de los $K$ posibles valores totales.
+Supongamos por ejemplo, que tenemos $K=10$ y comenzamos consultando el elemento central, y es $f(c) = 7$. ¿Qué nos dice esto? Nos dice inmediatamente que las primeras apariciones de $8$ y $9$ estarán **a la derecha de $c$**, mientras que las primeras apariciones de $0$,$1$,$2$,$\dots$,$7$ estarán entre $0$ y $c$ inclusive. En otras palabras, el rango de $10$ cortes a analizar que teníamos se nos **separa** en dos: 8 cortes deben ser analizados del lado izquierdo, y 2 cortes deben ser analizados del lado derecho. Lo que hacemos es, recursivamente, analizar cada una de estas mitades de la misma forma, pero sabiendo que allí la función solamente puede tomar valores en un **subrango** de los $K$ posibles valores totales.
 Supongamos que analizamos el caso derecho, por ejemplo: Allí, sabemos que la función solo puede tomar valores $7$, $8$ y $9$, y nos interesa descubrir la primera aparición de $8$ y de $9$ (la primera de 7 no, porque sabemos que apareció antes, ya que una llamada recursiva "nos llamó" habiendo descubierto un valor $7$ a nuestra izquierda). Preguntamos como siempre en la mitad de nuestro rango: ¿Qué pasaría si encontramos un $7$? Sabríamos inmediatamente que la mitad izquierda no sirve para nada, y podemos ignorarla quedando solamente con la mitad derecha, y los mismos valores posibles $7,8,9$. Es decir, en tal caso **reducimos el problema a la mitad**. Lo mismo hubiera ocurrido si hubiéramos encontrado un $9$: La mitad derecha resultaría inútil, y en la izquierda seguiríamos buscando los mismos dos cortes.
@@ Línea 59: / Línea 61: @@
 ==== Comparación de soluciones ====
-En una corrida de ejemplo se obtuvieron los siguientes resultados:
+En una corrida comparativa de estos dos algoritmos eficientes, se obtuvieron los siguientes resultados:
 <code>
-Evaluaciones con saltos exponenciales : 44335
+Para N=10000000 y K=1000
+Evaluaciones con saltos exponenciales : 25846
 Evaluaciones con algoritmo recursivo  : 13429
+Valor teorico  : 13287.7
+Algoritmo directo  : 23230.2
 </code>
-El "valor teórico" $K \lg \left( \frac{N}{K} \right )$ en estos ejemplos da un valor $13287.7$, extremadamente cercano a lo que obtiene el método recursivo.
+El "valor teórico" $K \lg \left( \frac{N}{K} \right )$ en estos ejemplos da un valor extremadamente cercano a lo que obtiene el método recursivo.
+Notar que los algoritmos "directos" que hacen $K-1$ búsquedas binarias superarían en este caso al algoritmo de saltos exponenciales. Esto tiene sentido ya que cuando $K$ no es demasiado grande, realizar todas las búsquedas binarias individuales no es comparativamente tan malo.
+Para una corrida con valores de $K$ más extremos tendremos:
+<code>
+Para N=10000000 y K=100000
+Evaluaciones con saltos exponenciales : 1271222
+Evaluaciones con algoritmo recursivo  : 682974
+Valor teorico  : 664385.62
+Algoritmo directo  : 2325326.41
+</code>
+Si bien la versión recursiva eficiente sigue utilizando aproximadamente la mitad de evaluaciones que la de saltos exponenciales, con estos valores grandes de $K$ la de saltos exponenciales ya supera claramente a la evaluación directa, a diferencia de lo que ocurrió en el otro ejemplo con un $K$ más pequeño.
 El código utilizado, que implementa y compara ambos algoritmos sobre un caso al azar, es el siguiente:
@@ Línea 75: / Línea 94: @@
 #include <cassert>
 #include <algorithm>
+#include <iomanip>
 using namespace std;
 const int N = 10000000;
-const int K = 1000;
+const int K =   100000;
 vector<int> f(K-1);
+// "Evalua la f", es llamada por los algoritmos.
 int ef(int x)
 {
@@ Línea 118: / Línea 139: @@
         }
         resultadoExponenciales[t-1] = b;
+        prev = b-1;
     }
     return total;
@@ Línea 147: / Línea 169: @@
         f[i] = int((double(rand()) / double(RAND_MAX)) * N + 0.5);
     sort(f.begin(), f.end());
+    cout << "Para N=" << N << " y K=" << K << endl;
     cout << "Evaluaciones con saltos exponenciales : " << saltosExponenciales() << endl;
     cout << "Evaluaciones con algoritmo recursivo  : " << recu(-1,N,0,K-1) << endl;
+    cout << "Valor teorico  : " << fixed << setprecision(2) << K*log(double(N)/double(K))/log(2.0) << endl;
+    cout << "Algoritmo directo  : " << fixed << setprecision(2) << (K-1)*log(double(N))/log(2.0) << endl;
     assert(resultadoExponenciales == resultadoRecursivo);
     return 0;
 }
 </code>
+Vemos que como muchas veces ocurre, la implementación que resulta más eficiente es también la más corta, simple y elegante. Lo difícil es formular y entender con claridad las ideas del algoritmo recursivo.
 ==== ¿Por qué puede importar una diferencia tan pequeña en la complejidad? ====
@@ Línea 159: / Línea 187: @@
    * En problemas interactivos (muy comunes por ejemplo en IOI), es posible para el sistema corrector medir exactamente la cantidad de llamadas a las funciones que utilizamos, y en estos casos es fácil (y común) forzar a optimizar la cantidad de llamadas, pues no hace falta medir tiempos para distinguir cuántas llamadas se usan. Por eso en estos problemas, podría ser que una de estas soluciones obtenga 100 puntos y otras no.
-==== Problema de aplicación ====
+==== Problemas de aplicación ====
 Estas ideas pueden utilizarse para resolver exitosamente el problema [[http://ioinformatics.org/locations/ioi17/contest/day2/prize/prize-ARG.pdf|El Gran Premio]], de la IOI 2017.
 Otro problema relacionado con estas ideas es [[http://ioinformatics.org/locations/ioi07/contest/day1/aliens.pdf|Aliens]], de la IOI 2007.

OIA-Wiki

Herramientas de usuario

Herramientas del sitio

Diferencias

Herramientas de la página