Hoofdstuk 1 Flashcards
Op welke manieren kan je data structuren opverdelen? Leg ook alle onderverdelingen uit.
Dictionary vs container
Linear vs non-linear
Continuous vs linked
Wat zijn voordelen en nadelen van continuous datastructuren
De data ligt dicht bij elkaar dus kan snel opgevraagd worden (kan direct een hele blok naar het cache gekopieerd worden)
Nadelen:
De grootte moet op voorhand vast gelegd worden. Als de grootte moet aangepast worden kost dit veel, moet volledig over gekopieerd worden. Als er geen aaneengesloten stuk ruimte meer over is kan de datastructuur niet aangemaakt worden ook al is er genoeg ruimte.
Wat zijn de voor en nadelen van gelinkte structuren
Kan dynamisch aan gepast en uitgebreid worden. Geen aaneengesloten blok geheugen nodig dus kan altijd bijvoegen zolang er geheugen is.
Extra overhead door het opslaan van pointers.
What does caching allow you to exploit?
Locality.
Spatial locality, data that is close in memory has a higher chance of being used again (looping over continuous data structures)
Temporal locality: Data that has been used recently has a higher chance of being used again.
Kan een continue structuur non-linear zijn?
Ja bijvoorbeeld een heap. Deze is conceptueel niet linear maar is opgeslagen in continue vorm.
Linear vs non-linear slaagt op hoe het conceptueel wordt voorgesteld (Hoe je het zou tekenen) Continu vs linked is hoe het in het geheugen wordt opgeslagen.
