streamalism.org

1. Oversigt

I denne vejledning undersøger vi memoiseringsfunktionerne i Googles Guava-bibliotek.

Memoization er en teknik, der undgår gentagen udførelse af en beregningsdygtig funktion ved at cache resultatet af den første udførelse af funktionen.

1.1. Memoization vs Caching

Memoization svarer til cache med hensyn til hukommelseslagring. Begge teknikker forsøger at øge effektiviteten ved at reducere antallet af opkald til beregningsdyr kode.

Imidlertid hvor caching er et mere generisk udtryk, der løser problemet på niveauet med klasse-instantiering, genfinding af objekter eller genfinding af indhold, memoization løser problemet på niveauet for metode- / funktionsudførelse.

1.2. Guava Memoizer og Guava Cache

Guava understøtter både memoisering og caching. Memoization gælder for funktioner uden argument (Leverandør) og fungerer med nøjagtigt et argument (Fungere). Leverandør og Fungere her henvises til Guava-funktionelle grænseflader, som er direkte underklasser af Java 8-funktionelle API-grænseflader med de samme navne.

Fra version 23.6 understøtter Guava ikke memoization af funktioner med mere end et argument.

Vi kan kalde memoization-API'er på forespørgsel og angive en udsættelsespolitik, der styrer antallet af poster, der opbevares i hukommelsen og forhindrer ukontrolleret vækst af hukommelse i brug ved at fjerne / fjerne en post fra cachen, når den matcher betingelsen for politikken.

Memoization gør brug af Guava Cache; for mere detaljerede oplysninger om Guava Cache, se venligst vores Guava Cache-artikel.

2. Leverandør Memoisering

Der er to metoder i Leverandører klasse, der muliggør memoization: huskeog memoizeWithExpiration.

Når vi vil udføre den memoriserede metode, kan vi simpelthen ringe til få metode til returneret Leverandør. Afhængigt af om metodens returværdi findes i hukommelsen, få metode returnerer enten hukommelsesværdien eller udfører den memoiserede metode og vender returværdien til den, der ringer op.

Lad os undersøge hver metode til Leverandør'S memoization.

2.1. Leverandør Memoisering uden udsættelse

Vi kan bruge Leverandører‘ huske metode og specificer den delegerede Leverandør som en metodehenvisning:

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

Da vi ikke har specificeret en udsættelsespolitik, en gang få metode kaldes, vil den returnerede værdi forblive i hukommelsen, mens Java-applikationen stadig kører. Eventuelle opkald til få efter det første opkald returnerer den memoiserede værdi.

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

Antag, at vi kun vil holde den returnerede værdi fra Leverandør i notatet i en bestemt periode.

Vi kan bruge Leverandører‘ memoizeWithExpiration metode og specificer udløbstiden med den tilsvarende tidsenhed (f.eks. sekund, minut) ud over den delegerede Leverandør:

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

Når den angivne tid er gået (5 sekunder), udsender cachen den returnerede værdi af Leverandør fra hukommelsen og ethvert efterfølgende opkald til få metoden genudføres createBigNumber.

For mere detaljeret information henvises til Javadoc.

2.3. Eksempel

Lad os simulere en beregningsdyr metode, der hedder createBigNumber:

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

Vores eksempelmetode tager 2 sekunder at udføre og returnerer derefter a BigInteger resultat. Vi kunne huske det ved hjælp af enten huske eller memoizeWithExpiration API'er.

For enkelheds skyld udelader vi udsættelsespolitikken:

@Test offentlig ugyldighed givenMemoizedSupplier_whenGet_thenSubsequentGetsAreFast () {Leverandør memoizedSupplier; memoizedSupplier = Suppliers.memoize (CostlySupplier :: createBigNumber); BigInteger expectValue = nyt BigInteger ("12345"); assertSupplierGetExecutionResultAndDuration (memoizedSupplier, expectedValue, 2000D); assertSupplierGetExecutionResultAndDuration (memoizedSupplier, expectedValue, 0D); assertSupplierGetExecutionResultAndDuration (memoizedSupplier, expectedValue, 0D); } privat ugyldighed assertSupplierGetExecutionResultAndDuration (leverandørleverandør, T forventet værdi, dobbelt forventetDurationInMs) {Øjeblikkelig start = Øjeblikkelig.now (); T-værdi = leverandør.get (); Long durationInMs = Duration.between (start, Instant.now ()). ToMillis (); dobbelt marginOfErrorInMs = 100D; assertThat (værdi, er (equalTo (forventet værdi))); assertThat (durationInMs.doubleValue (), er (closeTo (expectDurationInMs, marginOfErrorInMs))); }

Den første få metodeopkald tager to sekunder, som simuleret i createBigNumber metode; imidlertid, efterfølgende opkald til få() vil udføre betydeligt hurtigere, da createBigNumber resultatet er blevet noteret.

3. Fungere Memoisering

At huske en metode, der tager et enkelt argument, vi bygge en LoadingCache kort ved hjælp af CacheLoader'S fra metode til at forsyne bygherren med vores metode som en guava Fungere.

LoadingCache er et samtidigt kort med værdier, der automatisk indlæses af CacheLoader.CacheLoader udfylder kortet ved at beregne Fungere angivet i fra metode, og sætte den returnerede værdi i LoadingCache. For mere detaljeret information henvises til Javadoc.

LoadingCache'S nøgle er Fungere'S argument / input, mens kortets værdi er Fungere'S returnerede værdi:

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

Siden LoadingCache er et kort, det tillader ikke nul-nøgler eller værdier. Derfor er vi nødt til at sikre, at Fungere understøtter ikke null som et argument eller returnerer null-værdier.

3.1. Fungere Memoization With Eviction Politics

Vi kan anvende forskellige Guava Cache's bortkastningspolitik, når vi husker en Fungere som nævnt i afsnit 3 i Guava Cache-artiklen.

For eksempel kan vi kaste de poster, der har været inaktive i 2 sekunder:

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

Lad os derefter se på to brugstilfælde af Fungere memoization: Fibonacci-sekvens og faktoria.

3.2. Fibonacci-sekvenseksempel

Vi kan rekursivt beregne et Fibonacci-tal ud fra et givet tal n:

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

Uden memoization vil udførelsen af ​​funktionen være langsom, når inputværdien er relativt høj.

For at forbedre effektiviteten og ydeevnen kan vi huske getFibonacciNumber ved brug af CacheLoader og CacheBuilder, specificering af udsættelsespolitikken, hvis det er nødvendigt.

I det følgende eksempel fjerner vi den ældste post, når memo-størrelsen har nået 100 poster:

public class FibonacciSequence {private static LoadingCache memo = CacheBuilder.newBuilder () .maximumSize (100) .build (CacheLoader.from (FibonacciSequence :: getFibonacciNumber)); offentlig statisk BigInteger getFibonacciNumber (int n) {if (n == 0) {return BigInteger.ZERO; } ellers hvis (n == 1) {returner BigInteger.ONE; } andet {returner memo.getUnchecked (n - 1) .add (memo.getUnchecked (n - 2)); }}}

Her bruger vi getUchchecked metode, der returnerer værdien, hvis den findes uden at kaste en afkrydset undtagelse.

I dette tilfælde behøver vi ikke eksplicit at håndtere undtagelsen, når vi specificerer getFibonacciNumber metodehenvisning i CacheLoader'S fra metodeopkald.

For mere detaljeret information henvises til Javadoc.

3.3. Faktorisk eksempel

Dernæst har vi en anden rekursiv metode, der beregner faktoren for en given inputværdi, n:

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

Vi kan forbedre effektiviteten af ​​denne implementering ved at anvende notater:

public class Factorial {privat statisk LoadingCache-memo = CacheBuilder.newBuilder () .build (CacheLoader.from (Faktor :: getFactorial)); offentlig statisk BigInteger getFactorial (int n) {if (n == 0) {returner BigInteger.ONE; } andet {returner BigInteger.valueOf (n) .multiply (memo.getUnchecked (n - 1)); }}}

4. Konklusion

I denne artikel har vi set, hvordan Guava leverer API'er til at udføre memoisering af Leverandør og Fungere metoder. Vi har også vist, hvordan man angiver udkastningspolitikken for den gemte funktionsresultat i hukommelsen.

Som altid kan kildekoden findes på GitHub.