Introduzione a Guava Memoizer

1. Panoramica

In questo tutorial, esploreremo le funzionalità di memoizzazione della libreria Guava di Google.

La memorizzazione è una tecnica che evita l'esecuzione ripetuta di una funzione computazionalmente costosa memorizzando nella cache il risultato della prima esecuzione della funzione.

1.1. Memoization vs Caching

La memorizzazione è simile alla memorizzazione nella cache per quanto riguarda l'archiviazione in memoria. Entrambe le tecniche tentano di aumentare l'efficienza riducendo il numero di chiamate a codice costoso dal punto di vista computazionale.

Tuttavia, mentre la memorizzazione nella cache è un termine più generico che affronta il problema a livello di istanza di classe, recupero di oggetti o recupero di contenuto, la memoizzazione risolve il problema a livello di esecuzione di metodo / funzione.

1.2. Guava Memoizer e Guava Cache

Guava supporta sia la memorizzazione che la memorizzazione nella cache. La memorizzazione si applica alle funzioni senza argomento ( Fornitore ) e alle funzioni con esattamente un argomento ( Funzione ). Il fornitore e la funzione qui si riferiscono alle interfacce funzionali Guava che sono sottoclassi dirette delle interfacce API funzionali Java 8 con lo stesso nome.

A partire dalla versione 23.6, Guava non supporta la memorizzazione di funzioni con più di un argomento.

Possiamo chiamare le API di memoizzazione su richiesta e specificare una politica di eliminazione che controlla il numero di voci conservate in memoria e impedisce la crescita incontrollata della memoria in uso sfrattando / rimuovendo una voce dalla cache una volta che corrisponde alla condizione della politica.

La memorizzazione fa uso di Guava Cache; per informazioni più dettagliate su Guava Cache, fare riferimento al nostro articolo Guava Cache.

2. Memoizzazione del fornitore

Esistono due metodi nella classe Suppliers che abilitano la memoizzazione: memoize e memoizeWithExpiration .

Quando vogliamo eseguire il metodo memoized, possiamo semplicemente chiamare il metodo get del fornitore restituito . A seconda che il valore restituito dal metodo esista in memoria, il metodo get restituirà il valore in memoria o eseguirà il metodo memoized e passerà il valore restituito al chiamante.

Esploriamo ogni metodo di memorizzazione del fornitore .

2.1. Memoizzazione del fornitore senza sfratto

Possiamo utilizzare il metodo memoize dei fornitori e specificare il fornitore delegato come riferimento del metodo:

Supplier memoizedSupplier = Suppliers.memoize( CostlySupplier::generateBigNumber);

Poiché non abbiamo specificato una politica di eliminazione, una volta chiamato il metodo get , il valore restituito persisterà in memoria mentre l'applicazione Java è ancora in esecuzione. Qualsiasi chiamata da ottenere dopo la chiamata iniziale restituirà il valore memorizzato.

2.2. Memoization del fornitore con sfratto per Time-To-Live (TTL)

Supponiamo di voler mantenere il valore restituito dal Fornitore nel promemoria solo per un certo periodo.

Possiamo utilizzare il metodo memoizeWithExpiration dei Fornitori e specificare l'ora di scadenza con la sua unità di tempo corrispondente (ad esempio, secondo, minuto), oltre al Fornitore delegato :

Supplier memoizedSupplier = Suppliers.memoizeWithExpiration( CostlySupplier::generateBigNumber, 5, TimeUnit.SECONDS);

Dopo che è trascorso il tempo specificato (5 secondi), la cache rimuoverà il valore restituito dal fornitore dalla memoria e qualsiasi chiamata successiva al metodo get rieseguirà generateBigNumber .

Per informazioni più dettagliate, fare riferimento a Javadoc.

2.3. Esempio

Simuliamo un metodo costoso dal punto di vista computazionale denominato generateBigNumber :

public class CostlySupplier { private static BigInteger generateBigNumber() { try { TimeUnit.SECONDS.sleep(2); } catch (InterruptedException e) {} return new BigInteger("12345"); } }

Il nostro metodo di esempio impiegherà 2 secondi per essere eseguito, quindi restituirà un risultato BigInteger . Potremmo memorizzarlo usando le API memoize o memoizeWithExpiration .

Per semplicità ometteremo la politica di sfratto:

@Test public void givenMemoizedSupplier_whenGet_thenSubsequentGetsAreFast() { Supplier memoizedSupplier; memoizedSupplier = Suppliers.memoize(CostlySupplier::generateBigNumber); BigInteger expectedValue = new BigInteger("12345"); assertSupplierGetExecutionResultAndDuration( memoizedSupplier, expectedValue, 2000D); assertSupplierGetExecutionResultAndDuration( memoizedSupplier, expectedValue, 0D); assertSupplierGetExecutionResultAndDuration( memoizedSupplier, expectedValue, 0D); } private  void assertSupplierGetExecutionResultAndDuration( Supplier supplier, T expectedValue, double expectedDurationInMs) { Instant start = Instant.now(); T value = supplier.get(); Long durationInMs = Duration.between(start, Instant.now()).toMillis(); double marginOfErrorInMs = 100D; assertThat(value, is(equalTo(expectedValue))); assertThat( durationInMs.doubleValue(), is(closeTo(expectedDurationInMs, marginOfErrorInMs))); }

La prima chiamata al metodo get richiede due secondi, come simulato nel metodo generateBigNumber ; tuttavia, le chiamate successive a get () verranno eseguite molto più velocemente, poiché il risultato generateBigNumber è stato memorizzato.

3. Memoizzazione delle funzioni

Per memorizzare un metodo che accetta un singolo argomento, costruiamo una mappa LoadingCache usando il metodo from di CacheLoader per fornire il builder relativo al nostro metodo come funzione Guava .

LoadingCache è una mappa simultanea, con valori caricati automaticamente da CacheLoader . CacheLoader popola la mappa calcolando la funzione specificata nel metodo from e inserendo il valore restituito in LoadingCache . Per informazioni più dettagliate, fare riferimento a Javadoc.

LoadingCache 'chiave s è la funzione ' s argomento / ingresso, mentre il valore della mappa è la funzione s restituito' valore:

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

Poiché LoadingCache è una mappa simultanea, non consente chiavi o valori nulli. Pertanto, dobbiamo assicurarci che la funzione non supporti null come argomento o restituisca valori null.

3.1. Memorizzazione delle funzioni con politiche di sfratto

Possiamo applicare diverse politiche di sfratto di Guava Cache quando memorizziamo una funzione come menzionato nella Sezione 3 dell'articolo Guava Cache.

Ad esempio, possiamo rimuovere le voci che sono rimaste inattive per 2 secondi:

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

Next, let's take a look at two use cases of Function memoization: Fibonacci sequence and factorial.

3.2. Fibonacci Sequence Example

We can recursively compute a Fibonacci number from a given number n:

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

Without memoization, when the input value is relatively high, the execution of the function will be slow.

To improve the efficiency and performance, we can memoize getFibonacciNumber using CacheLoader and CacheBuilder, specifying the eviction policy if necessary.

In the following example, we remove the oldest entry once the memo size has reached 100 entries:

public class FibonacciSequence { private static LoadingCache memo = CacheBuilder.newBuilder() .maximumSize(100) .build(CacheLoader.from(FibonacciSequence::getFibonacciNumber)); public static 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)); } } }

Here, we use getUnchecked method which returns the value if exists without throwing a checked exception.

In questo caso, non abbiamo bisogno di gestire in modo esplicito l'eccezione quando si specifica getFibonacciNumber metodo di riferimento nel CacheLoader 's dalla chiamata al metodo.

Per informazioni più dettagliate, fare riferimento a Javadoc.

3.3. Esempio fattoriale

Successivamente, abbiamo un altro metodo ricorsivo che calcola il fattoriale di un dato valore di input, n:

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

Possiamo migliorare l'efficienza di questa implementazione applicando la memoizzazione:

public class Factorial { private static LoadingCache memo = CacheBuilder.newBuilder() .build(CacheLoader.from(Factorial::getFactorial)); public static BigInteger getFactorial(int n) { if (n == 0) { return BigInteger.ONE; } else { return BigInteger.valueOf(n).multiply(memo.getUnchecked(n - 1)); } } }

4. Conclusione

In questo articolo, abbiamo visto come Guava fornisce API per eseguire la memorizzazione dei metodi del fornitore e della funzione . Abbiamo anche mostrato come specificare la politica di eliminazione del risultato della funzione archiviata in memoria.

Come sempre, il codice sorgente può essere trovato su GitHub.