algorithm - pseint - ¿Dónde se usa la búsqueda binaria en la práctica?
busqueda binaria recursiva (22)
A cada programador se le enseña que la búsqueda binaria es una manera buena y rápida de buscar una lista ordenada de datos. Hay muchos ejemplos de libros de texto sobre el uso de la búsqueda binaria, pero ¿qué ocurre con la programación real: dónde se usa realmente la búsqueda binaria en los programas de la vida real?
¡La búsqueda binaria es una manera buena y rápida!
Antes de la llegada de STL y .NET framework, etc., a menudo podía toparse con situaciones en las que necesitaba desplegar sus propias clases de colección personalizadas. Siempre que una matriz ordenada sea un lugar factible de almacenamiento de los datos, la búsqueda binaria sería la forma de ubicar las entradas en esa matriz.
Estoy bastante seguro de que la búsqueda binaria también se usa ampliamente hoy en día, aunque la biblioteca se encarga de "esconderla" para su comodidad.
Cada programador necesita saber cómo usar la búsqueda binaria cuando se depura.
Cuando tiene un programa y sabe que un error es visible en un punto particular durante la ejecución del programa, puede usar la búsqueda binaria para localizar el lugar donde realmente sucede. Esto puede ser mucho más rápido que un solo paso a través de grandes partes del código.
Entre otros lugares, tengo un intérprete con una tabla de nombres de comando y un puntero a la función para interpretar ese comando. Hay alrededor de 60 comandos. No sería increíblemente oneroso usar una búsqueda lineal, pero utilizo una búsqueda binaria.
Implementé búsquedas binarias en implementaciones BTree.
Los algoritmos de búsqueda BTree se usaron para encontrar el siguiente bloque de nodos para leer, pero dentro del bloque 4K (que contenía varias claves basadas en el tamaño de la clave), se utilizó la búsqueda binaria para encontrar el número de registro (para un nodo hoja) ) o el siguiente bloque (para un nodo no hoja).
Cegadoramente rápido en comparación con la búsqueda secuencial, ya que, como los árboles binarios equilibrados, elimina la mitad del espacio de búsqueda restante con cada control.
La búsqueda binaria se puede utilizar para acceder a los datos ordenados rápidamente cuando el espacio de memoria es ajustado . Supongamos que desea almacenar un conjunto de 100.000 enteros de 32 bits en una estructura de datos ordenados buscables, pero no va a cambiar el conjunto a menudo. Puede almacenar trivialmente los enteros en una matriz ordenada de 400,000 bytes, y puede usar la búsqueda binaria para acceder rápidamente. Pero si los pones, por ejemplo, en un árbol B, árbol RB o cualquier estructura de datos "más dinámica", comienzas a incurrir en gastos generales de memoria. Para ilustrar, el almacenamiento de los enteros en cualquier tipo de árbol donde haya dejado punteros secundarios derecho e infantil le haría consumir al menos 1.200.000 bytes de memoria (suponiendo una arquitectura de memoria de 32 bits). Claro, hay optimizaciones que puede hacer, pero así es como funciona en general.
Debido a que es muy lento actualizar una matriz ordenada (haciendo inserciones o eliminaciones), la búsqueda binaria no es útil cuando la matriz cambia con frecuencia.
Aquí algunos ejemplos prácticos donde he usado la búsqueda binaria:
- Implementar un "switch () ... case:" construir en una máquina virtual donde las etiquetas de casos son enteros individuales. Si tiene 100 casos, puede encontrar la entrada correcta en 6 a 7 pasos usando la búsqueda binaria, donde la secuencia de ramas condicionales toma un promedio de 50 comparaciones.
- Hacer una búsqueda de subcadenas rápida usando matrices de sufijos, que contienen todos los sufijos del conjunto de cadenas de búsqueda en ordenamiento lexiográfico (quería conservar memoria y mantener la implementación simple)
- Encontrar soluciones numéricas a una ecuación (cuando eres perezoso y no te importa implementar el método de Newton)
La búsqueda binaria se usa en todas partes . Tome cualquier colección ordenada de cualquier biblioteca de idiomas (Java, .NET, C ++ STL, etc.) y todos usarán (o tendrán la opción de usar) búsqueda binaria para encontrar valores. Si bien es cierto que debe implementarlo con poca frecuencia, aún debe comprender los principios que lo respaldan para aprovecharlo.
Los programas de prueba de semiconductores utilizados para medir la temporización digital o los niveles analógicos hacen un uso extensivo de la búsqueda binaria. Los equipos de prueba automática (ATE) de Advantest, Teradyne, Verigy y similares se pueden considerar blasters de mesa de verdad, aplicando lógica de entrada y verificando estados de salida de una parte digital.
Piense en una puerta simple, con la lógica de entrada cambiando en el tiempo = 0 de cada ciclo, y la transición de X ns después de que la lógica de entrada cambie. Si enciende la salida antes de T = X, la lógica no coincide con el valor esperado. Strobe más tarde que el tiempo T = X, y la lógica no coincide con el valor esperado. La búsqueda binaria se usa para encontrar el umbral entre el último valor que la lógica no concuerda, y la parte más temprana donde lo hace. (Un sistema Teradyne FLEX resuelve el tiempo hasta una resolución de 39pS, otros comprobadores son comparables). Esa es una manera simple de medir el tiempo de transición. La misma técnica se puede usar para resolver el tiempo de configuración, el tiempo de mantenimiento, los niveles de suministro de energía operable, el suministro de energía frente a la demora, etc.
Cualquier tipo de microprocesador, memoria, FPGA, lógica y muchos circuitos de señales mixtas analógicas usan búsqueda binaria en prueba y caracterización.
- Mike
Si tiene un conjunto de elementos para encontrar en una matriz, puede buscarlos linealmente u ordenar la matriz y luego usar la búsqueda binaria con el mismo predicado de comparación. Este último es mucho más rápido.
Todavía lo usamos mucho en nuestro código para buscar miles de ACLS muchas miles de veces por segundo. Es útil porque las listas de control de acceso (ACL) son estáticas una vez que ingresan desde el archivo, y podemos sufrir el gasto de aumentar la matriz a medida que la agreguemos durante el arranque. Increíblemente rápido una vez que también funciona.
Cuando puede buscar una matriz de 255 elementos en un máximo de 7 comparaciones / saltos (511 en 8, 1023 en 9, etc.), puede ver que la búsqueda binaria es lo más rápida que puede obtener.
Un ejemplo es el conjunto stl. La estructura de datos subyacente es un árbol de búsqueda binaria equilibrada que admite búsqueda, inserción y eliminación en O (log n) debido a la búsqueda binaria.
Otro ejemplo es un algoritmo de división de enteros que se ejecuta en tiempo de registro.
Una vez lo implementé (sin siquiera saber que esto era de hecho una búsqueda binaria) para un control de GUI que muestra datos bidimensionales en un gráfico. Al hacer clic con el mouse, debe establecer el cursor de datos en el punto con el valor de x más cercano. Cuando se trata de un gran número de puntos (varios 1000, esto era mucho cuando x86 solo comenzaba a tener una frecuencia de CPU de más de 100 MHz), esto no se podía usar realmente de forma interactiva: hacía una búsqueda lineal desde el principio. Después de pensar un poco, se me ocurrió que podía abordar esto en una división y conquistar la moda. Me tomó un tiempo para que funcione en todos los casos extremos.
Fue solo un tiempo después cuando supe que este es un algoritmo de CS fundamental ...
Encontrar raíces de una ecuación es probablemente una de esas cosas fáciles de hacer con un algoritmo muy fácil como la búsqueda binaria.
Los usos de Delphi pueden disfrutar de la búsqueda binaria mientras se busca una cadena en TStringList ordenada.
Creo que .NET SortedDictionary utiliza un árbol binario detrás de la escena (al igual que el mapa STL) ... por lo que se utiliza una búsqueda binaria para acceder a los elementos en SortedDictionary
Tenía un programa que iteraba a través de una colección para realizar algunos cálculos. Pensé que esto era ineficiente, así que ordené la colección y luego usé una única búsqueda binaria para encontrar un elemento de interés. Devolví este artículo y sus vecinos correspondientes. Tenía en efecto filtrado la colección.
Hacer esto fue en realidad más lento que iterar toda la colección y pescar los artículos que combinan.
Seguí agregando elementos a la colección sabiendo que el rendimiento de clasificación y búsqueda eventualmente se pondría al día con la iteración. Tomó una colección de aproximadamente 600 objetos hasta que la velocidad fue idéntica. 1000 objetos tuvieron un claro beneficio de rendimiento.
También consideraría el tipo de datos con los que está trabajando, los duplicados y la propagación. Esto tendrá un efecto en la clasificación y búsqueda.
Mi respuesta es probar ambos métodos y cronometrarlos.
El método list.sort() Python usa Timsort, que (AFAIK) utiliza la búsqueda binaria para ubicar las posiciones de los elementos.
Bueno, la búsqueda binaria ahora se usa en el 99% de los juegos y aplicaciones 3D. El espacio se divide en una estructura de árbol y se utiliza una búsqueda binaria para recuperar qué subdivisiones mostrar según una posición 3D y una cámara.
Uno de sus primeros escaparates fue Doom. Los árboles binarios y la búsqueda asociada mejoraron la representación.
Es la base de hg bisect
La búsqueda binaria ofrece una característica que muchas implementaciones de mapas / diccionarios ya no tienen: encontrar coincidencias no exactas.
Por ejemplo, utilicé la búsqueda binaria para implementar el geoetiquetado de fotos basadas en registros de GPS: coloque todos los puntos de ruta GPS en una matriz ordenada por marca de tiempo y use la búsqueda binaria para identificar el waypoint más cercano a la marca de tiempo de cada foto.
La ordenación binaria es útil para ajustar las fuentes al tamaño del texto con una dimensión constante de cuadro de texto
La búsqueda binaria se puede usar para depurar con Git. Se llama git bisect .
Respondiendo a tu pregunta con un ejemplo práctico.
En el lenguaje de programación R hay un paquete data.table . Se conoce desde C, sintaxis corta, extensión de alto rendimiento para la transformación de datos. Utiliza la búsqueda binaria. Incluso sin búsqueda binaria, se escala mejor que la competencia.
Puede encontrar benchmark vs python pandas y vs R dplyr en la agrupación wiki del proyecto 2E9 - datos de orden aleatorios.
También hay buenas bases de datos comparativas frente a bigdata benchm-databases .
En la versión data.table reciente (1.9.6), la búsqueda binaria se extendió y ahora se puede usar como índice en cualquier columna atómica.
Acabo de encontrar un buen resumen con el que estoy totalmente de acuerdo, ver .
Cualquiera que haga comparaciones R debe usar data.table en lugar de data.frame. Más aún para los puntos de referencia. data.table es la mejor estructura de datos / lenguaje de consulta que he encontrado en mi carrera. Está marcando el camino en el mundo de The R, y en mi camino, en todos los idiomas centrados en datos.
Entonces, sí, se está utilizando la búsqueda binaria y el mundo está mucho mejor gracias a ella.