Optimering (datalogi)

For alternative betydninger, se Optimering. (Se også artikler, som begynder med Optimering)

Inden for datalogi er optimering at ændre et stykke software eller en algoritme for at effektivisere visse parametre.

Software kan kan f.eks. ændres således at det afvikles hurtigere, bruger mindre hukommelse, bruger mindre processortid eller mindre strøm.

Ved optimering af algoritmer fortages ændringer til fordel for algoritmens tidskompleksitet.

Det vil ikke altid være muligt at forbedre én parameter, uden at forringe en anden. Derfor vil en optimering ofte lede til en afvejning af softwarens parametre. Afvejningen kan ske med henblik på at optimere softwaren til bestemte platforme, computersystemer eller brugere af softwaren. Således vil et stykke software ofte optimeres på ganske få parametre på bekostning af andre parametre. Herunder er de mest hyppige optimeringer og deres afvejninger.

Man kan ofte afvikle et program hurtigere på bekostning af hukommelsesforbruget. Dette kan f.eks. ske ved at lagre resultaterne af bestemte udregninger til senere brug, i stedet for at genberegne dem. Denne type optimering kan bruges ved beregningstunge opgaver som kræver høj afviklingshastighed og høj beregningspræcision som f.eks. computergrafik, computerspil eller simulationer.

Ved nedsættelse af strømforbruget kan afviklingen af softwaren også være langsommere.

I visse tilfælde er det ikke nødvendigt at alle beregninger er præcise. Man kan, til fordel for afviklingshastigheden, udføre mindre præcise eller endda direkte upræcise beregninger. Dette anses som et alternativ til at lagre resultaterne fra en mere præcis (og dermed ofte langsommere) beregning, i situationer hvor softwaren samtidigt optimeres med henblik på at mindske hukommelsesforbruget.

Nogle beregningsopgaver kan udføres på forskellige måder med forskellige afviklingshastigheder. Ændres en beregning således den afvikles hurtigere men har samme resultat, kaldes det en optimering ved reduktion.

For eksempel kan en algoritme til beregning af summen af heltal fra 1 til n skrives således i pseudokode:

function sum(n) {
  int sum = 0;
  for (int i = 0; i <= n; i++) {
    sum = sum + i;
  }
  return sum;
}

Det viser sig at denne algoritme vil tage længere tid at afvikle jo højere værdi n har. I stedet kan denne algoritme reduceres til følgende ækvivalente algoritme:

function sum(n) {
  return n * (1+n) / 2;
}

I dette eksempel antages det dog at systemet som skal afvikle algoritmen er hurtigere til at udføre multiplikation og division end gentagelse af addition, hvilket ikke altid er tilfældet. Derfor kan der ved optimering med fordel tages højde for hvilket system softwaren skal afvikles på.

Det er ofte meget hurtigere at genkalde lagrede værdier end det er at genberegne dem. Dette gælder i følgende eksempel ved beregning af fibonacci-tallene: Herunder ses hvordan man kan beregne ethvert fibonacci-tal rekursivt. Bemærk at grundet algoritmens opbygning, vil det kræve flere rekursioner for højere værdier af n.

function fibonacci(n) {
  if (n==0 or n==1) {
    return 1;
  } else {
    return fibonacci(n-1) + fibonacci(n-2);
  }
}

Dette kan optimeres i forhold til tidsforbruget, ved at minimere antallet af rekursioner. Dette gøres i kodeeksemplet herunder ved at lagre enhver ny beregning, som så kan genkaldes ved en senere beregning.

fib = [1, 1, 0, 0, 0, ...]; //Lager: Den n'te indgang lagrer fib(n). Hvis 0 skal værdien beregnes.

function fibonacci(n) {
  if (fib[n] == 0) {
    fib[n] = fibonacci(n-1) + fibonacci(n-2);
  }
  
  return fib[n]
}

I dette eksempel begrænses n dog til størrelsen på lageret. I pseudokoden er lageret angiveligt uendeligt stort, hvilket det ikke vil være på en fysisk computer.

Spire Denne artikel om datalogi eller et datalogi-relateret emne er en spire som bør udbygges. Du er velkommen til at hjælpe Wikipedia ved at udvide den.