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