streamalism.org

1. Overzicht

In deze tutorial bespreken we de memo-functies van de Guava-bibliotheek van Google.

Memoization is een techniek die herhaalde uitvoering van een rekenkundig dure functie vermijdt door het resultaat van de eerste uitvoering van de functie in het cachegeheugen te bewaren.

1.1. Memoisatie versus caching

Memoization is vergelijkbaar met caching met betrekking tot geheugenopslag. Beide technieken proberen verhoog de efficiëntie door het aantal oproepen naar computationeel dure code te verminderen.

Hoewel caching een meer algemene term is die het probleem aanpakt op het niveau van klasse-instantiatie, het ophalen van objecten of het ophalen van inhoud, memoization lost het probleem op op het niveau van de methode / functie-uitvoering.

1.2. Guava Memoizer en Guava Cache

Guava ondersteunt zowel memo-opname als caching. Memoization is van toepassing op functies zonder argument (Leverancier) en functies met precies één argument (Functie). Leverancier en Functie verwijzen hier naar Guava functionele interfaces die directe subklassen zijn van Java 8 Functionele API-interfaces met dezelfde namen.

Vanaf versie 23.6 ondersteunt Guava geen memoisatie van functies met meer dan één argument.

We kunnen memoization API's on-demand aanroepen en een verwijderingsbeleid specificeren dat het aantal vermeldingen in het geheugen regelt en de ongecontroleerde groei van het gebruikte geheugen voorkomt door een item uit de cache te verwijderen / verwijderen zodra het overeenkomt met de voorwaarde van het beleid.

Memoization maakt gebruik van de Guava Cache; Raadpleeg ons artikel over Guava Cache voor meer informatie over Guava Cache.

2. Leverancier Memoisatie

Er zijn twee methoden in het Leveranciers klasse die memoisatie mogelijk maakt: memoize, en memoizeWithExpiration.

Als we de memo-methode willen uitvoeren, kunnen we eenvoudig de krijgen methode van de geretourneerde Leverancier. Afhankelijk van of de retourwaarde van de methode in het geheugen bestaat, kan de krijgen method retourneert de in-memory waarde of voert de memoized methode uit en geeft de retourwaarde door aan de beller.

Laten we elke methode van de Leverancier‘Memoization.

2.1. Leverancier Memoization zonder uitzetting

We kunnen de Leveranciers‘ memoize methode en specificeer de gedelegeerde Leverancier als referentie voor de methode:

Leverancier memoizedSupplier = Suppliers.memoize (CostlySupplier :: GenereerBigNumber);

Aangezien we geen uitzettingsbeleid hebben gespecificeerd, eens de krijgen methode wordt aangeroepen, blijft de geretourneerde waarde in het geheugen aanwezig terwijl de Java-applicatie nog actief is. Alle oproepen naar krijgen na de eerste aanroep zal de gememoriseerde waarde worden geretourneerd.

2.2. Leverancier Memoisatie met uitzetting door Time-To-Live (TTL)

Stel dat we alleen de geretourneerde waarde van de Leverancier in de memo voor een bepaalde periode.

We kunnen de Leveranciers‘ memoizeWithExpiration methode en specificeer de vervaltijd met de bijbehorende tijdseenheid (bijv. seconde, minuut), naast de gedelegeerde Leverancier:

Leverancier memoizedSupplier = Suppliers.memoizeWithExpiration (CostlySupplier :: GenereerBigNumber, 5, TimeUnit.SECONDS);

Nadat de opgegeven tijd is verstreken (5 seconden), verwijdert de cache de geretourneerde waarde van de Leverancier uit het geheugen en elke volgende oproep aan de krijgen methode zal opnieuw worden uitgevoerd GenereerBigNummer.

Voor meer gedetailleerde informatie verwijzen wij u naar de Javadoc.

2.3. Voorbeeld

Laten we een computationeel dure methode simuleren met de naam GenereerBigNummer:

openbare klasse CostlySupplier {privé statisch BigInteger genererenBigNumber () {probeer {TimeUnit.SECONDS.sleep (2); } catch (InterruptedException e) {} retourneer nieuwe BigInteger ("12345"); }}

Onze voorbeeldmethode duurt 2 seconden om uit te voeren en retourneert vervolgens een BigInteger resultaat. We zouden het kunnen onthouden met behulp van de memoize of memoizeWithExpiration API's.

Voor de eenvoud laten we het uitzettingsbeleid achterwege:

@Test openbaar ongeldig gegevenMemoizedSupplier_whenGet_thenSubsequentGetsAreFast () {Leverancier memoizedSupplier; memoizedSupplier = Suppliers.memoize (CostlySupplier :: GenereerBigNumber); BigInteger verwachteValue = nieuwe BigInteger ("12345"); assertSupplierGetExecutionResultAndDuration (memoizedSupplier, verwachteValue, 2000D); assertSupplierGetExecutionResultAndDuration (memoizedSupplier, verwachteValue, 0D); assertSupplierGetExecutionResultAndDuration (memoizedSupplier, verwachteValue, 0D); } private void assertSupplierGetExecutionResultAndDuration (leverancier leverancier, T verwachteValue, dubbele verwachteDurationInMs) {Instant start = Instant.now (); T-waarde = leverancier.get (); Long durationInMs = Duration.between (start, Instant.now ()). ToMillis (); dubbele marginOfErrorInMs = 100D; assertThat (waarde, is (gelijk aan (verwachte waarde))); assertThat (durationInMs.doubleValue (), is (closeTo (verwachteDurationInMs, marginOfErrorInMs))); }

De eerste krijgen method-aanroep duurt twee seconden, zoals gesimuleerd in de GenereerBigNummer methode; echter, volgende oproepen naar krijgen() zal aanzienlijk sneller worden uitgevoerd, aangezien de GenereerBigNummer resultaat is genoteerd.

3. Functie Memoisatie

Om een ​​methode te onthouden waarvoor een enkel argument nodig is, moeten we bouw een LoadingCache kaart met behulp van CacheLoader‘S van methode om de bouwer te voorzien van onze methode als een Guava Functie.

LoadingCache is een gelijktijdige kaart, met waarden die automatisch worden geladen door CacheLoader.CacheLoader vult de kaart door de Functie gespecificeerd in de van methode, en het plaatsen van de geretourneerde waarde in de LoadingCache. Voor meer gedetailleerde informatie verwijzen wij u naar de Javadoc.

LoadingCacheDe sleutel is de Functie‘S argument / input, terwijl de waarde van de kaart de Functie‘S geretourneerde waarde:

LoadingCache memo = CacheBuilder.newBuilder () .build (CacheLoader.from (FibonacciSequence :: getFibonacciNumber));

Sinds LoadingCache is een gelijktijdige kaart, het staat geen null-sleutels of waarden toe. Daarom moeten we ervoor zorgen dat de Functie ondersteunt null niet als argument en retourneert geen null-waarden.

3.1. Functie Memoisatie met uitzettingbeleid

We kunnen een ander Guava Cache-uitzettingsbeleid toepassen wanneer we een Functie zoals vermeld in Sectie 3 van het Guava Cache-artikel.

We kunnen bijvoorbeeld de vermeldingen verwijderen die gedurende 2 seconden inactief zijn geweest:

LoadingCache memo = CacheBuilder.newBuilder () .expireAfterAccess (2, TimeUnit.SECONDS) .build (CacheLoader.from (Fibonacci :: getFibonacciNumber));

Laten we vervolgens eens kijken naar twee use-cases van Functie memoization: Fibonacci-reeks en faculteit.

3.2. Voorbeeld van een Fibonacci-reeks

We kunnen recursief een Fibonacci-getal berekenen uit een bepaald getal n:

openbare statische BigInteger getFibonacciNumber (int n) {if (n == 0) {return BigInteger.ZERO; } else if (n == 1) {return BigInteger.ONE; } else {retourneer getFibonacciNumber (n - 1) .add (getFibonacciNumber (n - 2)); }}

Zonder memo, wanneer de invoerwaarde relatief hoog is, zal de uitvoering van de functie traag zijn.

Om de efficiëntie en prestaties te verbeteren, kunnen we memoriseren getFibonacciNumber gebruik makend van CacheLoader en CacheBuilder, het specificeren van het uitzettingsbeleid indien nodig.

In het volgende voorbeeld verwijderen we het oudste item zodra de memogrootte 100 items heeft bereikt:

openbare klasse FibonacciSequence {privé statische LoadingCache memo = CacheBuilder.newBuilder () .maximumSize (100) .build (CacheLoader.from (FibonacciSequence :: getFibonacciNumber)); openbare statische BigInteger getFibonacciNumber (int n) {if (n == 0) {return BigInteger.ZERO; } else if (n == 1) {return BigInteger.ONE; } else {return memo.getUnchecked (n - 1) .add (memo.getUnchecked (n - 2)); }}}

Hier gebruiken we getUnchecked methode die de waarde retourneert als deze bestaat zonder een aangevinkte uitzondering te genereren.

In dit geval hoeven we de uitzondering niet expliciet af te handelen bij het specificeren getFibonacciNumber methode verwijzing in de CacheLoader‘S van methode oproep.

Voor meer gedetailleerde informatie verwijzen wij u naar de Javadoc.

3.3. Factoriaal voorbeeld

Vervolgens hebben we nog een recursieve methode die de faculteit berekent van een gegeven invoerwaarde, n:

openbare statische BigInteger getFactorial (int n) {if (n == 0) {return BigInteger.ONE; } else {return BigInteger.valueOf (n) .multiply (getFactorial (n - 1)); }}

We kunnen de efficiëntie van deze implementatie verbeteren door memoisatie toe te passen:

openbare klasse Factorial {privé statische LoadingCache memo = CacheBuilder.newBuilder () .build (CacheLoader.from (Factorial :: getFactorial)); openbare statische BigInteger getFactorial (int n) {if (n == 0) {return BigInteger.ONE; } else {retourneer BigInteger.valueOf (n) .multiply (memo.getUnchecked (n - 1)); }}}

4. Conclusie

In dit artikel hebben we gezien hoe Guava API's biedt om memo's van uit te voeren Leverancier en Functie methoden. We hebben ook laten zien hoe het verwijderingsbeleid van het opgeslagen functieresultaat in het geheugen kan worden gespecificeerd.

Zoals altijd is de broncode te vinden op GitHub.