Implementar un buffer circular en Arduino


En esta entrada vamos a implementar un buffer circular en Arduino. ¿Qué es y para qué sirve un buffer circular?

Imaginemos que vamos a recibir una serie de valores pero, normalmente para ahorrar memoria, no queremos almacenar todos ellos. Únicamente tenemos interés en almacenar los últimos N valores recibidos, manteniendo el orden de recepción.

La primera alternativa que se nos puede ocurrir es emplear un array de dimensión N, almacenar cada valor recibido en la posición 0, y desplazar el resto de valores a la derecha para alojar nuevo valor.

Este primer método es ineficiente porque requiere que desplacemos N-1 valores (cuando está lleno) cada vez que recibimos un nuevo valor, por lo que obtenemos un algoritmo de O(n).

Anuncio:

Por si os lo preguntáis, la cosa no mejora guardando en la última posición. En el momento que nuestro buffer se llene, igualmente tendremos que ser desplazar N-1 valores e nuevamente tenemos un algoritmo de O(n).

Un buffer circular (o buffer en anillo) es una alternativa para conseguir un orden O(1) en esta situación. Nuevamente empleamos un array de longitud N pero, en lugar de desplazar los valores almacenados, variamos la posición en la que insertamos el elemento

Para ello únicamente tenemos que almacenar y gestionar el índice de la posición actual. También tendremos que lidiar con los límites del array en las operaciones de lectura y escritura, por ejemplo, reiniciando el índice del buffer a 0 cuando sobrepasemos el límite superior del array.

La lectura de los M últimos valores de un buffer circular es ineficiente porque los valores no están en posiciones consecutivas en la memoria, por lo que no podemos copiarlo directamente.

Si esta pérdida de eficiencia es un problema y la memoria no es un factor crítico, podríamos emplear un buffer de longitud 2N. Grabando simultáneamente los valores en I e I+N, los M últimos valores siempre están almacenados entre I-M e I+N-M.

Los buffer circulares son frecuentes en sistemas de comunicación, almacenado de órdenes en un sistema y filtrado de sensores. En una próxima entrada veremos cómo usar un buffer circular para calcular rápidamente un filtro de media.

Buffer circular simple con índice

Aquí tenemos una implementación muy reducida de un buffer circular. Empleamos la variable 'circularBufferIndex' para almacenar la posición actual, y al añadir al buffer tratamos con los límites del Array.

Estos son los resultados de ejecutar este código. Vemos que los números se almacenan en el buffer y, cuando este se llenan, empiezan a sobreescribirse. De esta forma podemos obtener los N últimos números.

Buffer circular simple con puntero

El ejemplo anterior hemos empleado el índice para acceder a la posición actual del buffer porque resulta adecuado para explicar el funcionamiento. Pero, en general, lo normal es que usemos un puntero (de hecho, es un código que está pidiendo a gritos un puntero).

Así que, para que no se diga, aquí tenéis el código modificado para emplear un puntero en lugar del índice. Básicamente el funcionamiento es el mismo que el anterior, y los resultados que obtenéis son exactamente iguales a los mostrados anteriormente.

Buffer circular en una librería

¿Y si lo metemos en una librería? ¡Por supuesto que sí! Aquí tenéis una librería que implementa un buffer circular en Arduino. La implementación es algo más compleja que la de esta entrada, pero a cambio es más sencilla de usar y potente. ¡A disfrutar!



Si te ha gustado esta entrada y quieres leer más sobre Arduino puedes consultar la sección tutoriales de Arduino

Anuncio:

Previous Librería Arduino QuickMedian
Next Librería Arduino Circular Buffer
1000
2 Comment threads
1 Thread replies
0 Followers
 
Most reacted comment
Hottest comment thread
2 Comment authors
newest oldest
Osqui

Hola.
Estos últimos posts sobre algoritmos de ordenación, etc son muy interesantes y didácticos. Muchas gracias!!

No obstante, ¿Por qué no se anima a empaquetar todas estas funciones en una librería y ofrecerla en el Library Manager de una forma más directa y amigable para todo el mundo?
Muchas gracias de todas formas.

Osqui

Oooh, perdón! Acabo de ver que acaba de hacer justamente lo que le comentaba.
Gracias!!

luisllamas

Me alegro de que te haya sido de utilidad!