¿Existe un algoritmo que sea más rápido que la búsqueda binaria para buscar en los valores ordenados de la matriz?Más rápido que la búsqueda binaria para la lista ordenada
en mi caso, tengo un valores ordenados (podría ser cualquier valor de tipo) en una matriz A, que necesitan volver n si el valor que estaba buscando está dentro del alcance de A[n] and A[n+1]
Puede hacer mejor que O (log n) si los valores son enteros, en cuyo caso el mejor tiempo de ejecución del 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-rápida que funcionan mediante el almacenamiento en una tabla hash todos los prefijos para el que está almacenando al menos un número 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 permitir 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 se produce cuando log w = sqrt (log n), dando un tiempo de ejecución de O (sqrt (log n)).
Para más detalles sobre lo anterior, ver las conferencias 12 y 13, por supuesto, de Erik Demaine: http://courses.csail.mit.edu/6.851/spring07/lec.html
Me gustaría saber más sobre los árboles de fusión. Tal vez estaría dispuesto a explicarlos: http://stackoverflow.com/questions/3878320/understanding-fusion-trees – xscott
@xcott No estoy seguro de que no esté sobre-optimizando a menos que esté escribiendo una biblioteca numérica profesional. –
Sí 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.
Quiere 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 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 causar paradas de caché.
Pero todos estos siguen siendo O (lg N).
En una sola lista ordenada, no. Pero hay búsquedas mucho más rápidas; solo necesita una estructura de datos diferente a una lista ordenada. Un hash sería prácticamente constante en el tiempo de búsqueda, a un costo de mucha más memoria. Un enfoque híbrido podría tomar el enfoque de un diccionario. – tchrist
@tchrist: El problema requiere encontrar el par de elementos que unen firmemente una entrada buscada que no está en absoluto en la lista. Hashing solo encuentra coincidencias exactas. –
Vaya, tienes razón. De alguna manera, solo leo la primera oración, no la segunda. – tchrist
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.
Es posible que su matriz no contenga el valor n, pero contiene dos valores que son n. No es obvio que el hash sea aplicable aquí. – xscott
Oh, me lo perdí.Pero todavía podría hash primero y volver a la búsqueda binaria si el valor no está en la clave establecida. Pero esto es una complejidad añadida. En general, no se puede hacer mejor que la entropía de la distribución de los valores. Si conocía la distribución, puede usar un árbol de Huffman para decidir dónde se divide. – srean
Si los valores de la lista están distribuidos uniformemente, puede probar una división ponderada en lugar de una división binaria, p. Ej. 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 también está a un tercio del camino. Esto podría sufrir mal en las listas donde los valores están agrupados.
Se necesita algo más de optimización. No desea elegir el elemento más cercano al lugar donde adivina la respuesta, quiere probar un punto entre la ubicación adivinada y el centro de la lista, de modo que con p> .5 elimine más de la mitad de la lista. El punto de partición óptimo exacto depende de la distribución de valores en la lista. –
Lo que describes es exactamente búsqueda de interpolación. @Ben una forma eficiente de implementar su sugerencia es a través de un árbol de Huffman – srean
Una posibilidad es tratarlo como encontrar las raíces de una función. Básicamente, la búsqueda de:
a[i] <= i <= a[i + 1]
es equivalente a:
a[i] - i <= 0 <= a[i + 1] - i
Posteriormente, se podría intentar algo así como el método de Newton y así sucesivamente. 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.
El método de Newton requiere una función diferenciable, por lo que primero debería ajustarse una spline de interpolación. Si los valores son uni-modales se comportan bastante bien, de lo contrario podrían divergir y actuar de manera totalmente extraña. – srean
Sí. Puede usar una spline lineal, y la derivada en cualquier punto es: f '(i) = a [i + 1] - a [i] – xscott
Las splines lineales son por tramos lineales, por lo que su derivada no será continua. Uno tiene que ir por al menos cuadrático. Lo cual no es gran cosa. Esto resultará ser similar a [http://en.wikipedia.org/wiki/Interpolation_search] – srean
En búsqueda binaria dividir la lista en dos sublistas "" y sólo buscar en la lista secundaria 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 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).
En primer lugar, medida antes de hacer la optimización.
¿Realmente necesita optimizar esa búsqueda?
Si es así, entonces, en segundo lugar, primero piense en la complejidad algorítmica. P.ej. ¿puedes usar un árbol (por ejemplo, std::map) 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 hay que enfrentar, y no, no hay cambio de la representación de datos es posible, y la lista es corta, entonces una búsqueda lineal generalmente será más rápido, ya que 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 (descarta construir una tabla hash, por ejemplo) , la 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.
Cheers & hth.
Si usted tiene una gran cantidad de números de encontrar, y por alguna casualidad se clasifican También, usted puede hacerlo en O (n + m) donde m es el número de números a 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 puede cambiar 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 su 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.
¿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. Buscar A [2^i] para i = 0, 1, 2, ... hasta ir más allá de la posición de k en A. luego hacer una búsqueda binaria en la parte de la matriz 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 (idx log) donde idx es el índice de k en A. (ambos stpes están en idx log). 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é.
Tenga en cuenta que la multiplicación aquí se puede reemplazar con un simple cambio binario; es realmente barato –
Aunque en el caso general no se puede hacer mejor que O (log N), al menos puede optimizar eso, 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 los costos de computación.
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 resultados de la prueba en: Cannizzo, 2015, Fast and Vectorizable Alternative to Binary Search in O(1) Applicable to a Wide Domain of Sorted Arrays of Floating Point Numbers El documento viene con código fuente en github.
Si tiene un ordenador cuántico puede probar http://en.wikipedia.org/wiki/Grover%27s_algorithm :) –
@ David: La lista está ordenada, sin embargo, por lo que el algoritmo de Grover es peor que la búsqueda de bisección. O (sqrt N)> O (lg N) –
una máquina de estado trabajó un orden de magnitud para mí en datos grandes, pero la complejidad/memoria para construir estados es mucho más grande que la clasificación. – technosaurus