whiteMocca/Shutterstock.com
Memoization är en programmeringsteknik som accelererar prestanda genom att cacha returvärdena för dyra funktionsanrop. En & # 8220; memoiserad & # 8221; funktionen kommer omedelbart att mata ut ett förberäknat värde om det ges ingångar som det har sett tidigare.
Memoization är en specifik form av cachning som lämpar sig för scenarier där en kostsam funktion körs upprepade gånger, ibland med samma argument. Förutsatt att funktionen är ren så att den alltid producerar samma värde från en viss uppsättning ingångar kan memoing av den öka effektiviteten och minska bortkastade CPU-cykler.
Du kommer oftast att stöta på memoisering på funktionella programmeringsspråk. Tekniken har dock bred nytta. Det är ett abstrakt begrepp som du kan införliva i valfri rekursiv kod. Vi använder JavaScript för den här artikeln, men du kan skriva om exemplen till ditt arbetsspråk.
Ett enkelt exempel
Här & # 8217; en enkel funktion som genererar ett visst heltal:
const factorial = n = & gt; & # 123; om & # 40; n === 0 & # 41; retur 1; annars återvänder & # 40; faktiskt & # 40; n – 1 & # 41; * n & # 41 ;; & # 125 ;;
Faktorberäkningen är rekursiv, som faktoria () kallar sig inom det andra villkoret. Beräkningen är också ren, eftersom ett givet värde på n alltid returnerar samma värde. factorial (5) är 120, oavsett programmets tillstånd.
Annonsering
På grund av funktionens rekursiva natur beräknar fakturan för flera stora antal bortkastade operationer:
konst x = faktoria & # 40; 100 & # 41 ;; const y = faktoria & # 40; 50 & # 41 ;;
Alla beräkningar som behövs för att beräkna y utfördes redan som en del av beräkningen av x. Om factorial () cachade dess ingångar och deras motsvarande utdata, kunde beräkningen av y påskyndas betydligt.
Memorera faktorfunktionen
Här är ett grundläggande tillvägagångssätt som memorerar factorial () -funktionen:
const cache = & # 123 ; & # 125 ;; & nbsp; const factorial = n = & gt; & # 123; & nbsp; om & # 40; cache & # 91; n & # 93; & # 41; & # 123; returcache & # 91; n & # 93 ;; & # 125; & nbsp; låt värde; om & # 40; n === 0 & # 41; värde = 1; annars värde = & # 40; faktiskt & # 40; n – 1 & # 41; * n & # 41 ;; & nbsp; cache & # 91; n & # 93; = värde; returvärde; & nbsp; & # 125 ;;
Nu finns det ett cache-objekt som faktoria () använder för att registrera utdata. Varje gång funktionen anropas kontrollerar den först om den tidigare har sett ingången n. Om den har det kan den kortsluta omedelbart och returnera det cachade värdet. Annars fortsätter den rekursiva beräkningen som normalt, men efterföljande körningar med samma nummer kommer att snabbas upp.
Nu kommer databehandling av faktoria (50) efter faktoria (100) att bli mycket effektivare. Faktorn 50 skulle beräknas som en del av faktorn 100, så att funktionen kunde returnera värdet nästan omedelbart.
En mer allmän lösning
Medan ovanstående kod fungerar är den specifik för factorial () -funktionen. Om du använde andra liknande funktioner måste du manuellt lägga till cachekoden till var och en.
En mer allmän lösning låter dig slå in alla funktioner med en högre ordningsfunktion som ger memoizing-funktion:
const memoize = fn = & gt; & # 123; & nbsp; const cache = & # 123; & # 125 ;; & nbsp; återvänd & # 40; … args & # 41; = & gt; & # 123; const argsString = JSON.stringify & # 40; args & # 41 ;; om & # 40;! cache & # 91; argsString & # 93; & # 41; & # 123; cache & # 91; argsString & # 93; = fn & # 40; … args & # 41 ;; & # 125; returnera cache & # 91; argsString & # 93 ;; & # 125; & nbsp; & # 125 ;;
Nu kan du justera den ursprungliga funktionen ():
const factorial = memoize & # 40; n = & gt; & # 123; om & # 40; n === 0 & # 41; retur 1; annars återvänder & # 40; faktiskt & # 40; n – 1 & # 41; * n & # 41 ;; & # 125; & # 41 ;; Annons
Genom att förpacka factorial () med memoize () får den automatiska memoization-möjligheter. Omslagsfunktionen returnerar en ny funktion som avlyssnar alla samtal till faktoria (), skärper deras argument och kontrollerar om de har sett tidigare. Om de har det återanvänds det tidigare returvärdet utan att anropa den verkliga funktionen alls. När nya argument visas aktiveras funktionen och dess utdata läggs till cachen.
Omslaget använder JavaScript-viloparametersyntaxen för att acceptera ett varierande antal argument. Det betyder att det fungerar med alla JavaScript-funktioner. Detta tillvägagångssätt använder JSON.stringify () för att skapa strängrepresentationen av argumenten, så försiktighet bör iakttas om du anropar en funktion med komplexa objekt, som inte kan representeras fullt ut som JSON.
När ska man inte använda memoization?
Memoization kan ge betydande prestandaförbättringar, särskilt för matematiskt tunga operationer. Det är dock ingen teknik att använda överallt. Inte alla funktioner bör memoiseras, eftersom du i vissa fall kan skada prestanda.
Genom att slå in en funktion med memoize () tvingar du en jämförelse av ingångsargumenten varje gång den funktionen kallas. Detta i sig kommer att ta lite CPU-tid. Exempelomslaget ovan kör JSON.stringify () varje gång som funktionen anropas och lägger till en ny overhead.
Memoisering är lämplig för funktioner där det finns stora chanser att samma ingångsvärden kommer att ses regelbundet. Om du sällan anropar en funktion med samma argument kommer cache-träffar att vara sällsynta och du kan tappa prestanda till argumentserialisering och jämförelse. Att behålla cachen ökar också minnesanvändningen, eftersom alla tidigare in- och utgångar måste behållas.
Du bör därför utvärdera varje funktions roll i ditt program innan du bestämmer dig för att memorera. Jämför prestanda med och utan anteckningar. Ibland kan det visa sig mer fördelaktigt att lita på webbläsarens egna optimeringar.
Annons
Slutligen, kom ihåg att vissa funktioner inte kan memoreras. Tekniken fungerar bara med rena funktioner & # 8212; om din funktion når ut till globala variabler eller något annat applikationstillstånd, bör den inte memoiseras!
const functionUsingGlobalState = n = & gt; & # 123; om & # 40; n === window.scrollY & # 41; återvänd sant; annars returnerar funktionen AnvändaGlobalStat & # 40; n – 1 & # 41 ;; & # 125;
Att memorera funktionen ovan kan ge oväntade resultat efter den första körningen. Värdena på n kommer att cachas med hjälp av originalfönstret.scrollY version. Memoization-omslaget returnerar den cachade utmatningen, även om window.scrollY har ändrats.
Sammanfattning
Memoization är en form av cachning som påskyndar prestanda för repetitiv rekursiv operationer. Det är en funktionell programmeringsteknik som kan implementeras som ett generiskt omslag för alla rena funktioner.
Du kommer oftast att stöta på memoisering i ofta kallade funktioner som utför beräkningsmässigt tunga operationer. Det hjälper till att undvika slöseri genom att ta bort behovet av att beräkna värden som redan har producerats som en del av ett tidigare samtal.
Fördelarna med memoization kommer att bli mindre uppenbara i funktioner som är enkla att börja med eller sällan anropas. I vissa fall kan felaktig användning av memoering faktiskt skada prestanda, så memoera inte alla funktioner i din applikation blint.