Arrays

De miljoenste waarde van een array lezen kost één stap, maar een nieuwe waarde vooraan dezelfde array zetten verplaatst een miljoen waarden.

Wat een gegevensstructuur is

Een programma met een namenlijst, een wachtrij afdruktaken of een prijzentabel moet die gegevens ergens opslaan en vragen erover beantwoorden: wat is het derde item, staat deze naam in de lijst, welke taak is de volgende? Een gegevensstructuur is een manier om gegevens op te slaan samen met de methoden die zulke vragen beantwoorden. De cursus 6.006 van MIT onderscheidt hier twee ideeën. De interface zegt welke bewerkingen je mag vragen, zoals ‘geef het item op positie i’ of ‘voeg een item achteraan toe’. De gegevensstructuur bepaalt hoe die bewerkingen werkelijk in het geheugen worden uitgevoerd. Achter één interface kunnen verschillende gegevensstructuren zitten, die enorm in snelheid kunnen verschillen.

In deze cursus tel je stappen, zoals bij algoritmen, om twee structuren zonder stopwatch te vergelijken. In dit hoofdstuk is een stap één geheugencel lezen of schrijven. In het lab hieronder zie je de telling.

Eén blok cellen naast elkaar

Een array slaat waarden op in één aaneengesloten geheugenblok, elke waarde in een cel van gelijke grootte, genummerd vanaf 0. Die indeling maakt arrays snel leesbaar. Als het blok op adres s begint en elke cel c bytes inneemt, staat a[i] op adres s + i × c. De computer berekent dit met één vermenigvuldiging en één optelling en springt er direct heen, of i nu 3 of 3 000 000 is. De MIT-notities geven voor ‘get at(i)’ en ‘set at(i, x)’ op een array Θ(1): de kosten groeien niet met de lengte.

Dezelfde indeling maakt veranderingen in het midden traag. Stel dat de array 7, 3, 9, 4, 6 bevat en je 1 vooraan wilt zetten. Vóór 7 is geen opening, dus elke waarde moet eerst één cel naar rechts, vanaf de laatste zodat niets wordt overschreven. Dat zijn 5 verplaatsingen en 1 schrijfactie: 6 stappen. De voorste waarde verwijderen is het spiegelbeeld: lees haar en verplaats de andere 4 waarden één cel naar links. Invoegen op positie i in een array van n waarden kost n − i verplaatsingen plus één schrijfactie; vooraan is dus de slechtste plek en achteraan de beste.

Als het blok vol is

Een geheugenblok heeft een vaste grootte. Wat gebeurt er als je een waarde toevoegt terwijl elke cel bezet is? De array moet een nieuw, groter blok aanvragen en elke waarde kopiëren voordat de nieuwe kan worden geschreven. In het lab kost push op het volle blok van 5 waarden 5 kopieën en 1 schrijfactie. Als de array telkens maar één cel zou groeien, zou elke push alles kopiëren en zouden n pushes ongeveer n²/2 kopieën kosten.

De oplossing uit de MIT-notities is in grote stappen groeien, bijvoorbeeld verdubbelen. Vanaf capaciteit 1 worden kopieën gemaakt bij 1, 2, 4, 8 en 16 waarden. Zo kosten 17 pushes in totaal 1 + 2 + 4 + 8 + 16 = 31 kopieën, minder dan 2 per push. Eén push kan nog traag zijn, maar over elke lange reeks pushes zijn de gemiddelde kosten per push constant. Dit heet geamortiseerde Θ(1)-tijd. Een JavaScript-array gedraagt zich van buitenaf zo: MDN beschrijft arrays als aanpasbaar in grootte en push en pop werken aan het einde, de goedkope kant.

const a = [7, 3, 9, 4, 6];
console.log(a[3]);      // 4, one step
a.push(8);              // cheap: the end
a.unshift(1);           // every value moves one cell right
console.log(a.join(" ")); // 1 7 3 9 4 6 8