Analizar algoritmos de búsqueda en arreglos ordenados basados en funciones de comparación, con el objetivo de localizar elementos y posiciones específicas, usando técnicas de peor caso y adaptables a la distribución de los datos para una solución eficiente de problemas informáticos.
Sea \(A[1..n] = a_1, \cdots, a_n\) un arreglo ordenado con \(n \geq 1\) y un operador \(<\) (menor que); por simplicidad, también usaremos \(\leq\) (menor o igual que). Supondremos que no hay elementos duplicados en \(A\), note que esto no implica una perdida de generalidad.
La tarea será: dado el valor \(x\) a ser localizado en \(A\), el problema consiste en determinar la posición de inserción \(p\) tal que suceda alguna de las siguientes condiciones:
Para \(A[1..n]\) y el valor \(x\) a localizar su posición de inserción, el resultado puede ser cualquiera de las \(n+1\) posiciones posibles, i.e., instancias del problema. Un algoritmo naïve utilizaría \(n\) comparaciones para resolverlo.
"""
seqsearch(A, x, sp=1)
Búsqueda exhaustiva con inicio
"""
function seqsearch(A, x, sp=1)
n = length(A)
while sp <= n && x > A[sp]
sp += 1
end
sp
end
let S=[10, 20, 30, 40, 50, 60, 70]
(seqsearch(S, 0), seqsearch(S, 69), seqsearch(S, 70), seqsearch(S, 71))
end(1, 7, 7, 8)Sin embargo, dado que el arreglo esta ordenado y no hay duplicados, se puede mejorar mucho el tiempo de búsqueda.
Si se permiten duplicados se pueden mejorar muchos los tiempos; sobre todo si podemos preprocesar el arreglo, i.e., para determinar las zonas con duplicados.
El costo de búsqueda para cualquier instancia es \(O(\log n)\), y viene de la búsqueda binaria:
"""
binarysearch(A, x, sp=1, ep=length(A))
Encuentra la posición de inserción de `x` en `A` en el rango `sp:ep`
"""
function binarysearch(A, x, sp=1, ep=length(A))
3 while sp < ep
1 mid = div(sp + ep, 2)
if x <= A[mid]
2 ep = mid
else
sp = mid + 1
end
end
4 x <= A[sp] ? sp : sp + 1
end
let S=[10, 20, 30, 40, 50, 60, 70]
(binarysearch(S, 0), binarysearch(S, 69), binarysearch(S, 70), binarysearch(S, 71))
end(1, 7, 7, 8)Este algoritmo es simple y efectivo, y es capaz de resolver cualquier instancia en tiempo logarítmico, y esto lo hace al dividir el rango siempre a la mitad por cada iteración. El costo de búsqueda binaria es de \(C_\text{bin}(n) = \lfloor \log n \rfloor + O(1)\) comparaciones antes de colapsar el rango donde puede estar la posición de inserción.
Es importante hacer notar que la búsqueda binaria es muy eficiente en memoría y tiene un peor caso óptimo, ya que es idéntico al costo del problema, i.e., así lo determinamos. Si fuera posible tener probar varios puntos, i.e., \(m\) segmentos en una sola operación, el costo estaría acotado en \(\lceil \log_{m} n \rceil\). Esto tiene sentido para estructuras de datos que trabajan en diferentes niveles de memoría, donde aunque las comparaciones en hardware moderno sean binarias, la diferencia entre velocidades de los diferentes niveles de memoria se puede pensar que el costo dominante es, por ejemplo, acceder a una zona de disco y obtener una decisión entre \(m-1\) posibles, que particionan los rangos en \(m\) divisiones.
Cuando el tamaño del arreglo es demasiado grande, o la relación entre \(p / n\) es significativamente pequeña, la búsqueda acotada no es la mejor opción. Aun cuando en la práctica el límite superior \(n\) podría estar determinado, y por lo tanto, se pueden resolver búsquedas en \(O(\log n)\), es posible obtener una cota relativa a \(p\), independiente de \(n\), por lo que los casos de interés se verán beneficiados.
Una estrategia simple y poderosa es la siguiente:
Bentley y Yao (1976) describen a detalle una familia de algoritmos casí óptimos para la búsqueda no acotada siguiendo la estrategía anteriormente mencionada. En particular, poniendo un enfásis importante en la determinación del rango. Lo consigue mediante la definición de algoritmos definidos de manera interesante como sigue en el resto de la sección.
Es el algoritmo más simple, y ya lo vimos con anterioridad, realiza una búsqueda exhaustiva de la posición de inserción, hacendo pruebas para toda posición \(x \leq A[1], x \leq A[2], \cdots, x \leq A[p+1]\), por lo que su costo será de \(p+1\).
Sea \(F_0(n)\) una secuencia de puntos para un arreglo de longitud \(n\), donde se harán comparaciones para determinar el rango que contenga la respuesta para el algoritmo \(B_0\) y \(C_0(p)\) el costo de búsqueda. Entonces:
Consiste en comparar las posiciones \(2^i\), i.e., \(2^1, 2^2, 2^3, \cdots, 2^{\lfloor \log_2{p+1} \rfloor + 1}\), tal que \(A[2^{\lfloor\log_2{p}\rfloor+1}] \leq x \leq A[2^{\lfloor\log_2{p+1}\rfloor+1}]\). De manera similar que para \(B_0\) definimos \(F_1(n)\) y \(C_1\):
La explicación viene a continuación. El número de comparaciones para determinar el rango esta determinado por \(\lfloor \log_2{p+1} \rfloor + 1\). Una vez determinado el rango la búsqueda binaria sobre \[A[2^{\lfloor\log_2{p}\rfloor+1}:2^{\lfloor\log_2{(p+1)}\rfloor+1}],\] lo cual corresponde a \(\log_2 2^{\log{(p+1)}+1}/2 = \log_2{(p+1)}\). El costo \(C_1(p)\) puede ser escrito como \(2\log_2 p + O(1)\), con un poco de manipulación algebraica.
Es importante saber cuando usar un algoritmo u otro, por tanto determinar cuando \(2\log_2{p} + O(1) < \log_2 n + O(1).\) Para simplificar este análisis ignoraremos algunos detalles de la expresión: \[\begin{align} 2\log_2{p} & < \log_2 n, \\ 2^{\log_2{p^2}} & < 2^{\log_2 n}, \\ p^2 & < n, \\ p & < \sqrt{n}; \\ \end{align}\] esto indica que si \(p\) es menor a \(\sqrt{n}\) entonces hay una ventaja al usar \(B_1\); lo cual nos dice que para posiciones cercanas al inicio el uso de \(B_1\) puede llevar a búsquedas más veloces. Note que en la práctica es necesario tener en cuenta la memoria, interesantemente, para \(p\) pequeñas es posible que esto beneficie al algoritmo ya que podría mantener las listas en cache.
El siguiente código implementa \(B_1\)
function doublingsearch(A, x, sp=1)
n = length(A)
p = 0
i = 1
1 while sp+i <= n && A[sp+i] < x
p = i
i += i
end
2 binarysearch(A, x, sp + p, min(n, sp+i))
end
let S=[10, 20, 30, 40, 50, 60, 70]
(doublingsearch(S, 0), doublingsearch(S, 69), doublingsearch(S, 70), doublingsearch(S, 71))
end(1, 7, 7, 8)Es cierto que estos algoritmos son oportunistas, pero hay aplicaciones donde esto realmente sucede. En el peor caso, el costo será apenas dos veces el óptimo.
Aquí será más clara la dinámica. \(B_2\) consiste en comparar las posiciones \(2^{2^i}\), i.e., \(2^{4}, 2^{16}, 2^{256}, \cdots, 2^{2^{\lfloor \log_2{\lfloor\log_2{p+1}\rfloor + 1} \rfloor + 1}}\), tal que \[A[2^{2^{\lfloor\log_2{\lfloor\log_2{p}\rfloor+1}\rfloor + 1}}] \leq x \leq A[2^{2^{\lfloor\log_2{\lfloor\log_2{p+1}\rfloor+1}\rfloor + 1}}];\] La determinación de este rango requiere \(\lfloor\log_2{\lfloor\log_2{p+1}\rfloor+1}\rfloor+1\) comparaciones; sin embargo, este rango seguramente será muy grande, por el tamaño de los saltos que se estan dando entre puntos de comparación, por lo que no conviene usar busqueda binaria y podemos aplicar \(B_1\) para resolver en ese rango acotado.
\[\begin{align} F_2(n) &= 2^{2^1}, 2^{2^2}, \cdots, 2^{2^{\lfloor \log_2 {\lfloor \log_2 n \rfloor} + 1 \rfloor + 1}};\\ C_2(p) &= \lfloor \log_2 {\lfloor \log_2 p \rfloor} + 1 \rfloor + 1 + C_1(p') \\ &< \log_2 p + 2\log_2{\log_2 p} + O(1);\\ \end{align}\] donde \(p' = p - 2^{2^{\lfloor \log_2 {\lfloor \log_2 p \rfloor} + 1 \rfloor}}\), es decir, la posición de inserción en el rango ya acotado.
Note como el término de mayor peso es muy similar a \(B_1\) pero destaca la inclusión del término \(\log\log\) que permite adaptarse a \(p\) muy grandes con un pequeño costo adicional, que en términos prácticos se puede ver como una constante.
La idea principal es como sigue: una vez determinado el rango, en lugar de usar búsqueda binaria y tener un costo \(\lfloor \log_2 {\lfloor \log_2 p \rfloor} + 1 \rfloor + 1 + C_\text{bin}(2^{2^{\lfloor \log_2 {\lfloor \log_2 p \rfloor} + 1 \rfloor + 1}} - 2^{2^{\lfloor \log_2 {\lfloor \log_2 p \rfloor} + 1 \rfloor}})\) es preferible usar \(B_1\) y conseguir un algoritmo que se adapte a la entrada. De manera más precisa, tomar ventaja de \[C_1(2^{2^{\lfloor \log_2 {\lfloor \log_2 p \rfloor} + 1 \rfloor + 1}} - 2^{2^{\lfloor \log_2 {\lfloor \log_2 p \rfloor} + 1 \rfloor}}) < C_\text{bin}(2^{2^{\lfloor \log_2 {\lfloor \log_2 p \rfloor} + 1 \rfloor + 1}} - 2^{2^{\lfloor \log_2 {\lfloor \log_2 p \rfloor} + 1 \rfloor}})\] cuando \[p' < \sqrt{2^{2^{\lfloor \log_2 {\lfloor \log_2 p \rfloor} + 1 \rfloor + 1}} - 2^{2^{\lfloor \log_2 {\lfloor \log_2 p \rfloor} + 1 \rfloor}}}\].
Simplificando las expresiones, la relación que nos describe cuando es mejor usar \(B_2\) que la búsqueda binaria es como sigue:
\[\begin{align} {\log_2{p}} + 2\log_2{\log_2{p}} &< \log_2 n\\ 2^{\log_2{p} + \log_2{\log^2_2{p}}} &< 2^{\log_2 {n}}\\ 2^{\log_2{(p \log^2_2{p})}} &< 2^{\log_2 {n}}\\ 2p \log_2{p} & < n\\ p \log_2{p^2} & < n\\ \end{align}\]
Si \(p = \sqrt{n}\) entonces \(\sqrt{n} \log_2 n\) claramente es menor que \(n\) incluso para valores relativamente pequeños de \(n\), por lo que \(B_2\) funciona mejor para \(p\) relativamente grandes en comparación con \(B_1\).
Bentley y Yao (1976) generalizan la estrategía para cualquier \(k\). De manera simplificada:
donde \(\log_2^{(k)}(n) = \log_2(\lfloor \log_2^{(k-1)}{(n)} \rfloor + 1)\), con el caso base de \(\log_2^{(1)} n = \lfloor \log_2 n \rfloor + 1\).
La estrategia lleva a que el valor casi óptimo para la búsqueda por comparación se da cuando \(k=\log^\star_2{n}\) donde \(\log^\star_2\) es el logaritmo iterado, que esta definido como las veces que se debe iterar aplicando el logaritmo para obtener un valor de \(1\) o menor que \(1\), i.e., la \(k\) más pequeña tal que \(\log_2^{(k)}n \leq 1\).
En el siguiente video se adentraran en diferentes estrategías de búsqueda, notoriamente aquellas que llamaremos oportunistas o adaptables (adaptative). Estas técnicas nos permitirán tomar provecho de instancias sencillas de problemas e incrementar el desempeño en ese tipo de instancias.
Tenga en cuenta que, honrando la literatura, usaremos de forma indiscriminada listas ordenadas como sinónimo de arreglos ordenados.