Tabla de búsqueda

La versión actual de la página aún no ha sido revisada por colaboradores experimentados y puede diferir significativamente de la versión revisada el 21 de mayo de 2018; las comprobaciones requieren 5 ediciones .

Una tabla de búsqueda es una  estructura de datos que almacena los resultados de la interpolación de una función . Suele ser una matriz o una matriz asociativa que se utiliza para reemplazar los cálculos con una simple operación de búsqueda . El aumento de la velocidad puede ser significativo, ya que recuperar datos de la memoria suele ser más rápido que realizar cálculos que consumen mucho tiempo.

Un ejemplo clásico del uso de tablas de consulta es el cálculo de los valores de funciones trigonométricas , por ejemplo, el seno . Su cálculo directo puede ralentizar mucho la aplicación. Para evitar esto, la aplicación calcula previamente una cierta cantidad de valores de seno en el primer inicio, por ejemplo, para todos los grados enteros. Luego, cuando el programa necesita el valor del seno, usa la tabla de búsqueda para obtener el valor aproximado del seno de la memoria, en lugar de calcular su valor (por ejemplo, usando series ). Las tablas de búsqueda también se utilizan en los coprocesadores matemáticos ; un error en la tabla de búsqueda en los procesadores Pentium de Intel condujo al infame error que redujo la precisión de la operación de división.

Mucho antes de que las tablas de búsqueda estuvieran en la programación, la gente ya las usaba para facilitar los cálculos manuales. Especialmente comunes fueron las tablas de logaritmos , así como las funciones trigonométricas y estadísticas.

Existe una solución intermedia cuando se usa una tabla de búsqueda en combinación con cálculos simples: la interpolación . Esto le permite encontrar valores con mayor precisión entre dos puntos precalculados. Los costos de tiempo aumentarán ligeramente, pero a cambio, se proporcionará una mayor precisión en los cálculos. Además, esta técnica se puede utilizar para reducir el tamaño de la tabla de búsqueda sin pérdida de precisión.

Las tablas de búsqueda también se usan ampliamente en el procesamiento de imágenes por computadora (en esta área, las tablas correspondientes generalmente se denominan "paletas").

Es importante señalar que el uso de tablas de consulta en aquellas tareas en las que son ineficientes conduce a una disminución de la velocidad de trabajo. Esto no solo se debe a que recuperar datos de la memoria es más lento que calcularlos, sino también a que la tabla de búsqueda puede llenar la memoria y el caché . Si la tabla es grande, lo más probable es que cada acceso a ella resulte en una pérdida de caché . En algunos lenguajes de programación (como Java ), acceder a la tabla de búsqueda puede ser incluso más "caro" debido a la verificación de límites obligatoria, que incluye comparaciones adicionales y bifurcaciones para cada operación de búsqueda.

Hay dos limitaciones fundamentales para crear tablas de búsqueda. El primero es la cantidad total de memoria disponible: la tabla debe caber en el espacio disponible, aunque puede realizar la tabla de búsqueda en el disco, lo que aumenta el tiempo de la operación de búsqueda. Otra limitación es el tiempo que lleva crear una tabla de búsqueda en la primera ejecución; aunque esta operación generalmente solo se necesita una vez, puede llevar demasiado tiempo, lo que hace que el uso de tablas de búsqueda sea una solución inapropiada.

Calculando el seno

La mayoría de las computadoras solo admiten aritmética básica y no pueden calcular el valor del seno directamente. En cambio, para calcular el valor del seno con un alto grado de precisión, utilizan el método CORDIC o la serie de Taylor :

Sin embargo, dicho cálculo puede llevar mucho tiempo, especialmente en un procesador lento, y hay muchas aplicaciones, como gráficos por computadora , que necesitan calcular el valor de miles de senos cada segundo. Una solución común es precalcular una tabla de valores de seno, y luego encontrar el seno de un número se reduce a elegir el argumento más cercano a este número de la tabla (el valor de la función correspondiente estará cerca del valor correcto, porque el seno es una función continua y acotada). Por ejemplo:

arreglo real sine_table[-1000..1000] para x de -1000 a 1000 tabla_seno[x] := seno(pi * x / 1000) función lookup_sine(x) devuelve sine_table[round(1000 * x / pi)]

La tabla requiere mucha memoria; por ejemplo, si se utilizan números de punto flotante de precisión doble, se necesitarán 16 000 bytes . Puede usar menos puntos, pero luego la precisión disminuirá. Una buena práctica en tal caso es una aproximación lineal .

Aquí hay un ejemplo de una aproximación lineal:

función buscar_seno(x) x1 := suelo(x*1000/pi) y1 := tabla_seno[x1] y2 := tabla_seno[x1+1] devuelve y1 + (y2-y1)*(x/1000/pi-x1)

Al usar la interpolación, a menudo es beneficioso usar una distribución desigual de datos: en aquellos lugares donde la función es más cercana a una línea recta, tome pocos puntos para calcular la función, pero si la curvatura de la función es grande, tome más puntos. de este rango para que la aproximación se parezca más a una curva real (ver . también Interpolación ).

Ejemplos

Ejemplo de tabla de senos (en lenguaje de programación C ):

// tabla de senos de 8 bits const sin signo char sinetable [ 256 ] = { 128 , 131 , 134 , 137 , 140 , 143 , 146 , 149 , 152 , 156 , 159 , 162 , 165 , 168 , 171 , 174 , 176 , 179 , 182 , 185 , 188 , 191 , 193 , 196 , 199 , 201 , 204 , 206 , 209 , 211 , 213 , 216 , 218 , 220 , 222 , 224 , 226 , 228 , 230 , 232 , 234 , 236 , 237 , 239 , 240 , 242 , 243 , 245 , 246 , 247 , 248 , 249 , 250 , 251 , 252 , 252 , 253 , 254 , 254 , 255 , 255 , 255 , 255 , 255 , 255 , 255 , 255 , 255 , 255 , 255 , 254 , 254 , 253 , 252 , 252 , 251 , 250 , 249 , 248 , 247 , 246 , 245 , 243 , 242 , 240 , 239 , 237 , 236 , 234 , 232 , 230 , 228 , 226 , 224 , 222 , 220 , 218 , 216 , 213 , 211 , 209 , 206 , 204 , 201 , 199 , 196 , 193 , 191 , 188 , 185 , 182 , 179 , 176 , 174 , 171 , 168 , 165 , 162 , 159 , 156 , 152 , 149 , 146 , 143 , 140 , 137 , 134 , 131 , 128 , 124 , 121 , 118 , 115 , 112 , 109 , 106 , 103 , 99 , 96 , 93 , 90 , 87 , 84 , 81 , 79 , 76 , 73 , 70 , 67 , 64 , 62 , 5 , 5 _ 54 , 51 , 49 , 46 , 44 , 42 , 39 , 37 , 35 , 33 , 31 , 29 , 27 , 25 , 23 , 21 , 19 , 18 , 16 , 15 , 13 , 12 , 10 , 9 , 8 , 7 , 6 , 5 , 4 , 3 , 3 , 2 , 1 , 1 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 1 , 1 , 2 , 3 , 3 , 4 , 5 , 6 , 7 , 8 , 9 , 10 , 12 , 13 , 15 , 16 , 18 , 19 , 21 , 23 , 25 , 27 , 29 , 31 , 33 , 35 , 37 , 39 , 42 , 44 , 46 , 49 , 51 , 54 , 56 , 59 , 62 , 64 , 67 , 70 , 73 , 76 , 79 , 81 , 84 , 87 , 90 , 93 , 96 , 99 , 103 , 106 , 109 , 115 , 1 _ 118 , 121 , 124 };

En este caso, los valores de seno de [-1;1] se reflejan en el rango de enteros desde el mínimo 0 hasta el máximo 255, el cero corresponde a 128. En la gran mayoría de las CPU, las operaciones con números enteros son mucho más rápidas que con punto flotante.