memoisering

Memoisering er en programmeringsteknikk som forbedrer ytelsen ved å lagre resultater av dyre funksjonskall i en cache og bruke disse resultatene ved senere kall med samme inngang. For at memoisering skal være riktig, må funksjonen være deterministisk og i hovedsak ha få eller ingen bivirkninger.

En implementasjon bygger en cache der nøkkelen består av funksjonens argumenter. Før kalkulasjonen kjøres, sjekkes det om resultatet finnes i cachen. Hvis det gjør det, returneres det lagrede resultatet; hvis ikke beregnes det og lagres i cache for framtidige kall. Ofte brukes memoisering i rekursive eller dynamiske programmeringsproblemer, der samme subproblem oppstår flere ganger.

Fordeler inkluderer raskere kjøretid ved gjentatte inn- og utgaanger, spesielt i vekselvise rekursive ligninger. Ulemper inkluderer høyere minnebruk og risiko for at cache blir foreldet dersom data eller tilstander endres. Det krever at inn- og utdataene er egnet for rett hashing eller nøkkelbygging, og at man håndterer samtidige kall på en tråd-sikker måte om nødvendig.

Tilnærmingen blir ofte sett i sammenheng med dynamisk programmering og andre teknikker for å unngå gjentatte beregninger. Mange programmeringsspråk tilbyr innebygde eller tredjeparts løsninger for memoisering, ofte gjennom dekoratorer, wrapper-funksjoner eller spesialiserte cache-rammeverk.