Algoritmos de búsqueda dentro de una memoria EEPROM

[jonathanPIC888]

Buenas noches estimados,

Tengo una consulta técnica para una implementación que tengo que realizar y no logro ver por donde podría empezar.

El problema es el siguiente:

1° - Almacenar 100 enteros de 32 bits en una memoria EEPROM como parte de un sistema de configuración (en proceso y se está avanzando).

2° - Leer cualquiera de esos 100 enteros de 32 bits (Idem anterior).

3° - Algoritmo de búsqueda y comparación, donde nosotros ingresemos en una función el entero a comparar y que la función busque dentro de la EEPROM el entero solicitado.

Dentro del punto 3° es donde tengo mis dudas.

Quiero saber como es la manera más adecuada para implementar esto, teniendo en cuenta como parámetro vital, la velocidad del proceso de comparación.

Alguna recomendación ?

Saludos !

[Nocturno]

¿Esos 100 enteros están ordenados?. Si no lo están la única manera es repasarlos todos uno a uno hasta encontrar el solicitado.

[tsk]

Te sugeriría que te plantes una mejor forma de almacenar esos números, y de especificar mejor los requerimientos, porque no le veo sentido, para un sistema de configuración, buscar un entero y retornar que si lo encontró. ¿Cuál es la finalidad de hacer algo así?

Y es que definiendo bien tus requerimientos podrías usar estructuras de datos que te permitan reducir el espacio de búsqueda de los elementos.

[DominusDRR]

Independientemente del método que uses para buscar información, es mejor que tengas esos 400 bytes en la RAM, es decir al iniciar, leer la EEPROM y pasar esa información a un arreglo en la RAM, luego cualquier cambio que hagas en la RAM (en el arreglo) la pases a la EEPROM.

También deberías agregar comprobación de errores de esos 400 bytes, pueda que al momento que estás escribiendo en la EEPROM, exista un corte de energía y se guarden datos incompletos o corrompidos, entonces cuando inicie todo de nuevo, deberás estar seguro que lo que tienes en esa memoria es correcto.

[jonathanPIC888]

¿Esos 100 enteros están ordenados?. Si no lo están la única manera es repasarlos todos uno a uno hasta encontrar el solicitado.

Como estás Nocturno, no están ordenados. Yo pensé en repasar los 100 hasta encontrar, o no, el solicitado. No se que tan eficiente es hacer eso, la idea es no tardar más de 1-2 segundos en todo el proceso.

Te sugeriría que te plantes una mejor forma de almacenar esos números, y de especificar mejor los requerimientos, porque no le veo sentido, para un sistema de configuración, buscar un entero y retornar que si lo encontró. ¿Cuál es la finalidad de hacer algo así?

Y es que definiendo bien tus requerimientos podrías usar estructuras de datos que te permitan reducir el espacio de búsqueda de los elementos.

No tengo otra manera de almecenar esos números, salvo que lo que haga en una SD, que tengo la posibilidad, pero seguiría en el problema de poder leer ese conjunto de enteros de manera veloz.
La finalidad de lo que estoy haciendo es que hay 100 valores de configuración, que son ID´S de equipos. Necesito comparar un ID que estoy leyendo con un sensor, con alguno de los 100 ID almacenados.

Independientemente del método que uses para buscar información, es mejor que tengas esos 400 bytes en la RAM, es decir al iniciar, leer la EEPROM y pasar esa información a un arreglo en la RAM, luego cualquier cambio que hagas en la RAM (en el arreglo) la pases a la EEPROM.

También deberías agregar comprobación de errores de esos 400 bytes, pueda que al momento que estás escribiendo en la EEPROM, exista un corte de energía y se guarden datos incompletos o corrompidos, entonces cuando inicie todo de nuevo, deberás estar seguro que lo que tienes en esa memoria es correcto.

Esto lo estoy haciendo actualmente y funciona OK. Todos los datos están controlados mediante CRC al almacenarse y leerse. Lo único que no me queda del todo claro como sería el mejor procedimiento para lectura y comparación con un valor fijo.

Saludos y gracias por sus comentarios !

[DominusDRR]

Creo que deberías proporcionar el código de como deseas guardar y leer ese buffer de 400 bytes. De esa manera se puede sugerir algún cambio o corregir algo.

También, compartir el código de búsqueda,

Para guardar, lo básico es cada número de 32, descomponerlo en 4 bytes, e ir guardando esos 4 bytes en la RAM, y así sucesivamente.

Cuando tengas listo esos 400 bytes, calculas el CRC y agregas esos dos bytes (si es CRC de 16 bits) adicionales en el buffer de la RAM, y ahí procedes a guardar en la EEPROM.

La lectura es lo inverso.

Respecto a la búsqueda, una vez que tengas un arreglo en la RAM de 100 posiciones (de números de tipo uint32_t), podrías hacer un simple bucle for o similar para buscar el número deseado.

Al estar trabajando en la RAM, no creo que tome mucho tiempo, en el peor de los casos, el número buscado estará en la última posición.

La pregunta es ¿Por qué necesitas encontrarlo lo más rápido posible? ¿Cuánto tiempo es rápido o lento para ti?

[jonathanPIC888]

Estimado DominusDDR, hoy día quizás esté haciendo algunas pruebas y les comparto lo que tengo hasta ahora. A ver si lo puedo ir resolviendo.

[Robert76]

Hola, como comenta @Nocturno , si no están ordenados los números, habrá que leer uno por uno . Pero no todo está perdido. Se supone que los números los lees de.bytes en bytes, entonces si la primera comparación del octeto, no tiene coincidencia, no tiene sentido seguir comparando los otros 3 bytes. Simplemente pasas al siguiente número a comparar. Lo que daría como resultado unas 103 lecturas máximas en caso de que la última comparación sea correcta.
Ahora sí implementas una organización en los números será más rápida la búsqueda.

[jonathanPIC888]

Estimados amigos,

Ya pude realizar todo el proceso de grabación, lectura y gestión de los datos que necesito desde la EEPROM. Ahora me encuentro avanzando en el algoritmo de búsqueda, que de por si funciona, pero estoy intentando optimizar.

Lo que he realizado hasta el momento es lo siguiente:

- El uC 1 le envía una trama de configuración al uC 2 con 10 tramas de 10 enteros de 32 bits, utilizando la UART y CRC.
- El uC 2 procesa esos datos y los almacena de manera ordenada en la EEPROM + el control de CRC.
- Cada vez que se realiza una búsqueda, se realiza por bloques de 10 enteros, que se leen desde la EEPROM, se controla el CRC y por último se copia en RAM para su posterior comparación con un valor de parámetro.

Esta última parte de la comparación, funciona pero lo estoy ajustando.

[jonathanPIC888]

Buen día a todos,

Luego de algunas pruebas, he logrado terminar lo que me había propuesto.

Teniendo en cuenta el siguiente arreglo:

Código: [Seleccionar]

struct config_logger

{

  unsigned int32 config1;
  unsigned int32 config2;
  unsigned int32 config3;
  unsigned int32 config4;
  unsigned int32 config5;
  unsigned int32 config6;
  unsigned int32 config7;
  unsigned int32 config8;
  unsigned int32 config9;
  unsigned int32 config10;
  unsigned int16 crc;
 
} logs;


Lo cargo con los siguientes datos.

logs.config1 = 0xFFAA889A;
logs.config2 = 0xBB77889C;
logs.config3 = 0xCC668123;
logs.config4 = 0xAA66FF23;
logs.config5 = 0xC0660023;
logs.config6 = 0x0066812A;
logs.config7 = 0xCCAABB23;
logs.config8 = 0xFFFF8123;
logs.config9 = 0xDDDF0234;
logs.config10 = 0x4566812F;

En el mapeo de la memoria EEPROM queda así:

Código: [Seleccionar]

**   00 01 02 03 04 05 06 07 08 09 0a 0b 0c 0d 0e 0f \0D\0A
0000 9a 88 aa ff 9c 88 77 bb 23 81 66 cc 23 ff 66 aa \0D\0A
0010 23 00 66 c0 2a 81 66 00 23 bb aa cc 23 81 ff ff \0D\0A
0020 34 02 df dd 2f 81 66 45 89 de ff ff ff ff ff ff \0D\0A

Luego de mi función de búsqueda (post lectura de eeprom/corroborar CRC y copiar en RAM), lo que hago es apuntar al primer dato
en RAM y preguntar si existe el dato; por ejemplo: 0x4566812F (está en la última posición del arreglo).

Haciendo eso, encuentro el dato en 15ms aprox. Voy a ver para un arreglo más grande y con 10 estructuras almacenadas y les digo como me fué.

[DominusDRR]

¿15 ms?

Parecería que estás leyendo la EEPROM y realizando la búsqueda sobre la EEPROM, en lugar que haberla pasado a la RAM, y hacer las búsquedas y actualizaciones con dicha memoria.

¿Está activado algún nivel de optimización  el código del microcontrolador?

[jonathanPIC888]

Como estás DominusDRR

Estoy utilizando CCS C para lo que estoy armando. El tiempo lo estoy midiendo con el timer0 del PIC18F27K40.

Pero efectivamente la búsqueda la hace desde la RAM, no desde la EEPROM (externa 24LC1025).

Si cuando termine la implementación, el tiempo total de búsqueda me da, por ejemplo, 150...200ms, para mi está dentro los parámetros de tiempo que necesito.

[DominusDRR]

Como estás DominusDRR

Estoy utilizando CCS C para lo que estoy armando. El tiempo lo estoy midiendo con el timer0 del PIC18F27K40.

Pero efectivamente la búsqueda la hace desde la RAM, no desde la EEPROM (externa 24LC1025).

Si cuando termine la implementación, el tiempo total de búsqueda me da, por ejemplo, 150...200ms, para mi está dentro los parámetros de tiempo que necesito.

Parece mucho tiempo, pero siendo un MCU de 8 bits, tal vez sea lo normal. ¿Y el CCS C tiene niveles de optimización al compilar el código? O tal vez debas escribir en ASM esa parte de la búsqueda.

[jonathanPIC888]

O tal vez debas escribir en ASM esa parte de la búsqueda.

No escribo una línea de ASM hace 16 años por lo menos..ajjajajaj

[Robert76]

Bien, si ahora tienes los datos ordenados. Entonces utiliza el método de búsqueda dicotómico. Es decir El 1er dato lo comparas con un valor intermedio si es mayor o menor lo comparas con la sig. Mitad de referencia, es decir que en pocos pasos tienes una búsqueda
exponencial.