Sets

Funciones

Los conjuntos set, son contenedores de datos que nos permiten trabajar con colecciones de objetos, al igual que los array. La principal diferencia radica en que los elementos no se almacenan en posiciones contiguas de memoria, sino que utilizan una estructura en forma de árbol donde cada nodo tiene dos descendientes (Figura 1). Son conocidos como BST (binary search trees) o árboles rojo-negro.

Los BST son estructuras optimizadas para casos donde sean muy frecuentes las inserciones, borrados y búsquedas. Están permanentemente ordenados, de ahí que sea posible insertar, eliminar o localizar cualquier elemento en tiempo logarítmico O(logn), sin necesidad de utilizar funciones de ordenación como arrst_sort (Figura 2). Para que el mantenimiento se pueda llevar a cabo de forma eficiente, el árbol que soporta la estructura debe cumplir una serie de características:

• Binario: Cada nodo solo puede tener 0, 1 ó 2 hijos.
• Ordenado: Todos los descendientes a la izquierda de un nodo son de menor valor y los situados a la derecha de mayor valor. El criterio de orden y búsqueda se establece en el constructor mediante una función de comparación de clave y no se puede cambiar durante el tiempo de vida del contenedor. Los nuevos elementos se insertarán en su posición correcta conforme a este orden. No soporta elementos duplicados ni en posiciones arbitrarias.
• Balanceado: Un árbol puede cumplir las dos propiedades anteriores, pero haber degenerado a una lista donde las búsquedas ya no pueden resolverse en tiempo logarítmico (Figura 3). Internamente, los contenedores SetSt de NAppGUI están implementados con los llamados árboles rojo-negro, donde se garantiza una altura máxima de 2log(n+1). Esto se consigue reestructurando el árbol después de cada inserción o borrado, por lo que añadir un nuevo elemento (o eliminarlo) se resuelve en un máximo de O(logn). Esto es muchísimo más rápido que en arrays, donde hay que desplazar todos los elementos para insertar un registro en una posición concreta, con un coste asociado de O(n).

1. Crear sets

• Utiliza setst_create para crear un set.
• Utiliza setst_destroy para destruir el set y sus elementos.

Debido a que el conjunto de elementos debe permanecer siempre ordenado bajo el mismo criterio, deberemos indicar en el constructor la función de comparación objeto-clave (ver Comparadores y claves) (Listado 1). Al igual que ocurría a la hora de ordenar y buscar en arrays, necesitamos definir los campos que conformarán la clave única del objeto, la cual nos permitirá localizar elementos más adelante. La función que destruye un elemento del conjunto, no debe liberar la memoria que ocupa el objeto en sí, ya que es gestionada por el contenedor, al igual que ocurre con los ArrSt.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25

typedef struct _product_t Product;
struct _product_t
{
    type_t type;
    String *code;
    String *desc;
    Image *image;
    real32_t price;
};

static void i_remove(Product *prod)
{
    str_destroy(&prod->code);
    str_destroy(&prod->desc);
    image_destroy(&prod->image);
}

static int i_compare(const Product *prod, const char_t *code)
{
    return str_cmp(prod->code, code);
}

SetSt(Product) *products = setst_create(i_compare, Product, char_t);
...
setst_destroy(&products, i_remove, Product);

2. Insertar y eliminar elementos en sets

• Utiliza setst_insert para insertar un elemento.
• Utiliza setst_delete para eliminar un elemento.

Al contrario que ocurre con los arrays, no podemos añadir elementos en cualquier posición arbitraria, por lo que insertar lleva implícita una búsqueda mediante la clave del objeto (Listado 2). Si ya existiera un elemento con la misma clave, no se llevará a cabo la inserción y se devolverá NULL. En caso contrario, se nos devolverá la dirección de memoria donde deberemos inicializar nuestro objeto.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15

Product *prod = setst_insert(products, "GTK-1050", Product, char_t);
if (prod != NULL)
{
    prod->type = ekHDD;
    prod->code = str_c("GTK-1050");
    prod->desc = str_c("Gigabyte GeForce GTX 1050 OC 2Gb GDDR5");
    prod->image = load_image("card.png");
    prod->price = 573.34;
}
else
{
    // Object already exists
}
...
setst_destroy(&products, i_remove, Product);

No se permiten duplicados en SetSt, entendiendo como tal aquellos elementos que tengan la misma clave.

Eliminar es similar a insertar, tan solo deberemos proporcionar la clave y un destructor. Si no existe un elemento con dicha clave, se retornará FALSE (Listado 3).

1
2
3
4
5
6
7
8
9

bool_t del = setst_delete(products, "GTK-1050", i_remove, Product, char_t);
if (del == TRUE)
{
    // Deleted!
}
else
{
    // Not found
}

3. Búsqueda y recorrido en sets. Iteradores

• Utiliza setst_get para buscar un elemento.
• Utiliza setst_next para desplazar el iterador al siguiente elemento.
• Utiliza setst_prev para desplazar el iterador al elemento anterior.
• Utiliza setst_first para desplazar el iterador al primer elemento del set.
• Utiliza setst_last para desplazar el iterador al último elemento del set.

No podemos acceder a los elementos de un set mediante un índice aleatorio, como ocurría con los arrays. Los nodos están dispersos en diferentes zonas de memoria, lo que impide calcular la posición de un elemento concreto a partir de una dirección base. Un iterador no es más que un puntero dentro del set que actúa como marcador del elemento seleccionado actualmente (Figura 4). A partir de una posición concreta, podemos desplazarnos al elemento anterior o posterior, pero nunca dar saltos arbitrarios. En (Listado 4) vemos como recorrer los elementos iterando desde el primer registro, y en (Listado 5) como localizar un elemento conocida su clave.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19

const Product *prod = setst_first(products, Product);
while (prod != NULL)
{
    // Do something
    ...

    prod = setst_next(products, Product);
}

setst_foreach(prod, products, Product)
    // Do something
    ...
setst_fornext(prod, products, Product)

// In reverse order
setst_forback(prod, products, Product)
    // Do something
    ...
setst_forprev(prod, products, Product)

1
2
3
4
5
6
7
8
9

const Product *prod = setst_get_const(products, "GTK-1050", Product, char_t);
if (prod != NULL)
{
    // Do something
    ...

    // From here, we can move next or prev
    prod = setst_next(products, Product);
}

Tras setst_get(), el iterador quedará fijado en el elemento.

4. Comparativa arrays y sets

En (Tabla 1) se muestra una comparativa de rendimiento en el uso de ambos contenedores. Se ha utilizado la estructura Product descrita en (Listado 1). Compararemos seis tipos de contenedores, combinando registros y punteros. Las condiciones de la prueba son:

• Los elementos se ordenarán por el campo code utilizando el método i_compare descrito en (Listado 1).
• Los elementos han sido creados previamente y residen en memoria. Los tiempos solo reflejan la gestión realizada por los contenedores.
• El campo code toma valores desde "0" hasta "n-1", donde n=100.000 es el número de elementos. Los elementos han sido previamente desordenados utilizando la función bmem_shuffle_n.
• Las pruebas se han realizado en una Raspberry Pi 3 Model B con NAppGUI compilado en versión Release. Hemos elegido esta plataforma por su clara inferioridad técnica con respecto a otras. De esta forma la diferencia asintótica resulta más evidente.

Operation	ArrSt	ArrPt	ArrSt-Sort	ArrPt-Sort	SetSt	SetPt
Add(100k)	0.006	0.004	27.600	2.896	0.159	0.274
Loop(100k)	0.000	0.000	0.000	0.000	0.022	0.025
Search(100k)	84.139	588.080	0.101	0.218	0.121	0.232
Sort(100k)	0.085	0.205	-	-	-	-
Delete(100k)	0.004	0.003	31.198	3.064	0.171	0.253

A la vista de estos datos, podemos llegar a las siguientes conclusiones:

• Las búsquedas lineales O(n) son tremendamente lentas.
• Mantener un array ordenado tras cada inserción o borrado es costoso. Es más eficiente añadir todos los elementos y luego ordenar, aunque esto no siempre será posible. Si los elementos entran o salen de forma arbitraria pero el conjunto debe siempre estar ordenado, es mejor utilizar sets.
• Los contenedores basados en registros son más eficientes en consultas, pero menos al insertar o borrar. No obstante, este test no incluye el tiempo de crear o liberar memoria dinámica, algo inherente a los contenedores de punteros.
• Iterar en arrays sale prácticamente gratis, pero iterar en sets tiene un pequeño coste debido a la lógica de salto entre nodos.
• No podemos decir que un contenedor sea mejor que otro en general. Dependerá de cada caso concreto.
• Para grupos pequeños (menos de 1000 elementos) las diferencias son prácticamente imperceptibles.
• Para grupos extremadamente pequeños (hasta 100 elementos) utilizar siempre arrays. La mejora asintótica de los sets se ve empañada por la implementación mucho más eficiente de los Arrays.

setst_create ()

Crea un set de registros vacío.

SetSt(type)*
setst_create(FPtr_compare func_compare,
             type,
             ktype);

Retorna

El nuevo set.

Observaciones

Ver Crear sets.

setst_destroy ()

Destruye un set y todos sus elementos.

void
setst_destroy(SetSt(type) **set,
              FPtr_remove func_remove,
              type);

setst_size ()

Obtiene el número de elementos del set.

uint32_t
setst_size(const SetSt(type) *set,
           type);

Retorna

Número de elementos.

setst_get ()

Busca un elemento en O(logn). Si existe, el iterador interno quedará fijado en él.

type*
setst_get(SetSt(type) *set,
          const type *key,
          type,
          ktype);

Retorna

Puntero al elemento si existe, o NULL si no.

Observaciones

Ver Búsqueda y recorrido en sets. Iteradores.

setst_get_const ()

Versión const de setst_get.

const type*
setst_get_const(const SetSt(type) *set,
                const type *key,
                type,
                ktype);

Retorna

Elemento.

setst_insert ()

Inserta un nuevo elemento en el set.

type*
setst_insert(SetSt(type) *set,
             type *key,
             type,
             ktype);

Retorna

Puntero al elemento insertado, que debe utilizarse para inicializar el objeto. Si ya existe un elemento con la misma clave, retornará NULL.

Observaciones

Insertar o eliminar elementos invalida el iterador interno del set. Debes volver a inicializarlo con setst_first o similares. Ver Insertar y eliminar elementos en sets.

setst_delete ()

Elimina un elemento del set.

bool_t
setst_delete(SetSt(type) *set,
             type *key,
             FPtr_remove func_remove,
             type,
             ktype);

Retorna

TRUE si el elemento ha sido eliminado, o FALSE si no existe un elemento con dicha clave.

Observaciones

Insertar o eliminar elementos invalida el iterador interno del set. Debes volver a inicializarlo con setst_first o similares. Ver Insertar y eliminar elementos en sets.

setst_first ()

Obtiene el primer elemento del set e inicializa el iterador interno.

type*
setst_first(SetSt(type) *set,
            type);

Retorna

Puntero al primer elemento o NULL si el set está vacío.

Observaciones

Ver Búsqueda y recorrido en sets. Iteradores.

setst_first_const ()

Versión const de setst_first.

const type*
setst_first_const(const SetSt(type) *set,
                  type);

Retorna

Elemento.

setst_last ()

Obtiene el último elemento del set e inicializa el iterador interno.

type*
setst_last(SetSt(type) *set,
           type);

Retorna

Puntero al último elemento o NULL si el set está vacío.

Observaciones

Ver Búsqueda y recorrido en sets. Iteradores.

setst_last_const ()

Versión const de setst_last.

const type*
setst_last_const(const SetSt(type) *set,
                 type);

Retorna

Elemento.

setst_next ()

Obtiene el siguiente elemento del set, tras incrementar el iterador interno.

type*
setst_next(SetSt(type) *set,
           type);

Retorna

Puntero al siguiente elemento o NULL si el iterador ha alcanzado el último.

Observaciones

Ver Búsqueda y recorrido en sets. Iteradores.

setst_next_const ()

Versión const de setst_next.

const type*
setst_next_const(const SetSt(type) *set,
                 type);

Retorna

Elemento.

setst_prev ()

Obtiene el elemento anterior del set, tras decrementar el iterador interno.

type*
setst_prev(SetSt(type) *set,
           type);

Retorna

Puntero al elemento anterior o NULL si el iterador ha alcanzado el primero.

Observaciones

Ver Búsqueda y recorrido en sets. Iteradores.

setst_prev_const ()

Versión const de setst_prev.

const type*
setst_prev_const(const SetSt(type) *set,
                 type);

Retorna

Elemento.

setst_foreach ()

Recorre todos los elementos del set. Utiliza setst_fornext para cerrar el bucle.

void
setst_foreach(type *elem,
              SetSt(type) *set,
              type);

Observaciones

Ver Búsqueda y recorrido en sets. Iteradores.

setst_foreach_const ()

Versión const de setst_foreach.

void
setst_foreach_const(const type *elem,
                    const SetSt(type) *set,
                    type);

setst_fornext ()

Cierra el bucle abierto por setst_foreach, incrementando el iterador interno.

void
setst_fornext(type *elem,
              SetSt(type) *set,
              type);

setst_fornext_const ()

Versión const de setst_fornext.

void
setst_fornext_const(const type *elem,
                    const SetSt(type) *set,
                    type);

setst_forback ()

Recorre todos los elementos del set en orden inverso. Utiliza setst_forprev para cerrar el bucle.

void
setst_forback(const type *elem,
              type);

Observaciones

Ver Búsqueda y recorrido en sets. Iteradores.

setst_forback_const ()

Versión const de setst_forback.

void
setst_forback_const(const type *elem,
                    const SetSt(type) *set,
                    type);

setst_forprev ()

Cierra el bucle abierto por setst_forback, decrementando el iterador interno.

void
setst_forprev(type *elem,
              SetSt(type) *set,
              type);

setst_forprev_const ()

Versión const de setst_forprev.

void
setst_forprev_const(const type *elem,
                    const SetSt(type) *set,
                    type);