whiteMocca/Shutterstock.com
Memoisatie is een programmeertechniek die de prestaties versnelt door de geretourneerde waarden van dure functieaanroepen in de cache op te slaan. Een “gememoriseerd” functie zal onmiddellijk een vooraf berekende waarde uitvoeren als deze invoer heeft gegeven die hij eerder heeft gezien.
Memoization is een specifieke vorm van caching die zich leent voor scenario's waarin een kostbare functie herhaaldelijk wordt uitgevoerd, soms met dezelfde argumenten. Op voorwaarde dat de functie puur is, zodat deze altijd dezelfde waarde produceert uit een bepaalde set invoer, kan het onthouden ervan de efficiëntie verhogen en verspilde CPU-cycli verminderen.
U zult memovorming het vaakst tegenkomen in functionele programmeertalen. De techniek heeft echter een breed nut. Het is een abstract concept dat u in elke recursieve code kunt opnemen. We gebruiken JavaScript voor dit artikel, maar u kunt de voorbeelden in uw werktaal herschrijven.
Een eenvoudig voorbeeld
Hier is 8217;een eenvoudige functie die de faculteit van een bepaald geheel getal genereert:
const faculteit = n => { als (n === 0) retour 1; anders retourneer (faculteit(n – 1) * n); };
De faculteitsberekening is recursief, omdat faculteit() zichzelf binnen de else-voorwaarde aanroept. De berekening is ook zuiver, omdat elke gegeven waarde van n altijd dezelfde waarde zal opleveren. faculteit(5) is 120, ongeacht de status van het programma.
Advertentie
Vanwege de recursieve aard van de functie leidt het berekenen van de faculteit van verschillende grote getallen tot verspilde bewerkingen:
const x = faculteit(100); const y = faculteit(50);
Alle berekeningen die nodig zijn om y te berekenen, zijn al uitgevoerd als onderdeel van de berekening van x. Als faculteit() de invoer en de bijbehorende uitvoer in de cache zou opslaan, zou de berekening van y aanzienlijk kunnen worden versneld.
De faculteitsfunctie onthouden
Hier is een basisbenadering die de faculteit()-functie onthoudt:
const cache = { ;}; const faculteit = n => { als (cache[n]) { terug cache[n]; } laat waarde; als (n === 0) waarde = 1; else waarde = (faculteit(n – 1) * n); cache[n] = waarde; winstwaarde; };
Nu is er een cache-object dat faculteit() gebruikt om de uitvoerwaarden vast te leggen. Elke keer dat de functie wordt aangeroepen, wordt eerst gecontroleerd of de invoer n eerder is gezien. Als dit het geval is, kan het onmiddellijk kortsluiten en de in de cache opgeslagen waarde retourneren. Anders verloopt de recursieve berekening normaal, maar volgende runs met hetzelfde nummer worden versneld.
Nu zal het berekenen van faculteit(50) na faculteit(100) veel efficiënter zijn. De faculteit van 50 zou worden berekend als onderdeel van de faculteit van 100, dus de functie zou de waarde bijna onmiddellijk kunnen retourneren.
Een meer algemene oplossing
Hoewel de bovenstaande code werkt, is deze specifiek voor de functie faculteit(). Als je andere vergelijkbare functies zou gebruiken, zou je handmatig de cachecode aan elke functie moeten toevoegen.
Een meer algemene oplossing zou je elke functie laten inpakken met een functie van hogere orde die de geheugencapaciteit:
const onthouden = fn => { const cache = {}; terug (…args) => { const argsString = JSON.stringify(args); if (!cache[argsString]) { cache[argsString] = fn(…args); } cache teruggeven[argsString]; } };
Nu kun je de originele faculteit() functie aanpassen:
const faculteit = memoize(n => { als (n === 0) retour 1; anders retourneer (faculteit(n – 1) * n); }); Advertentie
Door factorial() te verpakken met memoize(), krijgt het automatische memo-mogelijkheden. De wrapper-functie retourneert een nieuwe functie die alle aanroepen naar faculteit() onderschept, hun argumenten stringiseert en controleert of ze eerder zijn gezien. Als dat het geval is, wordt de vorige geretourneerde waarde opnieuw gebruikt zonder de echte functie aan te roepen. Wanneer nieuwe argumenten worden gezien, wordt de functie aangeroepen en wordt de uitvoer toegevoegd aan de cache.
De wrapper gebruikt de JavaScript-syntaxis voor restparameters om een variabel aantal argumenten te accepteren. Dit betekent dat het met elke JavaScript-functie werkt. Deze benadering gebruikt JSON.stringify() om de tekenreeksrepresentatie van de argumenten te maken, dus wees voorzichtig als u een functie aanroept met complexe objecten, die niet volledig kunnen worden weergegeven als JSON.
Wanneer memoization niet gebruiken?
Memorisatie kan aanzienlijke prestatieverbeteringen opleveren, met name voor wiskundig zware bewerkingen. Het is echter geen techniek om overal te gebruiken. Niet alle functies moeten in het geheugen worden opgeslagen, omdat je in sommige gevallen de prestaties zou kunnen schaden.
Door een functie in te pakken met memoize(), forceer je een vergelijking van de invoerargumenten elke keer dat die functie wordt genoemd. Dit kost op zich al wat CPU-tijd. De voorbeeldwrapper hierboven voert JSON.stringify() uit elke keer dat de functie wordt aangeroepen, waardoor een nieuwe overhead wordt toegevoegd.
Memorisatie is geschikt voor functies waarbij de kans groot is dat dezelfde invoerwaarden regelmatig worden gezien. Als u zelden een functie met dezelfde argumenten aanroept, zullen cachehits zeldzaam zijn en kunt u prestaties verliezen door de serialisatie en vergelijking van argumenten. Het onderhouden van de cache verhoogt ook het geheugengebruik, omdat alle eerdere in- en uitgangen behouden moeten blijven.
U moet daarom de rol van elke functie in uw programma volledig beoordelen voordat u besluit om te onthouden. Vergelijk prestaties met en zonder geheugenopslag. Soms kan het voordeliger zijn om te vertrouwen op de eigen optimalisaties van de browser.
Advertentie
Houd er ten slotte rekening mee dat sommige functies niet in het geheugen kunnen worden opgeslagen. De techniek werkt alleen met pure functies—als je functie globale variabelen of een andere applicatiestatus bereikt, mag deze niet in het geheugen worden opgeslagen!
const functionUsingGlobalState = n => { if (n === window.scrollY) retourneer waar; else return functieUsingGlobalState(n – 1); }
Het onthouden van de bovenstaande functie kan onverwachte resultaten opleveren na de eerste run. Waarden van n worden in de cache opgeslagen met de originele versie van window.scrollY. De memo-wrapper retourneert de uitvoer in de cache, zelfs als window.scrollY is gewijzigd.
Samenvatting
Memoisatie is een vorm van caching die de uitvoering van repetitieve recursieve versnelt operaties. Het is een functionele programmeertechniek die kan worden geïmplementeerd als een generieke wrapper voor elke pure functie.
Memoisatie kom je het vaakst tegen in vaak aangeroepen functies die rekenintensieve bewerkingen uitvoeren. Het helpt verspilling te voorkomen door de noodzaak weg te nemen om waarden die al zijn geproduceerd als onderdeel van een eerdere oproep, opnieuw te berekenen.
De voordelen van memo's zullen minder duidelijk zijn in functies die eenvoudig zijn om mee te beginnen of die zelden worden aangeroepen. In sommige gevallen kan oneigenlijk gebruik van geheugenopslag de prestaties zelfs schaden, dus onthoud niet blindelings elke functie in uw toepassing.