kodehoved

Med introduktionen af .NET 2.0 fandt ArrayList en afløser i List<T>. Skønt ordet ”array” ikke længere indgår i navnet, er List<T> faktisk stadig baseret på Array, hvilket vi kan konstatere ved hjælp af Reflector.

De største fordele ved List<T> i forhold til ArrayList er typefastheden og en ganske betydelig performanceforbedring i forbindelse med håndtering af værdityper (value types). Typefastheden leder til simplere kode, da vi undgår at skulle undersøge type på og om nødvendig caste elementer, når vi piller dem ud af listen. Performanceforbedringen kommer af, at vi undgår at box/unboxe i forbindelse med værdityper.

Så for at gøre en lang historie kort: List<T> er langt at foretrække frem for ArrayList, så for at få mest ud af den, er det en god ide at se på, hvordan den er implementeret. Som nævnt er List<T> internt baseret på en Array. Det betyder, at skønt List<T> præsenterer en datastruktur uden fast størrelse, er dette blot en illusion. Når man opretter en List<T>, har den en størrelse, og når der er behov for mere plads, er typen således nødsaget til at oprette en ny, større struktur og flytte alle elementer til denne. Det er selvsagt ikke en billig operation.

Som udgangspunkt afsættes der faktisk ikke plads i en List<T>, hvilket man kan verificere ved at konstatere at Capacity indledningsvis sættes til 0. Så snart der tilføjes et element, afsættes der plads til 4 elementer, og herefter fordobles kapaciteten, hver gang behovet opstår. Det vil sige, at det femte element (og her tænker jeg ikke på filmen) resulterer i at Capacity stiger til 8, det niende element får Capacity til at stige til 16 og så fremdeles. Det betyder, at der for små lister kan spildes meget tid på disse interne omrokeringer, og derfor er det en god ide, at oprette sine List<T>-instanser med en passende kapacitet via den tilhørende constructor.

For meget store lister er dette overhead mindre betydende, men her kan man optimere pladsforbruget ved at sætte en passende kapacitet, så man kan undgå, at der afsættes for meget plads til referencer. Har man f.eks. en liste med 1,1 million navne, vil standardopførelsen gøre, at der afsættes plads til 2^21 eller 2.097.152 elementer. Så uanset hvad er det en god ide at sætte en indledende kapacitet, hvis man på nogen måde har mulighed for at komme med et kvalificeret gæt på den nødvendige kapacitet.

Mange implementeringer af en List-type er baseret på det, man kalder en hægtet listet (linked list), i hvilken brugeren har en reference til det første element i listen, og hvert element desuden har en reference til det efterfølgende element (eller null for sidste element i listen). En sådan implementering vil typisk tilbyde en Insert()- og en Add()-metode ganske som tilfældet er for List<T>. I dette tilfælde vil Insert() almindeligvis være særdeles effektiv, idet det kun kræver justering af to referencer at indsætte et element forrest i listen. Med mindre listen også gemmer en reference til det sidste element, vil det til gengæld være dyrt at indsætte elementer sidst i listen, da dette kræver, at vi løber hele listen igennem via referencerne i de enkelte elementer.

Sådan er det ikke med List<T>. Her forholder det sig faktisk lige omvendt. At tilføje et element via Add() er særdeles effektivt, men vil dog medføre et overhead, hvis kapaciteten skal udvides. Faktisk fremgår det af dokumentationen, at Add() som udgangspunkt er en O(1) operation. Skal listen udvides bliver det dog en O(n) operation.

Insert() er derimod en O(n) operation ifølge dokumentationen, men hvis vi tager et kig på implementeringen ved hjælp af Reflector (se nedenfor), ser vi, at dette faktisk ikke gælder, hvis Insert() resulterer i at elementet indsættes i slutningen af listen. I det tilfælde er Insert() stort set lige så hurtig som Add() – og i realiteten er der tale om O(1).

public void Insert(int index, T item)
{
   if (index > this._size) {
      ThrowHelper.ThrowArgumentOutOfRangeException(ExceptionArgument.index,
         ExceptionResource.ArgumentOutOfRange_ListInsert);
   }
   if (this._size == this._items.Length) {
      this.EnsureCapacity(this._size + 1);
   }
   if (index < this._size) {
      Array.Copy(this._items, index, this._items, index + 1, this._size - index);
   }
   this._items[index] = item;
   this._size++;
   this._version++;
}

Som det også fremgår af ovenstående, ligger Insert() naturligvis under for de samme restriktioner som Add() i det tilfælde, at kapaciteten skal udvides.

Så hvad kan vi lære af at se på implementeringen af List<T>? For det første, vil det som sagt være en god ide at vælge en passende kapacitet ved oprettelsen af sin liste for at undgå de tunge omallokeringer og det voldsomme overhead ved store lister. Dernæst kan vi konstatere, at i og med at List<T> ikke er implementeret som en hægtet liste, er Add() langt at foretrække frem for Insert(). Faktisk er omkostningerne ved sidstnævnte så store, at man virkelig kun skal bruge den som sidste udvej. Og sidst men ikke mindst, er der ingen grund til fortsat at bruge ArrayList.