streamalism.org

1. Oversikt

I denne veiledningen vil vi utforske memoiseringsfunksjonene i Googles Guava-bibliotek.

Memoization er en teknikk som unngår gjentatt kjøring av en beregningsdyr funksjon ved å cache resultatet av den første kjøringen av funksjonen.

1.1. Memoization vs Caching

Memoisering ligner på hurtigbufring med hensyn til minnelagring. Begge teknikkene prøver å øke effektiviteten ved å redusere antall samtaler til beregningsdyr kode.

Imidlertid, mens caching er et mer generelt begrep som løser problemet på nivået av klasseinstansiering, gjenfinning av objekt eller gjenfinning av innhold, memoization løser problemet på nivået for metode- / funksjonsutførelse.

1.2. Guava Memoizer og Guava Cache

Guava støtter både memoisering og caching. Memoisering gjelder funksjoner uten argument (Leverandør) og fungerer med nøyaktig ett argument (Funksjon). Leverandør og Funksjon her refererer til Guava funksjonelle grensesnitt som er direkte underklasser av Java 8 Funksjonelle API grensesnitt med samme navn.

Fra versjon 23.6 støtter ikke Guava memoization av funksjoner med mer enn ett argument.

Vi kan ringe memoization APIs on-demand og spesifisere en utkastelsespolicy som styrer antall oppføringer som er lagret i minnet og forhindrer ukontrollert vekst av minne i bruk ved å kaste ut / fjerne en oppføring fra hurtigbufferen når den samsvarer med betingelsen for policyen.

Memoization bruker Guava Cache; for mer detaljert informasjon om Guava Cache, se vår Guava Cache-artikkel.

2. Leverandør Memoisering

Det er to metoder i Leverandører klasse som muliggjør memoisering: huske, og memoizeWithExpiration.

Når vi ønsker å utføre den memoriserte metoden, kan vi ganske enkelt ringe få metoden for den returnerte Leverandør. Avhengig av om metodens returverdi eksisterer i minnet, vil få metoden vil enten returnere minneverdien eller utføre den memoriserte metoden og sende returverdien til den som ringer.

La oss utforske hver metode for Leverandør’S memoization.

2.1. Leverandør Memoization Without Eviction

Vi kan bruke Leverandører‘ huske metode og spesifiser delegert Leverandør som en metodereferanse:

Leverandør memoizedSupplier = Suppliers.memoize (CostlySupplier :: createBigNumber);

Siden vi ikke har spesifisert noen utkastelsespolitikk, først når få metode kalles, vil den returnerte verdien vedvare i minnet mens Java-applikasjonen fortsatt kjører. Eventuelle samtaler til få etter den første samtalen vil den memoiserte verdien returneres.

2.2. Leverandør Memoization With Eviction by Time-To-Live (TTL)

Anta at vi bare vil beholde den returnerte verdien fra Leverandør i notatet for en viss periode.

Vi kan bruke Leverandører‘ memoizeWithExpiration metode og spesifiser utløpstiden med tilhørende tidsenhet (f.eks. sekund, minutt), i tillegg til den delegerte Leverandør:

Leverandør memoizedSupplier = Suppliers.memoizeWithExpiration (CostlySupplier :: createBigNumber, 5, TimeUnit.SECONDS);

Etter at den angitte tiden har gått (5 sekunder), vil hurtigbufferen kaste ut den returnerte verdien av Leverandør fra hukommelsen og eventuelle etterfølgende samtaler til få metoden vil kjøres på nytt createBigNumber.

For mer detaljert informasjon, se Javadoc.

2.3. Eksempel

La oss simulere en beregningsdyr metode som heter createBigNumber:

offentlig klasse CostlySupplier {privat statisk BigInteger generereBigNumber () {prøv {TimeUnit.SECONDS.sleep (2); } fange (InterruptedException e) {} returnere nytt BigInteger ("12345"); }}

Eksempelmetoden vår tar to sekunder å utføre, og returnerer deretter a BigInteger resultat. Vi kan huske det med enten huske eller memoizeWithExpiration APIer.

For enkelhets skyld vil vi utelate politikken for utkastelse:

@Test offentlig ugyldig givenMemoizedSupplier_whenGet_thenSubsequentGetsAreFast () {Leverandør memoizedSupplier; memoizedSupplier = Suppliers.memoize (CostlySupplier :: createBigNumber); BigInteger expectValue = new BigInteger ("12345"); assertSupplierGetExecutionResultAndDuration (memoizedSupplier, expectedValue, 2000D); assertSupplierGetExecutionResultAndDuration (memoizedSupplier, expectedValue, 0D); assertSupplierGetExecutionResultAndDuration (memoizedSupplier, expectedValue, 0D); } private void assertSupplierGetExecutionResultAndDuration (leverandørleverandør, T forventet verdi, dobbelt forventetDurationInMs) {Øyeblikkelig start = Øyeblikkelig nå (); T-verdi = leverandør.get (); Long durationInMs = Duration.between (start, Instant.now ()). ToMillis (); dobbel marginOfErrorInMs = 100D; assertThat (verdi, er (equalTo (forventet verdi))); assertThat (durationInMs.doubleValue (), er (closeTo (expectDurationInMs, marginOfErrorInMs))); }

Den første få metodeanrop tar to sekunder, som simulert i createBigNumber metode; derimot, påfølgende samtaler til få() vil kjøre betydelig raskere, siden createBigNumber resultatet er blitt husket.

3. Funksjon Memoisering

Å huske en metode som tar et enkelt argument vi bygge en LoadingCache kart ved hjelp av CacheLoader‘S fra metode for å skaffe byggherren angående vår metode som en guava Funksjon.

LoadingCache er et samtidig kart, med verdier som automatisk lastes inn av CacheLoader.CacheLoader fyller kartet ved å beregne Funksjon spesifisert i fra metode, og sette den returnerte verdien i LoadingCache. For mer detaljert informasjon, se Javadoc.

LoadingCache’S nøkkel er Funksjon‘S argument / input, mens kartets verdi er Funksjon‘S returnerte verdi:

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

Siden LoadingCache er et samtidig kart, det tillater ikke nullnøkler eller verdier. Derfor må vi sørge for at Funksjon støtter ikke null som argument eller returnerer nullverdier.

3.1. Funksjon Memoization With Eviction Policies

Vi kan bruke forskjellige Guava Caches utkastelsesregler når vi noterer en Funksjon som nevnt i seksjon 3 i Guava Cache-artikkelen.

For eksempel kan vi kaste ut oppføringene som har vært inaktive i to sekunder:

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

Deretter, la oss ta en titt på to brukstilfeller av Funksjon memoization: Fibonacci-sekvens og faktoria.

3.2. Fibonacci-sekvenseksempel

Vi kan rekursivt beregne et Fibonacci-tall fra et gitt tall n:

offentlig statisk BigInteger getFibonacciNumber (int n) {if (n == 0) {return BigInteger.ZERO; } annet hvis (n == 1) {returner BigInteger.ONE; } annet {return getFibonacciNumber (n - 1) .add (getFibonacciNumber (n - 2)); }}

Uten notering, når inngangsverdien er relativt høy, vil utførelsen av funksjonen være treg.

For å forbedre effektiviteten og ytelsen kan vi huske getFibonacciNumber ved hjelp av CacheLoader og CacheBuilder, spesifisere eviction policy hvis nødvendig.

I det følgende eksemplet fjerner vi den eldste oppføringen når notatstørrelsen har nådd 100 oppføringer:

offentlig klasse FibonacciSequence {privat statisk LoadingCache-notat = CacheBuilder.newBuilder () .maximumSize (100) .build (CacheLoader.from (FibonacciSequence :: getFibonacciNumber)); offentlig statisk BigInteger getFibonacciNumber (int n) {if (n == 0) {return BigInteger.ZERO; } annet hvis (n == 1) {returner BigInteger.ONE; } annet {return memo.getUnchecked (n - 1) .add (memo.getUnchecked (n - 2)); }}}

Her bruker vi bli ukontrollert metode som returnerer verdien hvis den eksisterer uten å kaste et avkrysset unntak.

I dette tilfellet trenger vi ikke eksplisitt å håndtere unntaket når vi spesifiserer getFibonacciNumber metode referanse i CacheLoader‘S fra metodeanrop.

For mer detaljert informasjon, se Javadoc.

3.3. Faktorisk eksempel

Deretter har vi en annen rekursiv metode som beregner faktoren for en gitt inngangsverdi, n:

offentlig statisk BigInteger getFactorial (int n) {if (n == 0) {return BigInteger.ONE; } annet {returner BigInteger.valueOf (n) .multiply (getFactorial (n - 1)); }}

Vi kan forbedre effektiviteten av denne implementeringen ved å bruke notater:

offentlig klasse Faktor {privat statisk LoadingCache-notat = CacheBuilder.newBuilder () .build (CacheLoader.from (Faktor :: getFactorial)); offentlig statisk BigInteger getFactorial (int n) {if (n == 0) {return BigInteger.ONE; } annet {return BigInteger.valueOf (n) .multiply (memo.getUnchecked (n - 1)); }}}

4. Konklusjon

I denne artikkelen har vi sett hvordan Guava tilbyr APIer for å utføre memoisering av Leverandør og Funksjon metoder. Vi har også vist hvordan du spesifiserer utkastelsespolitikken for det lagrede funksjonsresultatet i minnet.

Som alltid kan kildekoden bli funnet på GitHub.