performance algorithm binary-search

performance - Búsqueda binaria para una distribución no uniforme



algorithm binary-search (6)

Asumiré de su descripción:

  • X se distribuye uniformemente
  • Y=1/X son sus datos que desea buscar y se almacenan en la tabla ordenada
  • dado el valor y , necesita buscarlo en binario en la tabla anterior

La búsqueda binaria usualmente usa el valor en el centro del rango (mediana). Para una distribución uniforme es posible acelerar la búsqueda sabiendo aproximadamente en qué punto de la tabla debemos buscar el valor buscado.

Por ejemplo, si tenemos valores distribuidos uniformemente en el rango [0,1] y la consulta es de 0.25 , es mejor mirar no en el centro del rango sino en el primer trimestre del rango.

Para utilizar la misma técnica para datos 1 / X , almacene en la tabla, no en Y, sino en inverso en 1 / Y. No busque y sino el valor inverso 1 / y .

La búsqueda binaria es altamente eficiente para distribuciones uniformes. Cada miembro de tu lista tiene la misma probabilidad de ''éxito''. Es por eso que intentas el centro cada vez.

¿Existe un algoritmo eficiente para no tener distribuciones uniformes? Por ejemplo, una distribución después de una distribución 1 / x.

Déjame hacerla precisa. Lo que quieres para la búsqueda binaria es:

Given array A which is sorted, but have non-uniform distribution Given left & right index L & R of search range Want to search for a value X in A To apply binary search, we want to find the index M in [L,R] as the next position to look at. Where the value X should have equal chances to be in either range [L,M-1] or [M+1,R]

En general, por supuesto, usted desea elegir M donde piense que el valor de X debería estar en A. Porque incluso si pierde, la mitad de la "posibilidad" total se eliminaría.

Así que me parece que tienes alguna expectativa acerca de la distribución. Si pudiera decirnos qué quiere decir exactamente con ''1 / x distribución'', entonces tal vez alguien aquí pueda ayudar a desarrollar mi sugerencia para usted.

Déjame dar un ejemplo trabajado.

Usaré una interpretación similar de ''1 / x distribución'' como @Leonid Volnitsky

Aquí hay un código Python que genera la matriz de entrada A

from random import uniform # Generating input a,b = 10,20 A = [ 1.0/uniform(a,b) for i in range(10) ] A.sort() # example input (rounded) # A = [0.0513, 0.0552, 0.0562, 0.0574, 0.0576, 0.0602, 0.0616, 0.0721, 0.0728, 0.0880]

Supongamos que el valor a buscar es:

X = 0.0553

Entonces el índice estimado de X es:

= total number of items * cummulative probability distribution up to X = length(A) * P(x <= X)

Entonces, ¿cómo calcular P(x <= X) ? Es este caso es simple. Revertimos X de nuevo al valor entre [a, b] que llamaremos

X'' = 1/X ~ 18

Por lo tanto

P(x <= X) = (b-X'')/(b-a) = (20-18)/(20-10) = 2/10

Así que la posición esperada de X es:

10*(2/10) = 2

Bueno, y eso es muy preciso!

Para repetir el proceso de predecir dónde está X en cada sección dada de A, se requiere un poco más de trabajo. Pero espero que esto ilustre suficientemente mi idea.

Sé que esto podría no parecer más una búsqueda binaria si puede acercarse tanto a la respuesta en un solo paso. Pero admítalo, esto es lo que puede hacer si conoce la distribución de la matriz de entrada.

El propósito de una búsqueda binaria es que, para una matriz que está ordenada, cada vez que la mitad de la matriz minimiza el peor de los casos, por ejemplo, la peor cantidad posible de comprobaciones es log2 (entradas). Si realiza algún tipo de búsqueda binaria ''desigual'', donde divide la matriz en una mitad más grande y más pequeña, si el elemento está siempre en la mitad más grande, puede tener el peor comportamiento en el peor de los casos. Por lo tanto, creo que la búsqueda binaria aún sería el mejor algoritmo para usar, independientemente de la distribución esperada, solo porque tiene el mejor comportamiento del caso peor.

Hay una conexión profunda entre la búsqueda binaria y los árboles binarios: el árbol binario es básicamente una búsqueda binaria "precalculada" en la que los puntos de corte se deciden por la estructura del árbol, en lugar de ser elegidos mientras se ejecuta la búsqueda. Y como resultado, tratar con los "pesos" de probabilidad para cada tecla a veces se hace con árboles binarios.

Una razón es porque es un árbol de búsqueda binario bastante normal pero conocido de antemano, completo con conocimiento de las probabilidades de consulta.

Niklaus Wirth cubrió esto en su libro "Algorithms and Data Structures", en algunas variantes (una para Pascal, una para Modula 2, otra para Oberon), al menos una de las cuales está disponible para descargar desde su sitio web .

Sin embargo, los árboles binarios no siempre son árboles de búsqueda binarios, y un uso de un árbol binario es derivar un código de compresión Huffman .

De cualquier manera, el árbol binario se construye comenzando con las hojas separadas y, en cada paso, uniendo los dos subárboles menos probables en un subárbol más grande hasta que solo quede un subárbol. Para elegir de manera eficiente los dos subárboles menos probables en cada paso, se utiliza una estructura de datos de cola de prioridad, tal vez un montón binario .

Un árbol binario que se construye una vez y luego nunca se modifica puede tener varios usos, pero uno que se pueda actualizar de manera eficiente es aún más útil. Hay algunas estructuras de datos de árbol binario de peso equilibrado por ahí, pero no estoy familiarizado con ellas. Cuidado: el término "peso equilibrado" se usa comúnmente cuando cada nodo siempre tiene el peso 1, pero los pesos de los subárboles están aproximadamente equilibrados. Algunos de estos pueden ser adaptables para variados pesos de nodos, pero no lo sé con certeza.

De todos modos, para una búsqueda binaria en una matriz, el problema es que es posible usar una distribución de probabilidad arbitraria, pero ineficiente. Por ejemplo, podría tener una matriz de total de pesos en ejecución. Para cada iteración de su búsqueda binaria, desea determinar el punto de distribución a mitad de camino a través de la probabilidad, de modo que determine el valor para eso y luego busque la matriz de totales de pesos en ejecución. Obtiene la siguiente opción perfectamente equilibrada en peso para su búsqueda binaria principal, pero tuvo que hacer una búsqueda binaria completa en su matriz total de ejecución para hacerlo.

Sin embargo, el principio funciona si puede determinar el punto medio ponderado sin buscar una distribución de probabilidad conocida. El principio es el mismo: necesita la integral de su distribución de probabilidad (que reemplaza la matriz total en ejecución) y cuando necesita un punto medio, lo elige para obtener un valor central exacto para la integral. Eso es más un problema de álgebra que un problema de programación.

Un problema con una búsqueda binaria ponderada como esta es que el desempeño en el peor de los casos es peor, generalmente por factores constantes, pero si la distribución es lo suficientemente sesgada, puede terminar con una búsqueda lineal de manera efectiva. Si su distribución asumida es correcta, el rendimiento promedio del caso se mejora a pesar de la lenta búsqueda ocasional, pero si su distribución asumida es incorrecta, puede pagar por eso cuando muchas búsquedas son para artículos que están destinados a ser poco probables según esa distribución. En la forma de árbol binario, los nodos "improbables" están más alejados de la raíz de lo que estarían en un árbol binario simplemente equilibrado (se asume una distribución de probabilidad plana).

Una suposición de distribución de probabilidad plana funciona muy bien, incluso cuando está completamente equivocada: el peor de los casos es bueno, y los casos mejores y promedio deben ser al menos tan buenos por definición. Cuanto más se mueva de una distribución plana, las cosas pueden ser peores si las probabilidades reales de consulta resultan ser muy diferentes de sus suposiciones.

La búsqueda binaria no ponderada ni siquiera es óptima para las claves distribuidas uniformemente en los términos esperados, pero es en el peor de los casos.

La búsqueda binaria ponderada proporcionalmente (que he estado usando durante décadas) hace lo que usted desea para obtener datos uniformes, y al aplicar una transformación implícita o explícita para otras distribuciones. La tabla hash ordenada está estrechamente relacionada (y lo he sabido durante décadas pero nunca me molesté en probarlo).

En esta discusión, asumiré que los datos se seleccionan de manera uniforme entre 1..N y en una matriz de tamaño N indexada por 1..N. Si tiene una solución diferente, por ejemplo, una distribución Zipfian donde el valor es proporcional a 1 / índice, puede aplicar una función inversa para aplanar la distribución, o la Transformada de Fisher a menudo ayudará (vea Wikipedia).

Inicialmente tienes 1..N como límites, pero de hecho puedes conocer el mínimo ... Máx. En cualquier caso, supondremos que siempre tenemos un intervalo cerrado [Min, Max] para el rango de índice [L..R] que estamos buscando actualmente, e inicialmente esto es O (N). Estamos buscando la clave K y queremos indexar I para que

[IR] / [K-Max] = [LI] / [Min-K] = [LR] / [Min-Max] por ejemplo I = [RL] / [Max-Min] * [Max-K] + L.

Redondea para que la partición más pequeña se haga más grande en lugar de más pequeña (para ayudar en el peor de los casos). El error esperado de la media cuadrática absoluta y absoluta es <√ [RL] (basado en un modelo de Poisson / Skellam o Random Walk; consulte Wikipedia). El número esperado de pasos es, por lo tanto, O (loglogN).

El peor de los casos se puede restringir para que sea O (logN) de varias maneras. Primero, podemos decidir qué constante consideramos aceptable, tal vez requiriendo los pasos 1. Continuando con los pasos de loglogN como se indicó anteriormente, y luego utilizando la reducción a la mitad logrará esto para cualquiera de estos c.

Alternativamente, podemos modificar la base estándar b = B = 2 del logaritmo para b> 2. Supongamos que tomamos b = 8, entonces efectivamente c ~ b / B. luego podemos modificar el redondeo de arriba para que en el paso k la partición más grande tenga como máximo N * b ^ -k. Es decir, realice un seguimiento del tamaño esperado si eliminamos 1 / b de cada paso, lo que lleva al peor caso b / 2 lgN. Sin embargo, esto devolverá nuestro caso esperado a O (registro N) ya que solo se nos permite reducir la partición pequeña en 1 / b cada vez. Podemos restaurar la expectativa de O (loglog N) utilizando un simple redondeo de la pequeña partición para los pasos de loglogN antes de aplicar el redondeo restringido. Esto es apropiado porque dentro de una ráfaga que se espera que sea local a un valor particular, la distribución es aproximadamente uniforme (es decir, para cualquier función de distribución suave, por ejemplo, en este caso Skellam, cualquier segmento suficientemente pequeño es aproximadamente lineal con una pendiente dada por su derivada en el centro del segmento).

En cuanto al hash ordenado, pensé que leí esto en Knuth hace décadas, pero no puedo encontrar la referencia. La técnica consiste en empujar en lugar de sondear - (posiblemente binario ponderado) buscar para encontrar el lugar correcto o un hueco, luego empujar a un lado para dejar espacio según sea necesario, y la función hash debe respetar el orden. Este empuje puede envolverse y, por lo tanto, se necesita un segundo paso a través de la tabla para recogerlos a todos. Es útil para rastrear a Min y Max y sus índices (para avanzar o retroceder el listado ordenado comienza en uno y sigue cíclicamente al otro; luego se pueden usar en lugar de 1 y N como corchetes iniciales para la búsqueda anterior, de lo contrario 1 y N se pueden usar como sustitutos).

Si el factor de carga alfa está cerca de 1, entonces se espera la inserción de O (√N) para los artículos de O (√N) esperados, que aún se amortizan a O (1) en promedio. Se espera que este costo disminuya exponencialmente con alfa: creo (según los supuestos de Poisson) que μ ~ σ ~ √ [Nexp (α)].

La búsqueda binaria ponderada proporcionalmente anterior puede usarse para mejorar la sonda inicial.

Tiene un vector de entradas, digamos [x1, x2, ..., xN] , y es consciente del hecho de que la distribución de las consultas se da con probabilidad 1/x , en el vector que tiene. Esto significa que sus consultas se realizarán con esa distribución, es decir, en cada consulta, tomará el elemento xN con mayor probabilidad.

Esto hace que su árbol de búsqueda binario se equilibre teniendo en cuenta sus etiquetas, pero sin imponer ninguna política en la búsqueda. Un posible cambio en esta política sería relajar la restricción de un árbol de búsqueda binaria equilibrada (más pequeño a la izquierda del nodo principal, mayor a la derecha), y elegir realmente los nodos principales como los que tienen mayores probabilidades, y Sus nodos hijos como los dos elementos más probables.

Tenga en cuenta que este no es un árbol de búsqueda binario, ya que no está dividiendo su espacio de búsqueda por dos en cada paso, sino más bien un árbol equilibrado con respecto a la distribución de su patrón de búsqueda. Esto significa que su peor caso de búsqueda puede alcanzar O(N) . Por ejemplo, teniendo v = [10, 20, 30, 40, 50, 60] :

30 / / 20 50 / / / 10 40 60

Que se puede reordenar o rebalancear , usando su función f(x) = 1 / x :

f([10, 20, 30, 40, 50, 60]) = [0.100, 0.050, 0.033, 0.025, 0.020, 0.016] sort(v, f(v)) = [10, 20, 30, 40, 50, 60]

En un nuevo árbol de búsqueda , que se parece a:

10 -------------> the most probable of being taken / / leaving v = [[20, 30], [40, 50, 60]] 20 30 ---------> the most probable of being taken / / leaving v = [[40, 50], [60]] 40 50 -------> the most probable of being taken / leaving v = [[60]] 60

Si busca 10 , solo necesita una comparación, pero si está buscando 60 , realizará comparaciones O(N) , lo que no lo califica como una búsqueda binaria. Como señaló @ Steve314, cuanto más lejos se vaya de un árbol completamente equilibrado, peor será su peor caso de búsqueda.