August 21, 2025

STP077: Liste von Listen

57 minutes

Als der inoffizielle Wikipedia-Vorlesepodcast sehen wir es als unsere Pflicht, eine Eigenheit dieser anzusprechen: nämlich Listen von Listen, obwohl es uns eigentlich um Listen im Speicher geht.

Shownotes

Rückbezüge:

fundamentale Datenstrukturen siehe STP071: Felder/Listen, assoziative Datenfelder (Maps), Graphen

Frage: Wie stellt man solche Datenstrukturen im Speicher dar? Gibt es darauf überhaupt die eine richtige Antwort?

algorithmische Komplexität siehe STP029: Liste mit n Elementen ausdrucken in O(n), aber sortieren in O(n log(n)) bis O(n^2)

Speicherallokation siehe STP047 und Speicherschutz siehe STP019: Bezug wird gleich klar werden

Listen kann man als verkettete Liste darstellen

klassisches Studienobjekt in Erstsemester-Datenstrukturen-Vorlesungen

intuitiv verständlich: Parallele zu segmentierten Halsketten

wahlweise einfach oder doppelt verkettet

effiziente Operationen: Einfügen am Ende, Entfernen am Ende

ineffiziente Operationen: Einfügen in der Mitte, Wahlzugriff/Suche

Vergleichstabelle mit Darstellung der Zeiteffizienz

alles in allem durchwachsene Performance -> geht es besser?

alternative Strategie: interne Darstellung der Liste als balancierter Baum (oder evtl. "ausgeglichener Baum")

außerdem Link auf die englische Wikipedia, die nicht nur unbalancierte, sondern auch balancierte Bäume zeigt

kann nur sortierte Listen darstellen

Idee: Wurzelknoten hat das Median-Element, dann der linke Ast alle kleineren und der rechte Ast alle größeren Elemente

im Grunde alle gängigen Operationen mittelschnell: Wahlzugriff/Suche, Einfügen an beliebigen Stellen, Entfernen von beliebigen Stellen (Änderungen erfordern im Allgemeinen ein Austarieren des Baumes)

große Variation von Implementationsstrategien für dieses Balancieren -> hier nicht

verkettete Listen und balancierte Bäume sehen auf dem Papier ziemlich effizient aus, haben aber in ihrer reinen Form pathologisch schlechtes Speicherverhalten

hoher Platzverbrauch: z.B. bei einfach bzw. doppelt verketteten Listen muss zu jedem Element müssen noch eine bzw. zwei Speicheradressen abgelegt werden

hohe Allokationslast: wenn nicht eine Arena oder ein vergleichbarer Small Object Allocator verwendet wird

schlechte Lokalität: beim Durchlaufen nachfolgender Elemente werden im schlimmsten Fall ständig unterschiedliche Speicherseiten getroffen, was fortlaufend Seitenfehler verursachen kann

in der Praxis mit Abstand dominante Implementationsstrategie: dynamische Felder

Beobachtung: Einfügen oder Löschen an beliebigen Stellen wird kaum gemacht; man hängt eher mehrmals ans Ende an und sortiert dann, falls nötig

Idee: Optimieren auf Einfügen am Ende bei möglichst optimalen Speicherverhalten

Umsetzung: einfaches Feld (ein fortlaufendes Stück Speicher, in dem mehrere Elemente hintereinander abgelegt werden) mit aktuellem Füllstand N und Kapazität K

Einfügen ans Ende: normalerweise einfach N erhöhen; wenn N nicht in K passt, größeren Speicher reservieren, alles hinüberkopieren und die alten Speicherallokation verwerfen

Löschen vom Ende: einfach N reduzieren, keine Deallokation erforderlich

Einfügen am Anfang oder in die Mitte: alle Elemente dahinter nach hinten verschieben

nahezu optimales Speicherverhalten von dynamischen Feldern begründet ihre Dominanz

Platzverbrauch: neben der Speichergröße der Elemente selber nur zwei Zahlen (N und K)

Allokationslast: Vergrößern geht für gewöhnlich in exponentiellen Schritten und wird damit für wachsende Listen immer seltener nötig

Lokalität: lineare Suche durch die Liste geht linear durch den Speicher hindurch -> folgende Speicherseiten können vom Prozessor oft schon auf Verdacht vorgeladen werden

trotzdem: die anderen Datenstrukturen haben auch ihre Berechtigung (z.B. modifizierte balancierte Bäume als Basis für Datenbank-Indizes)

Xyrill will auch noch auf analoge Weise über Maps und Graphen reden -> weiter in STP079

...more

View all episodes

By Xyrillian Noises