Array

Uit Wikipedia, de vrije encyclopedie
Ga naar: navigatie, zoeken

Een array (Engels voor rij of reeks) is bij het programmeren van computers een datastructuur die bestaat uit een lijst van elementen. Ieder element in een array heeft een unieke index waarmee dat element aangeduid kan worden.

Hoewel een array een eenvoudige datastructuur is, kunnen er krachtige dingen mee gedaan worden. Vectoren in een meerdimensionale ruimte bijvoorbeeld kunnen met een eenvoudige array worden geïmplementeerd en in een taal als Perl kunnen bijvoorbeeld arrays van references naar hashes (associatieve arrays) worden gemaakt.

De eenvoudigste implementatie van een array, zoals in C gebeurt, is een reeks opeenvolgende geheugencellen.

Pure arrays[bewerken]

Een pure array heeft als index een verzameling van opeenvolgende integers, of een ander discreet datatype. De elementen van zo'n array worden meestal opeenvolgend in het geheugen opgeslagen. Een voorbeeld van een taal met pure arrays is C. In C, en de meeste andere talen met pure arrays, wordt de extra eis gesteld dat arrays homogeen zijn, wat wil zeggen dat alle elementen van de array van hetzelfde type zijn.

Wanneer arrays geïmplementeerd worden als een reeks van opeenvolgende geheugencellen, wordt het adres van het i-de element in een homogene array gegeven door b+(i-1)*s, waarbij b het beginadres van de array is en s de grootte (in geheugeneenheden) van ieder element in de array. De efficiëntie van de indexatie is dus O(1).

Het voordeel van (homogene) pure arrays is dus dat het indexeren erg efficiënt geïmplementeerd kan worden. Het nadeel is dat iedere array een enkel ononderbroken geheugenblok nodig heeft. Dit kan leiden tot fragmentatie van het geheugen.

Het is ook mogelijk om een array te implementeren met behulp van een gelinkte lijst in plaats van een opeenvolgend geheugenblok. De efficiënte is in dit geval O(x) in plaats van O(1). De nadelen van zo'n implementatie zijn dat het indexeren minder efficiënt is en dat er meer geheugen nodig is (minimaal één extra pointer voor ieder element). Het voordeel is dat zo'n implementatie flexibeler is: arrays hoeven niet homogeen te zijn, en kunnen ook dynamisch zijn.

Associatieve arrays[bewerken]

1rightarrow blue.svg Zie Associatieve array voor het hoofdartikel over dit onderwerp.

Voor een associatieve array gelden minder restricties op de index: het is toegestaan om niet-discrete waarden als index te gebruiken. Ook hoeft de index in veel talen met associatieve arrays niet homogeen te zijn: de indexwaarden hoeven niet van hetzelfde type te zijn. Voorbeelden van talen met associatieve arrays zijn PHP, Perl en JavaScript.

Associatieve arrays worden over het algemeen geïmplementeerd met behulp van hashtables en zijn in de praktijk altijd dynamisch.

Dynamische arrays[bewerken]

Een dynamische array kan van lengte veranderen. Dit kan impliciet gebeuren, door het toevoegen of verwijderen van elementen, of expliciet, met een speciale syntaxisconstructie (zoals het ReDim statement in Visual Basic). Andere talen die dynamische arrays ondersteunen zijn bijvoorbeeld Perl en Lisp.

Voorbeeld in C[bewerken]

Voorbeeld van een array van integers in de programmeertaal C:

int array[2]; // Een array met 2 integers (geen van de elementen hebben (nog) een waarde)
array[0] = 1; // Geeft het allereerste element in de array waarde 1
array[1] = 3; // Geeft het tweede element in de array waarde 3

Hierbij is de naam van de array "array" en de opgeslagen waarden in de array zijn 1 en 3. Deze waarden zijn nu te gebruiken met behulp van array[0] en array[1]. In sommige programmeertalen (bijvoorbeeld C of PHP) is 0 de index van de eerste waarde in de array, in andere programmeertalen is dit 1. Er zijn ook talen waar men zelf de ondergrens kan bepalen (bijvoorbeeld Perl).

Meer-dimensionele arrays[bewerken]

Een 2-dimensionale array waarbij elk element in de array een array op zich is

Het hierboven genoemde voorbeeld is een 1-dimensionale array (ook wel vector of scalair genoemd). In veel programmeertalen is het ook mogelijk om meer-dimensionale arrays te gebruiken. Een twee-dimensionale array wordt ook wel een matrix genoemd.

Er bestaan verschillende manieren om een multidimensionale array te representeren in een computergeheugen. Eén mogelijkheid is om een array te maken met pointers naar andere arrays (zie afbeelding). Als we een tweedimensionale array beschouwen als een tabel met rijen en kolommen, dan zijn de rijen afzonderlijke arrays. Een voordeel hiervan is dat de rijen niet allemaal even lang hoeven te zijn (de zgn. 'jagged array'); de lengte kan zelfs dynamisch aangepast worden.

Een andere mogelijkheid is om de rijen achter elkaar op te slaan als elementen in een eendimensionale array. Een tweedimensionale array met m rijen en n kolommen wordt dan een eendimensionale van grootte m×n. De eerste rij is dan opgeslagen in elementen 1 tot en met n, de tweede in elementen n+1 tot en met 2n, enz. Het voordeel van deze representatie is snelheid: alle elementen staan bij elkaar in het geheugen, er hoeven geen pointers gevolgd te worden naar andere delen van het geheugen.

In beide gevallen is de uitbreiding naar drie- en meer-dimensionale arrays mogelijk door een array van tweedimensionale arrays te maken, enz.

Array-ondersteuning in enkele talen[bewerken]

Een lijstje van array-ondersteuning in enkele talen:

C
Enkel pure, homogene, niet-dynamische arrays. Deze zijn noodzakelijk geïmplementeerd als een opeenvolgend blok geheugen omdat C een één-op-één mapping tussen arrays en pointermanipulatie specificeert.
Pascal
Enkel pure, homogene, niet-dynamische arrays. In tegenstelling tot bij C zijn deze niet te manipuleren met behulp van pointers.
Perl, Python, Ruby
Zowel pure, heterogene, dynamische arrays (lists) als associatieve arrays (hashes).
C++ en Java
Pure, homogene, niet-dynamische arrays. C++ biedt ondersteuning voor associatieve arrays via STL en Java via de standaard library. Verder is het in beide talen mogelijk om heterogene arrays na te bootsen met behulp van containers. Arrays in Java zijn in feite objecten.
PHP, JavaScript en Lua
Enkel associatieve arrays, die echter ook als gewone arrays gebruikt kunnen worden.
Pure functionele programmeertalen zoals bijvoorbeeld Haskell
Geen arrays. Omdat pure functionele programmeertalen geen side-effects toestaan heeft het geen zin om arrays te gebruiken. Gelijksoortige functionaliteit wordt verkregen met behulp van lijsten en tupels.
Niet-pure functionele talen zoals bijvoorbeeld OCaml
Pure, homogene, dynamische arrays en associatieve arrays.

Zie ook[bewerken]

Bronnen, noten en/of referenties
  • Programming Language Design Concepts, David A. Watt, John Wiley & Sons, 2004, ISBN 0470853204
  • Programming Language Pragmatics, 2e ed., Michael L. Scott, Elsevier, 2006, ISBN 0126339511
  • Data Structures with Abstract Data Types and Modula-2, Stubbs en Webre, Brooks/Cole, 1987, ISBN 0534073026