Memoisering

Den aktuella versionen av sidan har ännu inte granskats av erfarna bidragsgivare och kan skilja sig väsentligt från versionen som granskades den 9 november 2021; verifiering kräver 1 redigering .

Memoization (Cache) ( eng. memoization from eng. memory och eng. optimization ) är ett exempel på att använda en cache i mjukvaruutveckling, i programmering, spara resultaten av exekvering av funktioner för att förhindra omberäkningar. Detta är en av de optimeringsmetoder som används för att påskynda exekveringen av datorprogram . Innan en funktion anropas kontrollerar den om funktionen har anropats tidigare:

om den inte anropas, anropas funktionen och resultatet av dess exekvering sparas;
om det anropas används det sparade resultatet.

Memoization kan användas för mer än att bara påskynda ett program. Till exempel används den i korsrekursiv top-down- parsning i en generaliserad top- down-analysalgoritm [1] .

Även om det är relaterat till cachelagring är memoisering en specifik typ av optimering som skiljer sig från cachelagringsmetoder som buffring och sidbyte.

Inom logiska programmeringsspråk kallas memoisering som tabulering.

Användningsexempel

Funktionen memoize() nedan lagrar resultaten av varje anrop till den mottagna funktionen som [nyckel:värde].

// En funktion som genererar en nyckel baserat på parametrarna const generKey = args => ( args . map ( x => ` ${ x . toString () } : ${ typeof ( x ) } ` ). join ( '| ' ) / / Resultat: "x1:nummer|x2:nummer|..." ); // Tar en funktion som en parameter const memoize = fn => { const cache = {}; return (... args ) => { // Genererar en nyckel för att lagra resultatet const key = generKey ( args ); constval = cache [ nyckel ] ; // Kontrollerar om det finns ett värde för den givna nyckeln och returnerar det om det finns om ( val ) return val ; // Lagrar resultatet av ett funktionsanrop const res = fn (... args ); cache [ nyckel ] = res ; // Returnerar resultatet return res ; }; };

Med den kan vi undvika att utföra om beräkningar om de redan har utförts.

// En funktion som hittar summan av tal från a till b const sumSeq = ( a , b ) => { console . log ( 'Beräkna summa' ); låt r = 0 ; för ( låt i = a ; i < b ; i ++ ) r += i ; returnera r ; }; // Memoize funktionen sumSeq const mSumSeq = memoize ( sumSeq ); konsol . log ( 'Första anropet mSumSeq(2, 5)' ); konsol . log ( 'Värde: ' + mSumSeq ( 2 , 5 )); // Skriver ut "9" till konsolkonsolen . log ( 'Andra anropet mSumSeq(2, 5)' ); konsol . log ( 'Från cache: ' + mSumSeq ( 2 , 5 )); // Skriver ut "9" till konsolkonsolen . log ( 'Call mSumSeq(2, 6)' ); konsol . log ( 'Beräknat: ' + mSumSeq ( 2 , 6 )); // Skriver ut "14" till konsolen

När funktionen mSumSeq( 2, 5 ) anropades igen, räknade inte programmet om summan, det kontrollerade förekomsten av värdet med tangenten [2:number|5:number] i cachen, och eftersom det redan hade skapats och tilldelades värdet 9 vid det första funktionsanropet, kommer detta värde att skickas till variabeln val från memoize() och returneras som ett argument till console.log().

Detta exempel visar den enklaste tillämpningen av memoization i programmering, så du kanske inte märker några betydande förändringar i arbetshastigheten, men denna optimeringsmetod kan avsevärt underlätta processorns arbete med laddade matematiska beräkningar.

Se även

Operation Strength Down är en optimering som ersätter dyra operationer med billigare motsvarigheter.
Uppslagstabellen är nyckeldatastrukturen som används vid memoisering .
En flugvikt (designmönster) är ett mönster som använder memoisering.
Dynamisk programmering - tillämpningar av memoiseringstekniker.
Lata datorer .

Länkar

Kodexempel hämtade från källan:

HowProgrammingWorks, Timur Shemsedinov - Github-förråd .

Anteckningar

↑ Norvig, Peter. Tekniker för automatisk memoisering med applikationer för kontextfri analys // Computational Linguistics. - 1991. - T. 17 , nr 1 . - S. 91-98 .