Memoisation

Från Wikipedia
Hoppa till: navigering, sök

Memoisation är en teknik för att optimera datorprogram som innebär att resultatet av uträkningar som sker medan programmet körs lagras i en tabell. Om en beräkning som redan har utförts efterfrågas, kan tabellen läsas av istället för upprepa hela den potentiellt tidskrävande uträkningen. Tekniken kan jämföras med cachning av minne.

Speciellt handlar memoisation om att associera funktionsargument med funktionsvärde för enskilda funktioner, oftast genom att spara associationerna i en hashtabell. Tekniken är bara tillämpbar på funktioner utan sidoeffekter, och används därför oftast inom funktionell programmering där sådana funktioner är vanliga eller kan markeras explicit.

I programspråk med stöd för högre ordningens funktioner kan man skriva en funktion som omvandlar godtyckliga funktioner till memoiserade funktioner. I övriga språk måste memoisation implementeras separat för varje funktion.

Tekniken är också allmänt känd inom algoritmteorin som dynamisk programmering, vilket är ett effektivt lösningssätt för vissa typer av optimeringsproblem. Delresultat lagras och återanvänds istället för att beräknas på nytt varje gång de behövs. När tekniken används praktisk leder den till snabbare program men kräver istället mer datorminne. En betydande andel viktiga optimeringsproblem går i praktiken inte att lösa utan dynamisk programmering.