STP077: Liste von Listen

<p>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.</p><h2>Shownotes</h2><ul>
<li>
<p>Rückbezüge:</p>
<ul>
<li>fundamentale Datenstrukturen siehe STP071: Felder/Listen, <del>assoziative Datenfelder (Maps), Graphen</del></li>
<li>Frage: Wie stellt man solche Datenstrukturen im Speicher dar? Gibt es darauf überhaupt die eine richtige Antwort?</li>
<li>algorithmische Komplexität siehe STP029: Liste mit <code>n</code> Elementen ausdrucken in <code>O(n)</code>, aber sortieren in <code>O(n log(n))</code> bis <code>O(n^2)</code></li>
<li>Speicherallokation siehe STP047 und Speicherschutz siehe STP019: Bezug wird gleich klar werden</li>
</ul>
</li>
<li>
<p>Listen kann man als <a href="de.wikipedia.org/w/index.php?title=Liste_(Date…)&oldid=253638160">verkettete Liste darstellen</a></p>
<ul>
<li>klassisches Studienobjekt in Erstsemester-Datenstrukturen-Vorlesungen</li>
<li>intuitiv verständlich: Parallele zu segmentierten Halsketten</li>
<li>wahlweise einfach oder doppelt verkettet</li>
<li>effiziente Operationen: Einfügen am Ende, Entfernen am Ende</li>
<li>ineffiziente Operationen: Einfügen in der Mitte, Wahlzugriff/Suche</li>
<li><a href="en.wikipedia.org/w/index.php?title=Template:Li… mit Darstellung der Zeiteffizienz</a></li>
<li>alles in allem durchwachsene Performance -> geht es besser?</li>
</ul>
</li>
<li>
<p>alternative Strategie: interne Darstellung der Liste als <a href="de.wikipedia.org/w/index.php?title=Balancierte… Baum</a> (oder evtl. "ausgeglichener Baum")</p>
<ul>
<li>außerdem Link auf <a href="en.wikipedia.org/w/index.php?title=Self-balanc… englische Wikipedia</a>, die nicht nur unbalancierte, sondern auch balancierte Bäume zeigt</li>
<li>kann nur sortierte Listen darstellen</li>
<li>Idee: Wurzelknoten hat das Median-Element, dann der linke Ast alle kleineren und der rechte Ast alle größeren Elemente</li>
<li>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)</li>
<li>große Variation von Implementationsstrategien für dieses Balancieren -> hier nicht</li>
</ul>
</li>
<li>
<p>verkettete Listen und balancierte Bäume sehen auf dem Papier ziemlich effizient aus, haben aber in ihrer reinen Form pathologisch schlechtes Speicherverhalten</p>
<ul>
<li>hoher Platzverbrauch: z.B. bei einfach bzw. doppelt verketteten Listen muss zu jedem Element müssen noch eine bzw. zwei Speicheradressen abgelegt werden</li>
<li>hohe Allokationslast: wenn nicht eine Arena oder ein vergleichbarer Small Object Allocator verwendet wird</li>
<li>schlechte Lokalität: beim Durchlaufen nachfolgender Elemente werden im schlimmsten Fall ständig unterschiedliche Speicherseiten getroffen, was fortlaufend Seitenfehler verursachen kann</li>
</ul>
</li>
<li>
<p>in der Praxis mit Abstand dominante Implementationsstrategie: <a href="en.wikipedia.org/w/index.php?title=Dynamic_arr… Felder</a></p>
<ul>
<li>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</li>
<li>Idee: Optimieren auf Einfügen am Ende bei möglichst optimalen Speicherverhalten</li>
<li>Umsetzung: einfaches Feld (ein fortlaufendes Stück Speicher, in dem mehrere Elemente hintereinander abgelegt werden) mit aktuellem Füllstand N und Kapazität K</li>
<li>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</li>
<li>Löschen vom Ende: einfach N reduzieren, keine Deallokation erforderlich</li>
<li>Einfügen am Anfang oder in die Mitte: alle Elemente dahinter nach hinten verschieben</li>
</ul>
</li>
<li>
<p>nahezu optimales Speicherverhalten von dynamischen Feldern begründet ihre Dominanz</p>
<ul>
<li>Platzverbrauch: neben der Speichergröße der Elemente selber nur zwei Zahlen (N und K)</li>
<li>Allokationslast: Vergrößern geht für gewöhnlich in exponentiellen Schritten und wird damit für wachsende Listen immer seltener nötig</li>
<li>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</li>
<li>trotzdem: die anderen Datenstrukturen haben auch ihre Berechtigung (z.B. modifizierte balancierte Bäume als Basis für Datenbank-Indizes)</li>
</ul>
</li>
<li>
<p>Xyrill will auch noch auf analoge Weise über Maps und Graphen reden -> weiter in STP079</p>
</li>
</ul>