Implementar un array de tamaño dinámico en Arduino

Una petición habitual que vemos en foros y páginas de Arduino es cómo conseguir una colección en C++ que cambie su tamaño dinámicamente, permitiendo añadir y eliminar elementos, en una implementación suficientemente ligera para funcionar correctamente en un microprocesador como Arduino.

Bueno, afortunadamente no somos los primeros ni los últimos dentro del mundo de la programación con esta necesidad de crear colecciones dinámicas. De hecho, esta problemática lleva con nosotros desde que el mundo es mundo (o bueno, al menos desde los principios de la informática).

Como resultado, se han encontrado múltiples soluciones que los distintos lenguajes han implementado en distintas colecciones (árboles, array de tamaño dinámico, linked list), cada una con sus propias ventajas y desventajas.

En esta entrada vamos a implementar un array de tamaño dinámico, y en la siguiente abordaremos la problemática desde el punto con una linked list.

En primer lugar… ¡imposible!. Me diréis, un array no puede variar su tamaño una vez creado. Al instanciar un array se reserva espacio en la memoria para almacenar sus elementos, y una vez creado es imposible cambiar su tamaño (entre otras cosas porque puede no tener sitio para crecer donde está guardado)

Y tenéis toda la razón, un array no puede cambiar su tamaño una vez creado. Pero nada nos impide crear un nuevo array con el tamaño deseado (más grande o más pequeño), copiar el contenido del array original, y finalmente eliminarlo. Así es precisamente como trabaja un array de tamaño dinámico.

En primer lugar creamos un array con una determinada capacidad. Cuando guardemos elementos, contabilizamos la cantidad de elementos que tenemos en el array.

Mientras el número de elementos sea inferior a la capacidad del array, el array de tamaño dinámico se comporta igual que un array normal.

Si seguimos añadiendo elementos en algún momento agotaremos la capacidad del array.

En ese momento generamos un nuevo array, copiamos los elementos, y borramos el antiguo array.

La norma que se suele tomar es que el nuevo array tenga el doble de capacidad que el array original (2*N). No obstante, cualquier otra norma es posible (por ejemplo 1.2*N, N+10…).

Si queremos reducir el array para disminuir la cantidad de memoria ocupada por el mismo, generamos un nuevo array que tenga como capacidad el número de elementos almacenados, e igualmente copiamos y borramos el original. Si lo preferimos podemos dejar un cierto margen aunque, en general, no es lo habitual.

En cuanto a la eficiencia, el array de tamaño dinámico se comporta igual que un array normal (porque de hecho lo es). En particular, las lecturas por índice son O(1), y las escrituras por índice son O(1). Las inserciones de elementos es de O(n). Añadir un elemento (al final de la colección) es O(1), salvo, si existe capacidad restante.

Si es necesario expandir (cambiar el tamaño del array) las operaciones se ralentizan, porque es necesario generar el nuevo array, y copiar todos los elementos, lo cual es un proceso relativamente lento.

Evitar la expansión del array es el motivo por el que se suele tomar como normal duplicar la capacidad. No obstante, en un micro con poca memoria como Arduino quizás sea excesivo, y sea preferible sacrificar algo de velocidad disminuyendo el factor de crecimiento.

A continuación tenemos una implementación muy básica de un array de tamaño dinámico para ilustrar su funcionamiento.

Únicamente disponemos de dos métodos, AddItem() y RemoveTail() que, respectivamente, añaden o eliminan el último elementos del array dinámico.

Por otro lado, tenemos el método resize(), que realiza el cambio de tamaño del array, y el método Trim() que reduce el tamaño del array al número de elementos para reducir la memoria consumida.

int* list; size_t count; size_t capacity; // Crear una nueva lista void CreateList(size_t _capacity) { list = new int[_capacity]; capacity = _capacity; count = 0; } // Añadir elemento al final de la lista void AddItem(int item) { ++count; if (count > capacity) { size_t newSize = capacity * 2; resize(newSize); } list[count – 1] = item; } // Eliminar ultimo elemento de la lista void RemoveTail() { –count; } // Reducir capacidad de la lista al numero de elementos void Trim() { resize(count); } // Reescalar lista void resize(size_t newCapacity) { int* newList = new int[newCapacity]; memmove(newList, list, count * sizeof(int)); delete[] list; capacity = newCapacity; list = newList; } // Muestra la lista por Serial para debug void printList() { Serial.print(“Capacity:”); Serial.print(capacity); Serial.print(” Count:”); Serial.print(count); Serial.print(” Items:”); for (size_t index = 0; index < count; index++) { Serial.print(list[index]); Serial.print(‘ ‘); } Serial.println(); } void setup() { Serial.begin(9600); Serial.println(“Lista con 2 elementos”); CreateList(2); Serial.println(); Serial.println(“Introducir 1 y 2 elementos”); AddItem(1); AddItem(2); printList(); Serial.println(); Serial.println(“Resize e introducir 3 y 4 elementos”); AddItem(3); AddItem(4); printList(); Serial.println(); Serial.println(“Resize e introducir 5 y 6 elementos”); AddItem(5); AddItem(6); printList(); Serial.println(); Serial.println(“Eliminar dos ultimos”); RemoveTail(); RemoveTail(); printList(); Serial.println(); Serial.println(“Ajustar tamaño”); Trim(); printList(); } void loop() { }

100

101

102

103

104

105

106

107

int* list;

size_t count;

size_t capacity;

// Crear una nueva lista

void CreateList(size_t _capacity)

{

list = new int[_capacity];

capacity = _capacity;

count = 0;

}

// Añadir elemento al final de la lista

void AddItem(int item)

{

++count;

if (count > capacity)

{

size_t newSize = capacity * 2;

resize(newSize);

}

list[count – 1] = item;

}

// Eliminar ultimo elemento de la lista

void RemoveTail()

{

—count;

}

// Reducir capacidad de la lista al numero de elementos

void Trim()

{

resize(count);

}

// Reescalar lista

void resize(size_t newCapacity)

{

int* newList = new int[newCapacity];

memmove(newList, list, count * sizeof(int));

delete[] list;

capacity = newCapacity;

list = newList;

}

// Muestra la lista por Serial para debug

void printList()

{

Serial.print(“Capacity:”);

Serial.print(capacity);

Serial.print(” Count:”);

Serial.print(count);

Serial.print(” Items:”);

for (size_t index = 0; index < count; index++)

{

Serial.print(list[index]);

Serial.print(‘ ‘);

}

Serial.println();

}

void setup()

{

Serial.begin(9600);

Serial.println(“Lista con 2 elementos”);

CreateList(2);

Serial.println();

Serial.println(“Introducir 1 y 2 elementos”);

AddItem(1);

AddItem(2);

printList();

Serial.println();

Serial.println(“Resize e introducir 3 y 4 elementos”);

AddItem(3);

AddItem(4);

printList();

Serial.println();

Serial.println(“Resize e introducir 5 y 6 elementos”);

AddItem(5);

AddItem(6);

printList();

Serial.println();

Serial.println(“Eliminar dos ultimos”);

RemoveTail();

printList();

Serial.println();

Serial.println(“Ajustar tamaño”);

Trim();

printList();

}

void loop()

{

}

Si ejecutamos el código, veremos la siguiente salida.

Por supuesto esto no podía quedar aquí. Aquí tenéis el enlace a la librería List, una implementación completa de una lista dinámica, con añadir, insertar, eliminar elementos, invertir el orden, convertir desde/hacia un array, etc…

A la vez que sigue siendo lo suficientemente sencilla para funcionar en un procesador como Arduino. ¡A disfrutar!

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

Implementar un array de tamaño dinámico en Arduino Deja un comentario

Deja una respuesta Cancelar la respuesta