Erweiterte verknüpfte Listen: Ein grundlegender Leitfaden

Wie funktioniert eine verknüpfte Liste?

Eine verknüpfte Liste ist eine Datenstruktur, in der die Felder der einzelnen Daten durch Zeiger statt durch Offsets verbunden sind. Sie besteht aus einem Hauptelement, das das erste und das letzte Element speichert, sogenannte Knotenelemente, die alle erforderlichen Benutzerfelder (wie Telefonnummer, Eigentümer, Unternehmen usw.) und einen Zeiger auf den nächsten Knoten enthalten. Das letzte Element ist mit dem NULL-Feld verknüpft, das das Ende der Liste anzeigt.

Wenn der verknüpften Liste ein neues Element hinzugefügt wird, muss der Hauptknoten den „Tail“-Zeiger auf den neuen Endknoten aktualisieren und der vorherige NULL-Zeiger muss auf das neue Tail aktualisiert werden.

Diese Datenstruktur ermöglicht eine effiziente Aufzeichnung neuer Daten, ohne dass die Größe des gesamten Arrays geändert werden muss. Es handelt sich um eine effektive Methode zum Speichern schreibgeschützter Daten, und es ist nicht erforderlich, die Anzahl der Elemente im Voraus zu kennen. Es handelt sich um eine einfache Datenstruktur, die im Speicher folgendermaßen aussieht:

Verkettete Liste für Räumungsschlüssel

In einem früheren Artikel haben wir die Notwendigkeit eines Puffers zum Scannen des Baums besprochen, ohne den Baum nach jedem Löschen eines Elements zu verlassen. In Sprachen mit GC ist dies kein Problem. Wenn der Anwendungscode jedoch den Speicher verwaltet, kann ein Puffer, der auf einer verknüpften Liste mit veralteten Elementen basiert, eine Lösung sein.

Eine verknüpfte Liste ermöglicht das schnelle Hinzufügen von Elementen. Um jedoch etwas in der verknüpften Liste zu finden, ist ein sequenzielles Scannen erforderlich, was sie für den schnellen Schlüsselabruf ungeeignet macht. Daher ist sie eine effiziente Lösung zum Protokollieren von Daten, Erstellen temporärer Puffer und Organisieren von Daten, um sequenzielle Lesevorgänge von Kopfknoten durchzuführen.

Ein Beispiel für eine solche Aufgabe ist das Suchen nach Elementen, die verdrängt werden sollen. Verdrängung wird häufig in den verschiedenen Cache-Implementierungen verwendet. Der Cache enthält Daten, die mit größerer Latenz aus anderen Speicherquellen wiederhergestellt werden können. Cache wird normalerweise im Hauptspeicher gespeichert. Der Hauptspeicher ist begrenzt und für eine effektive Nutzung kann nur ein kleiner Snapshot der Daten im Hauptspeicher gespeichert werden.

Dies erfordert von uns eine intelligentere Nutzung des Speichers, indem wir die Speichernutzung für selten angeforderte Daten vermeiden und solche Daten entfernen, wenn sie zu selten angefordert werden.

Eine effektive Methode zum Entfernen von Feldern im Cache ist die Least Recently Used (LRU)-Methode. Nachfolgend sehen Sie die LRU-Darstellung:

In diesem Fall enthält die Anwendung mindestens eine verknüpfte Liste zum Speichern zuletzt verwendeter Objekte und verfügt über weitere Datenstrukturen (wie eine Hash-Tabelle) für eine schnelle Suche. Die Knoten sind miteinander verbunden.

Wenn ein Benutzer Daten aus der Hash-Tabelle abruft, aktualisiert die verknüpfte Liste diese Daten, indem sie sie an das Ende verschiebt. Als Ergebnis enthält das Ende nach mehreren Vorgängen kürzlich verwendete Daten, während der Kopf selten angeforderte Daten enthält.

Bei einem Speicherüberlauf kann die Anwendung die ersten N Elemente scannen, um ausreichend Speicher freizugeben. Dies ist ein einfacher Vorgang, da sich die verknüpfte Liste an sequentielle Scans anpasst. Speicher mit selten verwendeten Daten wird freigegeben und neue, häufigere Knoten können im Cache gespeichert werden.

 #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); }

Eine Anmerkung: Wenn die Anzahl der verwendeten Elemente in der Häufigkeit erheblich abweicht (beispielsweise 95 % der Anfragen, die auf die 100 wichtigsten Schlüssel von 1 Million verteilt sind), ist der Splay Tree möglicherweise besser zum Speichern des Caches geeignet. Dieser Baum ist basierend auf der Häufigkeit der Verwendung jedes Knotens ausgeglichen.

Die Grundidee des Splay Tree ist das Gegenteil von LRU – die am häufigsten verwendeten Elemente befinden sich in der Nähe der Wurzel, wodurch sich diese Datenstruktur ideal als Primärstruktur für den Cache eignet.

Die Räumung kann auf zwei Arten gelöst werden: durch Verwendung einer verknüpften Liste, die mit der Hauptstruktur verbunden ist, oder durch Ändern eines Splay-Baums in einen Threaded Binary Tree. Die Knoten im Splay-Baum sind bereits nach Nutzungshäufigkeit sortiert. Obwohl zusätzliches Threading von Baumblättern mehr CPU-Zeit erfordern kann, kann es daher Speicher sparen.

Um die Beschleunigung kürzlich verwendeter Daten im Speicher besser zu verstehen, können Sie unter diesem Link ein Beispiel einer Live-VM-Migration erkunden.

Verbessern Sie die Scangeschwindigkeit der verknüpften Liste

Wie bereits erwähnt, bieten verknüpfte Listen die schnellste Lösung zum Schreiben von Daten. Ihre Scangeschwindigkeit ist gut, aber langsamer als die Scangeschwindigkeit im Array.

Ich habe dieses Problem im vorherigen Artikel als Datenlokalität beschrieben. Da sie den binären Bäumen jedoch ähnlich sind, bieten verknüpfte Listen Verbesserungspotenzial. Durch das Aufrollen verknüpfter Listen können Sie mehr Daten in jedem Knoten der Liste speichern. Dadurch wird Speicher auf dem nächsten Zeigerknoten gespart und manchmal wird die Leistung verbessert, vorausgesetzt, die Größe des Elements passt zur CPU-Cache-Zeile:

Die Grundidee bleibt unverändert, aber die Darstellung der Liste im Speicher wird geändert.

Es wird sich in vielerlei Hinsicht ändern. Nachfolgend sind zwei Optionen aufgeführt:

Diese Verbesserungen erhöhen die Leistung von verknüpften Listen, erhöhen jedoch die Komplexität des Codes. Bei Festplattenoperationen mit einer verknüpften Liste kann ein entrollter Knoten mehr Elemente haben. Um die Funktionsweise zu verstehen, stellen Sie sich am besten eine verknüpfte Liste von Arrays vor.

Im Code müssen wir die Strukturbeschreibung ändern und von nun an jedes Element im Array der Struktur lesen oder schreiben:

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

Liste überspringen

Die Skip-Liste ist eine Methode, um die Geschwindigkeitseigenschaften von Suchelementen in einer verknüpften Liste zu verbessern. Diese Art von verknüpfter Liste speichert einen Schlüssel zum Sortieren der verknüpften Liste und enthält zusätzliche Zeiger, um Knoten effizienter zu lokalisieren als bei einem einfachen Scanvorgang.

Zusätzliche Knoten verbessern die Geschwindigkeit beim Durchlaufen zwischen Knoten in einer Skip-Liste. Es funktioniert wie eine binäre Suche. Im Gegenteil, es dauert länger, neue Elemente hinzuzufügen. Daher müssen Skip-Listen einen Schlüssel haben. Anwendungen können eine beliebige Anzahl von Ebenen erstellen, um die Geschwindigkeitseigenschaften zu verbessern. In den meisten Fällen ist es besser, etwas weniger oder ungefähr die gleiche Anzahl von Ebenen in der Höhe des Baums zu haben. (Sehen Sie sich das Bild oben an.)

Bei der Suche startet eine Anwendung auf der höchsten Ebene, da dies der schnellste Weg ist. Wenn der nächste Schlüssel erkannt wird, steigt sie auf eine niedrigere Ebene ab, bis der gewünschte Knoten gefunden wird.

Dieser Prozess führt zu einer Zeitkomplexität von O(log(n)). Beispielsweise ergibt die Verwendung von 4 Ebenen für eine Skip-Liste mit 16 Knoten, 20 Ebenen für 1 Million Knoten und 32 Ebenen für 4 Milliarden Knoten eine ähnliche Zeitkomplexität wie der RB-Baum.

Aus folgenden Gründen ist die Skip-Liste besser:

• Einfache Implementierung. Trotz der ähnlichen Eigenschaften wie der RB-Baum ist es viel einfacher zu implementieren und zu warten.

• Hohe Effizienz beim Anhängen neuer Knoten an das Ende der Sprungliste.

• Das Erstellen einer threadsicheren Implementierung einer Skip-Liste ist einfacher als das Erstellen eines Baums.

Lassen Sie uns die Umsetzung dieses Konzepts erkunden!

Strukturknoten:

 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;

Funktion zum Erstellen von Knoten:

 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; }

Während des Einfügens umfasst die Aufgabe das Erkennen des richtigen Speicherorts für den Knoten und das Bestimmen der Anzahl der Ebenen, die mit diesem Knoten verbunden werden sollen. Die Verwendung einer Zufallsfunktion zum Bestimmen der Ebenen vereinfacht den Vorgang für jeden neuen Knoten. Im Durchschnitt weist diese Funktion in 50 % der Fälle die zweite Ebene zu, in 25 % der Fälle die dritte Ebene und so weiter. Diese Methode minimiert die Zugriffszeit auf den Speicher zum Neuausgleich von Elementen.

 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; } } }

Funktion zum Suchen von Knoten:

 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; }

Eine Benchmark-Funktion zum Testen der Leistung einer verknüpften Liste, einer Skip-Liste und des RB-Baums. Die als Schlüssel verwendeten Werte werden als Zweierpotenzen festgelegt. Der Wert ist für Testzwecke unerheblich.

 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);

Ergebnisse des Tests dieser Datenstrukturen anhand der sequentiell wachsenden Schlüssel:

Dies ist der beste Zeitpunkt zum Einfügen (wenn Sie eine einfache verknüpfte Liste nicht in Betracht ziehen) und eine recht schnelle Methode zum Suchen von Elementen.

Ergebnisse des Tests dieser Datenstrukturen mit den sequentiell abnehmenden Schlüsseln:

Das ist leicht zu verstehen: Diese Implementierung einer Skip-Liste hat nur einen Kopfzeiger auf das erste Element. Das Hinzufügen von Knoten am Ende ist komplexer. Um diesen Ansatz zu ändern, können wir einen zweiten Zeiger (auf das Ende) hinzufügen oder die Skip-Liste umkehren (der Kopf zeigt auf die großen Werte). Das bedeutet, dass eine Skip-Liste eine effektive Datenstruktur für Protokolldaten wie Kafka-Streams ist. In diesem Fall kann sie mindestens doppelt so schnell wie der RB-Baum und einfacher zu implementieren sein.

Skip List reduziert die Einfügegeschwindigkeit von verknüpften Listen, bleibt jedoch bei sequentiellen Daten schneller als andere Datenstrukturen mit logarithmischer Zugriffszeit auf die Elemente, insbesondere wenn die Schlüssel sequentiell wachsen. Dennoch erschwert jedes sequentielle Wachstum der Schlüssel die Einfügungen in den Baum, da es viele Rotationen verursacht, um das Gleichgewicht des Baums aufrechtzuerhalten.

Es funktioniert nur dann effektiv, wenn der Wert während der gesamten Sequenz zunimmt (oder abnimmt). Wenn wir beispielsweise die Schlüssel zufällig anordnen, sind die Ergebnisse anders:

Wie man sieht, hat die Verteilung der Werte keinen signifikanten Einfluss auf die Geschwindigkeitseigenschaften des RB-Baums, sie beeinflusst jedoch erheblich die Leistung der Sprungliste.

Schlussfolgerungen

Heutzutage organisieren unsere Anwendungen Daten im Speicher oder auf der Festplatte möglicherweise auf unterschiedliche Weise. Karten und Listen spielen eine wichtige Rolle bei der Anordnung von Daten in unterschiedlicher Reihenfolge für unterschiedliche Zwecke. Diese Strukturen gewährleisten ausreichende Leistung, Ressourceneffizienz und Leistungsfähigkeit.

Manchmal reicht das für unsere Anforderungen nicht aus und die Anwendung muss in den kritischen Teilen geändert werden, um optimaler zu sein. In manchen Fällen kann die Verwendung geeigneterer Datenstrukturen von Vorteil sein, wie etwa Bäume für inexakte Übereinstimmungen oder Speichereinsparungen. In anderen Fällen sind Verbesserungen des Algorithmus von Vorteil, wie etwa die Verwendung asynchroner Methoden zur Verbesserung der Leistung einzelner Threads.

Wenn alle anderen Optionen ausgeschöpft sind, bleibt nur noch die Anpassung der Datenstruktur und der Nutzungsmethodik. Es gibt Beispiele für einige Änderungen der Datenstruktur, um diese für eine praktisch spezifische Aufgabe besser geeignet zu machen.

Während eine verknüpfte Liste in erster Linie eine Nur-Schreiben- und Sequenz-Scan-Datenstruktur ist, kann sie besser optimiert werden als der RB-Baum und bleibt auch in einem Nur-Schreiben-Fall effizient. Eine Verbesserung bestimmter Eigenschaften kann sich jedoch auf andere auswirken. Daher ist es am besten, das Wichtige zu priorisieren und das Unwichtige zu verwerfen.