Introduction to Guava Memoizer – Guava Memoizer简介

最后修改: 2018年 2月 1日

中文/混合/英文(键盘快捷键：t)

1. Overview

1.概述

In this tutorial, we’ll explore the memoization features of Googles’ Guava library.

在本教程中，我们将探索Googles的Guava库的记忆化功能。

Memoization is a technique that avoids repeated execution of a computationally expensive function by caching the result of the first execution of the function.

Memoization是一种技术，它通过缓存第一次执行函数的结果来避免重复执行一个计算量大的函数。

1.1. Memoization vs. Caching

1.1.记忆化与缓存

Memoization is similar to caching with regards to memory storage. Both techniques attempt to increase efficiency by reducing the number of calls to computationally expensive code.

在内存存储方面，记忆化类似于缓存。这两种技术都试图通过减少对计算成本高的代码的调用来提高效率。

However, whereas caching is a more generic term that addresses the problem at the level of class instantiation, object retrieval, or content retrieval, memoization solves the problem at the level of method/function execution.

然而，缓存是一个更通用的术语，它解决的是类实例化、对象检索或内容检索层面的问题，而记忆化解决的是方法/函数执行层面的问题。

1.2. Guava Memoizer and Guava Cache

1.2.Guava Memoiser和Guava Cache

Guava supports both memoization and caching. Memoization applies to functions with no argument (Supplier) and functions with exactly one argument (Function). Supplier and Function here refer to Guava functional interfaces which are direct subclasses of Java 8 Functional API interfaces of the same names.

Guava同时支持记忆化和缓存。记忆化适用于没有参数的函数（Supplier）和正好有一个参数的函数（Function）。Supplier和Function在这里指的是Guava功能接口，它们是Java 8 Functional API相同名称接口的直接子类。

As of version 23.6, Guava doesn’t support memoization of functions with more than one argument.

从23.6版本开始，Guava不支持对有一个以上参数的函数进行备忘。

We can call memoization APIs on-demand and specify an eviction policy which controls the number of entries held in memory and prevents the uncontrolled growth of memory in use by evicting/removing an entry from the cache once it matches the condition of the policy.

我们可以按需调用记忆化API，并指定一个驱逐策略，控制内存中持有的条目数量，防止使用中的内存不受控制地增长，一旦条目符合策略的条件，就从缓存中驱逐/删除。

Memoization makes use of the Guava Cache; for more detailed information regarding Guava Cache, please refer to our Guava Cache article.

Memoization使用了Guava Cache；关于Guava Cache的更多详细信息，请参考我们的Guava Cache文章。

2. Supplier Memoization

2.供应商记忆化

There are two methods in the Suppliers class that enable memoization: memoize, and memoizeWithExpiration.

在Suppliers类中有两个方法可以实现备忘。memoize，和memoizeWithExpiration。

When we want to execute the memoized method, we can simply call the get method of the returned Supplier. Depending on whether the method’s return value exists in memory, the get method will either return the in-memory value or execute the memoized method and pass the return value to the caller.

当我们想执行备忘方法时，我们可以简单地调用返回的Supplier的get方法。根据方法的返回值是否存在于内存中，get方法将返回内存中的值或执行备忘录化的方法并将返回值传递给调用者。

Let’s explore each method of the Supplier‘s memoization.

让我们来探讨一下Supplier的每一种备忘方法。

2.1. Supplier Memoization Without Eviction

2.1.供应商无驱逐的回忆

We can use the Suppliers‘ memoize method and specify the delegated Supplier as a method reference:

我们可以使用Suppliers的memoize方法并指定委托的Supplier作为方法引用。

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

Since we haven’t specified an eviction policy, once the get method is called, the returned value will persist in memory while the Java application is still running. Any calls to get after the initial call will return the memoized value.

由于我们没有指定驱逐策略，一旦调用get方法，当Java应用程序仍在运行时，返回的值将持续存在于内存中。初始调用后对get的任何调用将返回记忆化的值。

2.2. Supplier Memoization With Eviction by Time-To-Live (TTL)

2.2.供应商按生存时间（TTL）驱逐的记忆化

Suppose we only want to keep the returned value from the Supplier in the memo for a certain period.

假设我们只想把来自Supplier的返回值保留在备忘录中一段时间。

We can use the Suppliers‘ memoizeWithExpiration method and specify the expiration time with its corresponding time unit (e.g., second, minute), in addition to the delegated Supplier:

我们可以使用Suppliers的memoizeWithExpiration方法，除了委托的Supplier之外，还可以用相应的时间单位（例如，秒，分钟）指定过期时间。

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

After the specified time has passed (5 seconds), the cache will evict the returned value of the Supplier from memory and any subsequent call to the get method will re-execute generateBigNumber.

在指定的时间（5秒）过后，缓存将从内存中驱逐Supplier的返回值，任何对get方法的后续调用将重新执行generateBigNumber。

For more detailed information, please refer to the Javadoc.

有关更详细的信息，请参考Javadoc。

2.3. Example

2.3.例子

Let’s simulate a computationally expensive method named generateBigNumber:

让我们模拟一个名为generateBigNumber的计算量很大的方法。

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

Our example method will take 2 seconds to execute, and then return a BigInteger result. We could memoize it using either the memoize or memoizeWithExpiration APIs.

我们的例子方法将花费2秒钟执行，然后返回一个BigInteger结果。我们可以使用memoize或memoizeWithExpiration API将其备忘化。

For simplicity we’ll omit the eviction policy:

为了简单起见，我们将省略驱逐政策。

@Test
public void givenMemoizedSupplier_whenGet_thenSubsequentGetsAreFast() {
    Supplier<BigInteger> memoizedSupplier; 
    memoizedSupplier = Suppliers.memoize(CostlySupplier::generateBigNumber);

    BigInteger expectedValue = new BigInteger("12345");
    assertSupplierGetExecutionResultAndDuration(
      memoizedSupplier, expectedValue, 2000D);
    assertSupplierGetExecutionResultAndDuration(
      memoizedSupplier, expectedValue, 0D);
    assertSupplierGetExecutionResultAndDuration(
      memoizedSupplier, expectedValue, 0D);
}

private <T> void assertSupplierGetExecutionResultAndDuration(
  Supplier<T> 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)));
}

The first get method call takes two seconds, as simulated in the generateBigNumber method; however, subsequent calls to get() will execute significantly faster, since the generateBigNumber result has been memoized.

正如在generateBigNumber方法中模拟的那样，第一次get方法的调用需要两秒钟；然而，随后对get()的调用将大大加快执行速度，因为generateBigNumber的结果已经被记忆化。

3. Function Memoization

3.功能记忆化

To memoize a method that takes a single argument we build a LoadingCache map using CacheLoader‘s from method to provision the builder concerning our method as a Guava Function.

为了记忆一个只接受一个参数的方法，我们使用CacheLoader的from方法建立一个LoadingCache映射，以提供关于我们方法的构建器作为GuavaFunction./strong>。

LoadingCache is a concurrent map, with values automatically loaded by CacheLoader. CacheLoader populates the map by computing the Function specified in the from method, and putting the returned value into the LoadingCache. For more detailed information, please refer to the Javadoc.

LoadingCache是一个并发的地图，其值由CacheLoader自动加载。CacheLoader通过计算from方法中指定的Function来填充该地图，并将返回值放入LoadingCache。更详细的信息，请参考Javadoc。

LoadingCache‘s key is the Function‘s argument/input, while the map’s value is the Function‘s returned value:

LoadingCache的键是Function的参数/输入，而map的值是Function的返回值。

LoadingCache<Integer, BigInteger> memo = CacheBuilder.newBuilder()
  .build(CacheLoader.from(FibonacciSequence::getFibonacciNumber));

Since LoadingCache is a concurrent map, it doesn’t allow null keys or values. Therefore, we need to ensure that the Function doesn’t support null as an argument or return null values.

由于LoadingCache是一个并发的映射，它不允许空键或空值。因此，我们需要确保Function不支持null作为参数或返回null值。

3.1. Function Memoization With Eviction Policies

3.1.功能 Memoization与驱逐政策

We can apply different Guava Cache’s eviction policy when we memoize a Function as mentioned in Section 3 of the Guava Cache article.

当我们对一个Function进行备忘时，我们可以应用不同的Guava Cache的驱逐策略，这在Guava Cache文章的第3节中提到。

For instance, we can evict the entries which have been idle for 2 seconds:

例如，我们可以驱逐已经空闲了2秒的条目。

LoadingCache<Integer, BigInteger> 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.

接下来，让我们来看看Function memoization的两个用例。斐波那契数列和阶乘。

3.2. Fibonacci Sequence Example

3.2.斐波那契数列实例

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

我们可以从一个给定的数字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.

为了提高效率和性能，我们可以使用CacheLoader和CacheBuilder对getFibonacciNumber进行备忘，必要时指定驱逐策略。

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

在下面的例子中，一旦备忘录大小达到100个条目，我们就删除最老的条目。

public class FibonacciSequence {
    private static LoadingCache<Integer, BigInteger> 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.

在这里，我们使用getUnchecked方法，该方法在不抛出检查异常的情况下返回存在的值。

In this case, we don’t need to explicitly handle the exception when specifying getFibonacciNumber method reference in the CacheLoader‘s from method call.

在这种情况下，当在CacheLoader的from方法调用中指定getFibonacciNumber方法引用时，我们不需要明确处理这个异常。

For more detailed information, please refer to the Javadoc.

有关更详细的信息，请参考Javadoc。

3.3. Factorial Example

3.3.因果关系的例子

Next, we have another recursive method that computes the factorial of a given input value, n:

接下来，我们有另一种递归方法，计算一个给定的输入值n的阶乘。

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

We can enhance the efficiency of this implementation by applying memoization:

我们可以通过应用记忆化来提高这个实现的效率。

public class Factorial {
    private static LoadingCache<Integer, BigInteger> 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

4.总结

In this article, we’ve seen how Guava provides APIs to perform memoization of Supplier and Function methods. We have also shown how to specify the eviction policy of the stored function result in memory.

在这篇文章中，我们已经看到Guava如何提供API来执行Supplier和Functionmethods的记忆化。我们还展示了如何指定存储在内存中的函数结果的驱逐策略。

As always, the source code can be found over on GitHub.

一如既往，源代码可以在GitHub上找到over。