c++ - flujo - busqueda binaria javascript
Más rápido que la búsqueda binaria para la lista ordenada (10)
¿Hay un algoritmo que sea más rápido que la búsqueda binaria para buscar en los valores ordenados de la matriz?
en mi caso, tengo valores ordenados (podrían ser valores de cualquier tipo) en una matriz A , necesito devolver n si el valor que estaba buscando está en el rango de A[n] and A[n+1]
¿Qué pasa con el siguiente algo? se llama búsqueda exponencial y es una de las variaciones de la búsqueda binaria. http://en.m.wikipedia.org/wiki/Exponential_search
Buscando el elemento k en la matriz ordenada A de tamaño n. Busque A [2 ^ i] para i = 0, 1, 2, ... hasta ir más allá de la posición de k en A. luego haga una búsqueda binaria en la parte de la matriz a la izquierda (más pequeña) que yo.
int exponential_search(int A[], int key)
{
// lower and upper bound for binary search
int lower_bound = 0;
int upper_bound = 1;
// calculate lower and upper bound
while (A[upper_bound] < key) {
lower_bound = upper_bound;
upper_bound = upper_bound * 2;
}
return binary_search(A, key, lower_bound, upper_bound);
}
Este algo se ejecutará en O (log idx) donde idx es el índice de k en A. (ambos aspectos están en log idx). En el peor de los casos, el algo está en O (log idx), si k está entre los elementos más grandes de A o más grande que cualquier elemento de A. La constante multiplicativa es más grande que para la búsqueda binaria pero el algoritmo correría más rápido por muy grande arrays y al buscar datos que están hacia el comienzo de la matriz.
Me gustaría tener una idea del tamaño mínimo n en el que este algoritmo es preferible a la búsqueda binaria, pero no sé.
Antes que nada, mida antes de hacer la optimización.
¿Realmente necesita optimizar esa búsqueda?
Si es así, entonces, en segundo lugar, piense primero en la complejidad algorítmica. Por ejemplo, ¿puedes usar un árbol (como un std::map , por ejemplo) en lugar de una matriz? Si es así, depende de la frecuencia relativa de las inserciones / eliminaciones frente a las búsquedas, pero la premisa de tener una matriz ordenada a mano indica que las búsquedas son frecuentes en comparación con los cambios en el conjunto de datos, por lo que tendría sentido hacer un poco de trabajo adicional para inserciones / eliminaciones, lo que hace que cada búsqueda sea mucho más rápida, a saber, el tiempo logarítmico.
Si encuentra que efectivamente los tiempos de búsqueda son un cuello de botella que necesita direccionamiento, y no, no es posible cambiar la representación de datos, y la lista es corta, entonces una búsqueda lineal generalmente será más rápida porque hace menos trabajo por comparación.
De lo contrario, si la lista es más larga y no se conoce ni asume ninguna distribución particular de valores, y los valores no pueden tratarse como numéricos, y el consumo de memoria debe ser constante (excluyendo la construcción de una tabla hash, por ejemplo), entonces búsqueda binaria produce 1 bit de información por comparación y es probablemente lo mejor que puede hacer para la primera búsqueda.
Saludos y hth.
Aunque en el caso general no se puede hacer mejor que O (log N), al menos se puede optimizar, reduciendo significativamente la constante de proporcionalidad frente a O (log N).
Si tiene que realizar búsquedas múltiples en la misma matriz, estas se pueden vectorizar usando extensiones SIMD, reduciendo aún más el costo de cálculo.
En particular, si se trata de matrices de números de coma flotante que satisfacen ciertas propiedades, entonces hay formas de construir un índice especial que luego permite buscar la matriz en O (1).
Todos los aspectos anteriores se discuten con los resultados de las pruebas en: Cannizzo, 2015, alternativa rápida y vectorializable a la búsqueda binaria en O (1) Aplicable a un amplio dominio de matrices ordenadas de números de coma flotantes El papel viene con el código fuente en github .
En la búsqueda binaria divide la lista en dos "sublistas" y solo busca en la sublista que pueda contener el valor. Dependiendo de qué tan grande sea su matriz, podría ver una aceleración si divide la matriz en más de dos empalmes.
Puede determinar en qué región de la matriz debe buscar, manteniendo un índice, que busca primero. Como en una guía telefónica de una gran ciudad, donde se puede ver desde el exterior, donde debe comenzar a buscar. (Tengo problemas para expresar mi idea en el texto, y todavía no encontré un enlace en inglés que lo explique mejor).
Puede hacer mejor que O (log n) si los valores son enteros, en cuyo caso el mejor tiempo de ejecución en el peor de los casos, en términos de n, es O (sqrt (log n)). De lo contrario, no hay forma de vencer a O (log n) a menos que haya patrones en la secuencia de entrada. Hay dos enfoques utilizados para vencer a O (log n) en el caso de los enteros.
En primer lugar, puede utilizar árboles y-fast que funcionan almacenando en una tabla hash todos los prefijos para los que está almacenando al menos un entero con ese prefijo. Esto le permite realizar una búsqueda binaria para encontrar la longitud del prefijo de coincidencia más largo. Esto le permite encontrar el sucesor de un elemento para el que está buscando en el tiempo O (log w) donde w es la cantidad de bits en una palabra. Sin embargo, hay que trabajar con algunos detalles para que esto funcione y use solo espacio lineal, pero no están tan mal (ver el enlace a continuación).
En segundo lugar, puede utilizar árboles de fusión, que utilizan trucos de bits para permitirle realizar comparaciones w ^ O (1) en un número constante de instrucciones, obteniendo un tiempo de ejecución de O (log n / log w).
La compensación óptima entre estas dos estructuras de datos ocurre cuando log w = sqrt (log n), dando un tiempo de ejecución de O (sqrt (log n)).
Para más detalles sobre lo anterior, vea las lecciones 12 y 13 del curso de Erik Demaine: http://courses.csail.mit.edu/6.851/spring07/lec.html
Si los valores de la lista están distribuidos uniformemente, puede probar una división ponderada en lugar de una división binaria, por ejemplo, si el valor deseado es un tercio del camino desde el límite inferior actual hasta el valor actual, entonces puede probar el elemento que está también un tercio del camino. Esto podría sufrir mal en las listas donde los valores están agrupados.
Si tiene una gran cantidad de números para encontrar, y por algún azar también están clasificados, puede hacerlo en O (n + m) donde m es la cantidad de números que debe encontrar. Básicamente es el algoritmo de fusión típico, con una ligera modificación para registrar qué valor se insertaría cada número marcado antes, si se insertara en la matriz.
Siempre puedes intercambiar el espacio ... y el tiempo de otras operaciones. Suponiendo que todos sus elementos son bits p de tamaño constante, puede crear una matriz masiva que almacene, para cada valor posible que pueda buscar, el índice del siguiente valor más grande actualmente almacenado. Esta matriz necesita ser 2 ^ p * lg (n) bits, donde n es el número de valores almacenados. Cada inserción o eliminación es O (2 ^ p) pero típicamente alrededor de 2 ^ p / n, porque debe actualizar todos esos índices.
¡Pero tu búsqueda ahora es O (1)!
OK, OK, no es realmente práctico. Pero dividir la entrada en bloques de una manera similar posiblemente podría reducir la constante en frente de su registro. Posiblemente.
Si y no. Sí, hay búsquedas que son más rápidas, en promedio, que una búsqueda de bisección. Pero creo que todavía son O (lg N), solo que con una constante menor.
Desea minimizar el tiempo necesario para encontrar su elemento. En general, es deseable utilizar menos pasos, y una forma de abordar esto es maximizar la cantidad esperada de elementos que se eliminarán en cada paso. Con la bisección, siempre se elimina exactamente la mitad de los elementos. Puedes hacerlo mejor si sabes algo sobre la distribución de los elementos. Sin embargo, el algoritmo para elegir el elemento de partición generalmente es más complicado que elegir el punto medio, y esta complejidad adicional puede abrumar cualquier ahorro de tiempo que se espera obtener al usar menos pasos.
Realmente, en un problema como este, es mejor atacar los efectos de segundo orden, como el lugar de la memoria caché, que el algoritmo de búsqueda. Por ejemplo, al realizar una búsqueda binaria repetida, los mismos pocos elementos (primer, segundo y tercer cuartil) se utilizan MUY frecuentemente, por lo que ponerlos en una sola línea de caché podría ser muy superior al acceso aleatorio a la lista.
Dividir cada nivel en decir 4 u 8 secciones iguales (en lugar de 2) y hacer una búsqueda lineal a través de ellos también podría ser más rápido que la búsqueda de bisección, porque una búsqueda lineal no requiere calcular la partición y también tiene menos dependencias de datos que pueden causa puestos de caché.
Pero todos estos son todavía O (lg N).
Siempre puede ponerlos en una tabla hash, luego la búsqueda será O (1). Sin embargo, requerirá mucha memoria y si continúa agregando elementos, es posible que la tabla hash deba ser reubicada. Re-bucketing es O (n) pero se amortizará a O (1). En esencia, depende de si puede pagar ese espacio y el potencial de caché falla.
Una posibilidad es tratarlo como encontrar las raíces de una función. Básicamente, encontrar:
a[i] <= i <= a[i + 1]
Es equivalente a:
a[i] - i <= 0 <= a[i + 1] - i
Entonces podrías probar algo como el método de Newton y demás. Este tipo de algoritmos frecuentemente convergen más rápido que una búsqueda binaria cuando funcionan, pero no conozco uno que garantice converger para todas las entradas.