Listas enlazadas aumentadas: una guía esencial

¿Cómo funciona una lista enlazada?

Una lista vinculada es una estructura de datos donde los campos de cada dato están conectados mediante punteros en lugar de compensaciones. Consta de un elemento principal que almacena el primer y el último elemento, los llamados elementos de nodo, que contienen todos los campos de usuario necesarios (como teléfono, propietario, empresa, etc.) y un puntero al siguiente nodo. El último elemento está vinculado al campo NULL que indica el final de la lista.

Cuando se agrega un nuevo elemento a la lista vinculada, el nodo principal debe actualizar el puntero de "cola" al nuevo nodo final, y el puntero NULL anterior debe actualizarse al nuevo nodo final.

Esta estructura de datos permite un registro eficiente de nuevos datos sin cambiar el tamaño de toda la matriz. Es un método eficaz para almacenar datos de sólo escritura y no requiere conocer la cantidad de elementos de antemano. Es una estructura de datos simple y en la memoria se ve así:

Lista enlazada para claves de desalojo

En un artículo anterior, analizamos la necesidad de un búfer para escanear el árbol sin abandonarlo después de eliminar cada elemento. En idiomas con GC, esto no es un problema. Sin embargo, cuando el código de la aplicación administra la memoria, una solución puede ser un búfer basado en una lista vinculada que contenga elementos obsoletos.

Una lista vinculada permite la rápida adición de elementos. Sin embargo, encontrar algo en la lista vinculada requiere un escaneo secuencial, lo que lo hace inadecuado para la recuperación rápida de claves. Por lo tanto, es una solución eficaz para registrar datos, crear buffers temporales y organizar datos para realizar lecturas secuenciales desde los nodos principales.

Encontrar elementos para adelantarse es un ejemplo de tal tarea. La preferencia se utiliza a menudo en las diferentes implementaciones de caché. La caché contiene datos que se pueden restaurar desde otras fuentes de memoria con mayor latencia. El caché generalmente se almacena en la memoria principal. La memoria principal es limitada y, para un uso eficaz, sólo se puede almacenar una pequeña instantánea de datos en la memoria principal.

Requiere que usemos la memoria de manera más inteligente, evitando el uso de memoria para datos rara vez solicitados y eliminando dichos datos si se solicitan con poca frecuencia.

Un método eficaz para desalojar campos en caché es el método menos utilizado recientemente (LRU). Aquí está la representación de LRU a continuación:

En este caso, la aplicación incluye al menos una lista vinculada para almacenar objetos usados recientemente y tiene otras estructuras de datos (como una tabla hash) para una búsqueda rápida. Los nodos están interconectados.

Cuando un usuario recupera datos de la tabla hash, la lista vinculada actualiza estos datos moviéndolos a la cola. Como resultado, después de varias operaciones, la cola contiene datos utilizados recientemente, mientras que la cabeza contiene datos raramente solicitados.

En casos de desbordamiento de memoria, la aplicación puede escanear los primeros N elementos para liberar suficiente memoria. Esta es una operación sencilla ya que la lista vinculada se adapta a escaneos secuenciales. Se liberará la memoria con datos poco utilizados y se podrán almacenar en caché nuevos nodos más frecuentes.

 #include <stdlib.h> #include <stdio.h> typedef struct lnode_t { struct lnode_t *next; struct lnode_t *prev; void *ptr; } lnode_t; typedef struct list_t { lnode_t *head; lnode_t *tail; } list_t; lnode_t* lru_insert(list_t *list, char *ptr) { if (!list->head) { list->head = list->tail = calloc(1, sizeof(lnode_t)); list->head->ptr = ptr; return list->head; } lnode_t *saved_tail = list->tail; lnode_t *new = calloc(1, sizeof(sizeof(lnode_t))); new->ptr = ptr; saved_tail->next = new; new->prev = saved_tail; list->tail = new; return new; } void lru_update(list_t *list, lnode_t *lnode) { if (list->tail == lnode) { return; } lnode_t *saved_tail = list->tail; saved_tail->next = lnode; if (!lnode->prev) list->head = lnode->next; lnode->next = NULL; lnode->prev = saved_tail; list->tail = lnode; } void lru_evict(list_t *list, int items, void (*func)(void* arg, void *ptr), void* arg) { lnode_t *lnode = list->head; while(items-- && lnode) { func(arg, lnode->ptr); lnode_t *prev = lnode->prev; lnode_t *next = lnode->next; if (prev) prev->next = next; if (next) next->prev = prev; free(lnode); lnode = next; } if (!lnode) list->head = list->tail = NULL; } void print_deleted_obj(void *arg, void *ptr) { printf("evicted: %p\n", ptr); deleteThisInTheOtherStructure(arg, ptr); } int main() { list_t *list = calloc(1, sizeof(list_t)); lnode_t *test = lru_insert(list, "some data"); lru_insert(list, "another data"); lru_update(list, test); lru_evict(list, 1, print_deleted_obj, otherStructure); }

Una observación: cuando el número de elementos utilizados difiere significativamente en frecuencia (por ejemplo, el 95% de las solicitudes distribuidas en las 100 claves principales de 1 millón), el Splay Tree podría ser más adecuado para almacenar caché. Este árbol está equilibrado en función de la frecuencia de uso de cada nodo.

La idea principal de Splay Tree es la opuesta a LRU: los elementos más utilizados se encuentran cerca de la raíz, lo que hace que esta estructura de datos sea ideal como estructura primaria para el caché.

El desalojo se puede resolver de dos maneras: utilizando una lista vinculada interconectada con la estructura principal o modificando un árbol Splay a un árbol binario subproceso. Los nodos del Splay Tree ya están ordenados por frecuencia de uso. Aunque el subproceso adicional de las hojas de los árboles puede requerir más tiempo de CPU, puede ahorrar memoria.

Para comprender mejor la aceleración de los datos utilizados recientemente en la memoria, puede explorar un ejemplo de migración de VM en vivo en este enlace .

Mejore la velocidad de escaneo de la lista vinculada

Como se mencionó anteriormente, las listas vinculadas ofrecen la solución más rápida para escribir datos. Su velocidad de escaneo es buena, pero es más lenta que la velocidad de escaneo en la matriz.

Describí este problema como localidad de datos en el artículo anterior. Sin embargo, al ser similares a los árboles binarios, las listas enlazadas tienen potencial de mejora. Desenrollar listas vinculadas le permite almacenar más datos en cada nodo de la lista. Por lo tanto, ahorra memoria en el siguiente nodo puntero y, a veces, mejora el rendimiento, siempre que el tamaño del elemento coincida con la línea de caché de la CPU:

La idea principal permanece sin cambios, pero se alterará la representación de la lista en la memoria.

Cambiará en muchos sentidos. Hay 2 opciones a continuación:

Estas mejoras aumentan el rendimiento de las listas vinculadas, pero añaden cierta complejidad al código. Para operaciones de disco con una lista vinculada, un nodo desenrollado puede tener más elementos. Una forma sencilla de entender cómo funciona es imaginar una lista enlazada de matrices.

En el código, necesitamos modificar la descripción de la estructura y, de ahora en adelante, leer o escribir cada elemento en la matriz de la estructura:

 typedef struct lnode_t { struct lnode_t *next; struct lnode_t *prev; void *ptr[3]; } lnode_t;

Saltar lista

La lista de omisión es un método para mejorar las características de velocidad de los elementos de búsqueda en una lista vinculada. Este tipo de lista vinculada almacena una clave para ordenar la lista vinculada e incluye punteros adicionales para localizar nodos de manera más eficiente que una simple operación de escaneo.

Los nodos adicionales mejoran la velocidad de desplazamiento entre nodos en una lista de omisión. Funciona como una búsqueda binaria. Al contrario, lleva más tiempo añadir nuevos elementos. Por lo tanto, las listas de omisión deben tener una clave. Las aplicaciones pueden crear cualquier número de niveles para mejorar las características de velocidad. En la mayoría de los casos, una mejor opción es tener niveles ligeramente menores o aproximadamente iguales que la altura del árbol. (Mira la imagen de arriba)

Durante la búsqueda, una aplicación comienza desde el nivel más alto, que es la ruta más rápida. Al detectar la clave cercana desciende a un nivel inferior hasta encontrar el nodo deseado.

Este proceso da como resultado una complejidad temporal de O (log (n)). Por ejemplo, usar 4 niveles para una lista de omisión con 16 nodos, 20 niveles para 1 millón de nodos y 32 niveles para 4 mil millones de nodos proporciona una complejidad temporal similar al árbol RB.

La lista de omisión es mejor por las siguientes razones:

• Simplicidad de implementación. A pesar de las características similares al árbol RB, es mucho más fácil de implementar y mantener.

• Alta eficiencia al agregar nuevos nodos al final de la lista de omisión.

• Crear una implementación segura para subprocesos de la lista de omisión es más fácil que el árbol.

¡Exploremos la implementación de este concepto!

Nodos de estructura:

 typedef struct skip_node { uint64_t key; uint64_t value; struct skip_node **forward; } skip_node; typedef struct skip_t { uint64_t level; uint8_t max_level; skip_node *header; } skip_t;

Función para crear nodos:

 skip_node* create_skip_node(uint64_t key, int value, int level) { skip_node *newskip_node = (skip_node*)malloc(sizeof(skip_node)); newskip_node->key = key; newskip_node->value = value; newskip_node->forward = malloc(sizeof(skip_node)*level); for (uint64_t i = 0; i < level; i++) { newskip_node->forward[i] = NULL; } return newskip_node; } skip_t* skip_new(uint8_t max_level) { skip_t *list = (skip_t*)malloc(sizeof(skip_t)); list->level = 0; list->max_level = max_level; skip_node *header = create_skip_node(0, 0, max_level); list->header = header; for (uint64_t i = 0; i < max_level; i++) { header->forward[i] = NULL; } return list; }

Durante la inserción, la tarea incluye la detección de la ubicación correcta para almacenar el nodo y determinar el número de niveles para conectarse a este nodo. El uso de una función aleatoria para determinar los niveles ayuda a simplificar el proceso para cada nuevo nodo. En promedio, esta función asigna el segundo nivel en el 50% de los casos, el tercer nivel en el 25% de los casos, y así sucesivamente. Este método minimiza el tiempo de acceso a la memoria para reequilibrar elementos.

 uint64_t random_level(uint8_t max_level) { uint64_t level = 1; while (rand() < RAND_MAX / 2 && level < max_level) { level++; } return level; } void skip_insert(skip_t *list, uint64_t key, int value) { skip_node *update[list->max_level]; skip_node *current = list->header; for (uint64_t i = list->level - 1; i >= 0; i--) { while (current->forward[i] != NULL && current->forward[i]->key < key) { current = current->forward[i]; } update[i] = current; } current = current->forward[0]; if (current == NULL || current->key != key) { uint64_t newLevel = random_level(list->max_level); if (newLevel > list->level) { for (uint64_t i = list->level; i < newLevel; i++) { update[i] = list->header; } list->level = newLevel; } skip_node *newskip_node = create_skip_node(key, value, newLevel); for (uint64_t i = 0; i < newLevel; i++) { newskip_node->forward[i] = update[i]->forward[i]; update[i]->forward[i] = newskip_node; } } }

Función para buscar nodos:

 skip_node* skip_search(skip_t *list, uint64_t key) { skip_node *current = list->header; for (uint64_t i = list->level - 1; i >= 0; i--) { while (current->forward[i] != NULL && current->forward[i]->key < key) { current = current->forward[i]; } } current = current->forward[0]; ++nodes_scan; if (current != NULL && current->key == key) return current; else return NULL; }

Una función de referencia para probar el rendimiento de una lista vinculada, una lista de omisión y el árbol RB. Los valores, utilizados como claves, se establecen como potencias de dos. El valor a efectos de prueba no importa.

 skip_t *skipList = skip_new(atoi(argv[1])); list_t *llist = list_new(); tree_t *tree = calloc(1, sizeof(*tree)); size_t to_index = 50000000; struct timespec s_icalc; struct timespec e_icalc; struct timespec s_scalc; struct timespec e_scalc; clock_gettime(CLOCK_REALTIME, &s_icalc); for (uint64_t i = 0; i < to_index; ++i) tree_insert(tree, i, i*2); clock_gettime(CLOCK_REALTIME, &e_icalc); count = 0; nodes_scan = 0; clock_gettime(CLOCK_REALTIME, &s_scalc); for (uint64_t i = 0; i < to_index; ++i) { node_t *node = tree_get(tree, i); } clock_gettime(CLOCK_REALTIME, &e_scalc); clock_gettime(CLOCK_REALTIME, &s_icalc); for (uint64_t i = 0; i < to_index; ++i) skip_insert(skipList, i, i*2); clock_gettime(CLOCK_REALTIME, &e_icalc); count = 0; clock_gettime(CLOCK_REALTIME, &s_scalc); for (uint64_t i = 0; i < to_index; ++i) { skip_node* ret = skip_search(skipList, i); } clock_gettime(CLOCK_REALTIME, &e_scalc); clock_gettime(CLOCK_REALTIME, &s_icalc); for (uint64_t i = 0; i < to_index; ++i) list_add(llist, NULL, NULL); clock_gettime(CLOCK_REALTIME, &e_icalc);

Resultados de probar estas estructuras de datos en claves que crecen secuencialmente:

Este es el mejor momento para insertar (si no se tiene en cuenta una simple lista enlazada) y un método bastante rápido para buscar elementos.

Resultados de probar estas estructuras de datos en claves secuencialmente decrecientes:

Esto es fácil de entender: esta implementación de una lista de omisión solo tiene un puntero al primer elemento. Agregar nodos al final es más complejo. Para cambiar este enfoque, podemos agregar un segundo puntero (a la cola) o una lista de salto inversa (la cabeza apuntará a los valores grandes). Significa que una lista de omisión es una estructura de datos eficaz para datos de registro como las secuencias de Kafka. En ese caso, puede ser al menos dos veces más rápido que el árbol RB y más fácil de implementar.

Saltar lista reduce la velocidad de inserción de la lista vinculada; sin embargo, para datos secuenciales, sigue siendo más rápida que otras estructuras de datos con tiempo de acceso logarítmico a los elementos, especialmente cuando las claves crecen secuencialmente. Sin embargo, cualquier crecimiento secuencial de las claves complica las inserciones en el árbol ya que provoca muchas rotaciones para mantener el equilibrio del árbol.

Funciona eficazmente sólo cuando el valor aumenta (o disminuye) a lo largo de la secuencia. Por ejemplo, si aleatorizamos las claves, los resultados serán diferentes:

Como se ve, la distribución entre los valores no afecta significativamente la característica de velocidad del árbol RB, pero sí afecta notablemente el rendimiento de la lista de omisión.

Conclusiones

Hoy en día, nuestras aplicaciones pueden organizar los datos en la memoria o en el disco de diferentes maneras. Los mapas y las listas desempeñan un papel importante a la hora de organizar los datos en diferentes órdenes para diversos fines. Estas estructuras garantizan un rendimiento, una eficiencia de recursos y una capacidad suficientes.

En ocasiones no es suficiente para nuestras necesidades y hay que cambiar la aplicación en las partes críticas para que sea más óptima. Algunos casos pueden beneficiarse del uso de estructuras de datos más adecuadas, como árboles para coincidencias inexactas o economía de memoria. Otros, procedentes de mejoras del algoritmo, como el uso de métodos asincrónicos para mejorar el rendimiento de los subprocesos individuales.

Cuando se agoten todas las demás opciones, el enfoque restante es adaptar la estructura de datos y ajustar la metodología de uso. Hay ejemplos de algunos cambios en la estructura de datos para hacerlos más adecuados para una tarea prácticamente específica.

Si bien una lista vinculada es principalmente una estructura de datos de escaneo de secuencia y solo escritura, se puede optimizar más que el árbol RB y seguir siendo eficiente en un caso de solo escritura. Sin embargo, un impulso de características particulares puede impactar a otras. Por tanto, la mejor forma es priorizar lo importante y descartar lo que no lo es.