Introduction à Guava Memoizer

1. Vue d'ensemble

Dans ce didacticiel, nous explorerons les fonctionnalités de mémorisation de la bibliothèque Guava de Googles.

La mémorisation est une technique qui évite l'exécution répétée d'une fonction coûteuse en calcul en mettant en cache le résultat de la première exécution de la fonction.

1.1. Mémorisation vs mise en cache

La mémorisation est similaire à la mise en cache en ce qui concerne le stockage mémoire. Les deux techniques tentent d' augmenter l'efficacité en réduisant le nombre d'appels à du code coûteux en calcul.

Cependant, alors que la mise en cache est un terme plus générique qui aborde le problème au niveau de l'instanciation de classe, de la récupération d'objet ou de la récupération de contenu, la mémorisation résout le problème au niveau de l'exécution de la méthode / fonction.

1.2. Mémo de goyave et cache de goyave

Guava prend en charge à la fois la mémorisation et la mise en cache. La mémorisation s'applique aux fonctions sans argument ( Fournisseur ) et aux fonctions avec exactement un argument ( Fonction ). Le fournisseur et la fonction font ici référence aux interfaces fonctionnelles de Guava qui sont des sous-classes directes des interfaces API fonctionnelles Java 8 du même nom.

Depuis la version 23.6, Guava ne prend pas en charge la mémorisation des fonctions avec plus d'un argument.

Nous pouvons appeler des API de mémorisation à la demande et spécifier une politique d'éviction qui contrôle le nombre d'entrées conservées en mémoire et empêche la croissance incontrôlée de la mémoire utilisée en expulsant / supprimant une entrée du cache une fois qu'elle correspond à la condition de la politique.

La mémorisation utilise le cache de goyave; Pour plus d'informations sur Guava Cache, veuillez consulter notre article Guava Cache.

2. Mémorisation du fournisseur

Il existe deux méthodes dans la classe Suppliers qui permettent la mémorisation : memoize et memoizeWithExpiration .

Lorsque nous voulons exécuter la méthode mémorisée, nous pouvons simplement appeler la méthode get du fournisseur retourné . Selon que la valeur de retour de la méthode existe en mémoire, la méthode get retournera la valeur en mémoire ou exécutera la méthode mémorisée et passera la valeur de retour à l'appelant.

Explorons chaque méthode de mémorisation du fournisseur .

2.1. Mémorisation du fournisseur sans expulsion

Nous pouvons utiliser la méthode memoize des fournisseurs et spécifier le fournisseur délégué comme référence de méthode:

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

Comme nous n'avons pas spécifié de politique d'éviction, une fois la méthode get appelée, la valeur renvoyée restera en mémoire pendant que l'application Java est toujours en cours d'exécution. Tous les appels à obtenir après l'appel initial renverront la valeur mémorisée.

2.2. Mémorisation des fournisseurs avec expulsion par durée de vie (TTL)

Supposons que nous souhaitons uniquement conserver la valeur renvoyée par le fournisseur dans le mémo pendant une certaine période.

Nous pouvons utiliser la méthode memoizeWithExpiration des fournisseurs et spécifier l'heure d'expiration avec son unité de temps correspondante (par exemple, seconde, minute), en plus du fournisseur délégué :

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

Une fois le temps spécifié écoulé (5 secondes), le cache expulsera la valeur renvoyée du fournisseur de la mémoire et tout appel ultérieur à la méthode get réexécutera generateBigNumber .

Pour plus d'informations, reportez-vous au Javadoc.

2.3. Exemple

Simulons une méthode coûteuse en calcul nommée generateBigNumber :

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

Notre exemple de méthode prendra 2 secondes pour s'exécuter, puis retournera un résultat BigInteger . Nous pourrions le mémoriser en utilisant les API memoize ou memoizeWithExpiration .

Pour plus de simplicité, nous allons omettre la politique d'expulsion:

@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))); }

Le premier appel de la méthode get prend deux secondes, comme simulé dans la méthode generateBigNumber ; cependant, les appels suivants à get () s'exécuteront beaucoup plus rapidement, car le résultat generateBigNumber a été mémorisé.

3. Mémorisation des fonctions

Pour mémoriser une méthode qui prend un seul argument, nous construisons une carte LoadingCache en utilisant la méthode from de CacheLoader pour provisionner le constructeur concernant notre méthode en tant que fonction Guava .

LoadingCache est une carte simultanée, avec des valeurs chargées automatiquement par CacheLoader . CacheLoader remplit la carte en calculant la fonction spécifiée dans la méthode from et en plaçant la valeur renvoyée dans le LoadingCache . Pour plus d'informations, reportez-vous au Javadoc.

LoadingCache « est la clé de la fonction » argument de / entrée de, alors que la valeur de la carte est la fonction « s valeur renvoyée:

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

Étant donné que LoadingCache est une carte simultanée, il n'autorise pas les clés ou valeurs nulles. Par conséquent, nous devons nous assurer que la fonction ne prend pas en charge null comme argument ou ne renvoie pas de valeurs nulles.

3.1. Mémorisation des fonctions avec les politiques d'expulsion

Nous pouvons appliquer une politique d'éviction différente de Guava Cache lorsque nous mémorisons une fonction comme mentionné dans la section 3 de l'article Guava Cache.

Par exemple, nous pouvons expulser les entrées qui sont restées inactives pendant 2 secondes:

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.

Dans ce cas, nous ne devons pas traiter explicitement l'exception lors de la spécification getFibonacciNumber référence de méthode dans le CacheLoader « s de l' appel de la méthode.

Pour plus d'informations, reportez-vous au Javadoc.

3.3. Exemple factoriel

Ensuite, nous avons une autre méthode récursive qui calcule la factorielle d'une valeur d'entrée donnée, n:

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

Nous pouvons améliorer l'efficacité de cette implémentation en appliquant la mémorisation:

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. Conclusion

Dans cet article, nous avons vu comment Guava fournit des API pour effectuer la mémorisation des méthodes Fournisseur et Fonction . Nous avons également montré comment spécifier la politique d'éviction du résultat de la fonction stockée en mémoire.

Comme toujours, le code source peut être trouvé sur GitHub.