Crear una tabla de búsqueda en C++

1. Crear una tabla de búsqueda en C++
2. Cree una tabla de búsqueda que muestre redundancia cíclica para valores de 32 bits en C++
3. Crear una tabla de búsqueda preiniciada en C++
4. Cree una tabla de búsqueda para encontrar todos los valores posibles dentro de un índice dado en C++
5. Conclusión

Los sistemas integrados son dispositivos de hardware simples fabricados con CPU asequibles que se entregan a los proveedores a precios atractivos. Este recorte de precios tiene el costo de una potencia de procesamiento limitada y, a menudo, estos dispositivos corren el riesgo de desbordarse.

Para evitar tales riesgos, podemos usar tablas de búsqueda. Las tablas de búsqueda son matrices que almacenan datos para algo, lo que requiere mucha potencia de procesamiento si se realiza en tiempo real.

La tabla de búsqueda proporciona una solución rentable a estos problemas.

Este artículo explica los conceptos de una tabla de búsqueda, su implementación, los inconvenientes y algunos bloques de código para facilitar su comprensión.

Crear una tabla de búsqueda en C++

En este artículo, las tablas de búsqueda se crean de tres maneras diferentes:

1. Una tabla de búsqueda que el programa crea por sí mismo.
2. Una tabla de búsqueda manual se inicializa al inicio del programa, que el programa utiliza más adelante como referencia.
3. Un programa que declara una tabla de búsqueda creada con un conjunto de variables para encontrar todos los valores posibles dentro de un índice dado.

Los tres casos mencionados anteriormente son todas las formas posibles en que se usa una tabla de búsqueda en escenarios de la vida real.

Cree una tabla de búsqueda que muestre redundancia cíclica para valores de 32 bits en C++

Este ejemplo crea una tabla de búsqueda que verifica la redundancia cíclica para los cálculos de CRC de 32 bits. CRC también se conoce como PEC en algunas convenciones, pero ambos significan lo mismo.

Los siguientes bloques de código crean una tabla de búsqueda que imprime una tabla de cálculos de CRC para 256 bits de datos.

Importar paquetes

El programa utiliza dos paquetes de importación, a saber:

1. iostream - para operaciones de entrada/salida
2. iomanip - para alterar el resultado final del programa

Funciones de método para crear una tabla de búsqueda en C++

El primer método, make_pec_table, toma como parámetro el array table_pec. Este método trata con 8 bits de datos, expandiéndose aún más a 32 bits.

Un bucle do-while busca el valor mayor entre rem y 1 y lo eleva a la potencia de la variable value_of_polynomial. El bucle do-while se ejecuta hasta que el valor de x permanece distinto de cero.

El método pec_gen crea una variable sin signo pec, que almacena la tabla pec, donde los valores dentro de la matriz table_pec se insertan aquí usando un bucle for.

Dentro de la función principal, se crea nuevamente una matriz local table_pec de tamaño 256 bits. Luego se llama al método make_pec_table mientras se pasa el array table_pec como parámetro.

Finalmente, se imprime el resultado para todos los 256 bits de datos.

#include <iomanip>
#include <iostream>

void make_pec_table(unsigned long table_pec[]) {
  unsigned long value_of_polynomial = 0xEDB8320;
  unsigned long rem;
  unsigned char x = 0;
  do {
    // proceed  with data byte
    rem = x;
    for (unsigned long bit = 8; bit > 0; --bit) {
      if (rem & 1)
        rem = (rem >> 1) ^ value_of_polynomial;
      else
        rem = (rem >> 1);
    }
    table_pec[(size_t)x] = rem;
  } while (0 != ++x);
}

unsigned long pec_gen(unsigned char *m, size_t n, unsigned long table_pec[]) {
  unsigned long pec = 0xfffffffful;
  size_t i;
  for (i = 0; i < n; i++) pec = table_pec[*m++ ^ (pec & 0xff)] ^ (pec >> 8);
  return (~pec);
}

int main() {
  unsigned long table_pec[256];
  make_pec_table(table_pec);
  // display PEC table
  for (size_t i = 0; i < 256; i++) {
    std::cout << std::setfill('0') << std::setw(8) << std::hex << table_pec[i];
    if (i % 4 == 3)
      std::cout << std::endl;
    else
      std::cout << ", ";
  }
  return 0;
}

Crear una tabla de búsqueda preiniciada en C++

El siguiente ejemplo es un bloque de código del algoritmo de cifrado SHA256. El programa crea dos conjuntos de registros (que no son más que tablas de búsqueda creadas manualmente para que el programa las tome como referencia).

El primer conjunto de registros son los que se utilizan para almacenar valores hexadecimales de los primeros 64 dígitos numéricos como claves hash. Los valores de estas claves se almacenan dentro de la variable hash_keys, que se encuentran dentro de la clase constructora hash_functions.

const unsigned int hash_functions::hash_keys[64] = {
    0x428a2f98, 0x71374491, 0xb5c0fbcf, 0xe9b5dba5, 0x3956c25b,
    0x59f111f1, 0x923f82a4, 0xab1c5ed5, 0xd807aa98, 0x12835b01,
    0x243185be, 0x550c7dc3, .....}

De forma predeterminada, la lectura de datos es el único propósito de las tablas de búsqueda. Si se puede modificar una tabla de búsqueda, eso indica un error.

La matriz se declara inicialmente con const para evitar tal escenario.

Como la matriz contiene valores hexadecimales de los primeros 64 números naturales, no necesita ningún bit adicional para los signos. Por lo tanto, la matriz se declara sin firmar.

Si una tabla de búsqueda tiene valores negativos, la matriz debe declararse con un tipo de datos firmado.

Otro conjunto de registros de estado inicializados almacena un conjunto similar de valores hexadecimales para los primeros 8 enteros.

void hash_functions::stateregister() {
  s_r[0] = 0x6a09e667;
  s_r[1] = 0xbb67ae85;
  s_r[2] = 0x3c6ef372;
  .....
}

Estas dos tablas de búsqueda se inicializan previamente en el programa para reducir la complejidad del tiempo y aumentar la velocidad de procesamiento.

Es porque la conversión SHA256 es, en sí misma, un proceso largo para la CPU. Si está programado para calcular esos valores durante el tiempo de ejecución, aumentará drásticamente la complejidad del tiempo del programa.

Una vez que se inicializa una tabla de búsqueda, se puede usar llamándola como cualquier otra variable.

Una razón para agregar la tabla de búsqueda dentro de un constructor separado y no dentro de otro método es que las tablas de búsqueda ocupan un gran espacio en disco. Por lo tanto, debe declararse en el ámbito global o como una entidad estática.

Supongamos que una tabla de búsqueda se inicializa dentro de un método como una entidad local. En ese caso, el proceso de inicialización se repite cada vez que se llama al método.

Es una mala práctica insertar un método con una gran inicialización en medio de la ejecución del programa.

Tener tablas de búsqueda en el inicio o en el ámbito global es ventajoso y rentable.

for (int n = 0; n < 64; n++) {
  t1 = buffer[7] + hash_keys[n] + w[n];
}
for (n = 0; n < 8; n++) {
  s_r[n] += buffer[n];
}

Aquí debe tenerse en cuenta que la aplicación pierde mucho tiempo y potencia de procesamiento durante la fase de inicialización cuando se leen estos valores. Una vez que ocurre la inicialización, el programa requiere una potencia de procesamiento mínima para verificar entre valores.

Los sistemas informáticos de generaciones anteriores y los dispositivos electrónicos solían tener muy poca memoria y espacio en disco, lo que sigue siendo motivo de preocupación. Como resultado, el uso de una tabla de búsqueda en el firmware de esos dispositivos puede ocupar mucho espacio en el disco.

La variable que contiene la tabla de búsqueda se designó como const o una variable constante en el ejemplo anterior. Se hizo para indicarle al compilador que evite escribir algo en la tabla de búsqueda.

Aunque se define const, la aplicación a menudo fuerza la tabla de búsqueda en la RAM. Debido a que es un recurso tan valioso, los programadores necesitan codificar el término flash al declarar variables.

flash es una forma de memoria más lenta que reduce la velocidad de la aplicación pero ahorra RAM valiosa.

Cree una tabla de búsqueda para encontrar todos los valores posibles dentro de un índice dado en C++

Este ejemplo particular muestra los valores de la función de onda sinusoidal para un punto y grado dados.

Importar paquetes

Este ejemplo requiere tres paquetes de importación:

1. iostream
2. math.h
3. conio.h

El paquete iostream tiene sus implicaciones para las operaciones de entrada-salida. El paquete math.h se utiliza para invocar funciones matemáticas y funciones trigonométricas.

El paquete conio.h se utiliza para funciones del compilador como borrar pantalla, obtener, etc.

Inicializar variables para crear una tabla de búsqueda en C++

Este programa utiliza 3 variables de punto flotante: la variable array de tamaño 255, resultado y array_elements. Todas las demás variables son de tipo entero (PI se define como 3.1415…..).

La variable del array arr se declara con 255 tamaños. En otro bucle, la variable sine_table almacena los valores de seno para los picos dados.

Por último, la variable sine_table se imprime dentro del mismo bucle.

#include <conio.h>
#include <math.h>

#include <iostream>

#define PI 3.14159265

float arr[255], final_result, array_elements;
int index, Deg, sine_table;

int main(void) {
  printf("Enter the degree\n");
  scanf("%d", &Deg);

  printf("Enter the index of total point\n");
  scanf("%d", &index);

  printf("Enter the max range\n");
  int r;
  scanf("%d", &r);

  final_result = Deg / index;

  for (int i = 0; i < index; i++) {
    int sum;
    sum += final_result;
    arr[i] = sum;
  }

  for (int n = 0; n < index; n++) {
    array_elements = (arr[n]);
    sine_table = sin(array_elements * PI / 180) * r;
    printf("%d\t", sine_table);
  }
  getch();
  return (0);
}

Conclusión

Esperamos que haya comprendido todos los conceptos de la creación de tablas de búsqueda después de leer este artículo. Los ejemplos presentados aquí brindan una descripción general completa de cómo se crean y usan las tablas de búsqueda dentro de un programa.

Después de leer este artículo, se espera que haya captado las ventajas y desventajas de utilizar tablas de búsqueda en un programa.