STP077: Liste von Listen
Season 1
Episode 77
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
Published on 3 weeks ago