1. Обзор
В этом руководстве мы рассмотрим функции запоминания в библиотеке Google Guava.
Мемоизация — это метод, позволяющий избежать повторного выполнения ресурсоемкой функции за счет кэширования результата первого выполнения функции.
1.1. Мемоизация против кэширования
Мемоизация аналогична кэшированию в отношении хранения в памяти. Оба метода пытаются повысить эффективность за счет сокращения количества вызовов вычислительно дорогого кода.
Однако в то время как кэширование является более общим термином, который решает проблему на уровне создания экземпляра класса, извлечения объекта или извлечения содержимого, мемоизация решает проблему на уровне выполнения метода/функции.
1.2. Guava Memoizer и кэш Guava
Guava поддерживает как запоминание, так и кэширование. Мемоизация применяется к функциям без аргументов ( Supplier ) и функциям только с одним аргументом ( Function ). Поставщик и функция здесь относятся к функциональным интерфейсам Guava, которые являются прямыми подклассами интерфейсов Java 8 Functional API с теми же именами.
Начиная с версии 23.6, Guava не поддерживает запоминание функций с более чем одним аргументом.
Мы можем вызывать API-интерфейсы мемоизации по запросу и указывать политику исключения, которая контролирует количество записей, хранящихся в памяти, и предотвращает неконтролируемый рост используемой памяти путем исключения/удаления записи из кеша, как только она соответствует условию политики.
Мемоизация использует кэш Guava; для получения более подробной информации о Guava Cache, пожалуйста, обратитесь к нашей статье Guava Cache .
2. Мемоизация поставщиков
В классе Suppliers есть два метода , которые включают мемоизацию: memoize и memoizeWithExpiration .
Когда мы хотим выполнить мемоизированный метод, мы можем просто вызвать метод get возвращенного Supplier . В зависимости от того, существует ли возвращаемое значение метода в памяти, метод get либо вернет значение в памяти, либо выполнит запомненный метод и передаст возвращаемое значение вызывающей стороне.
Давайте рассмотрим каждый метод мемоизации Поставщика .
2.1. Мемоизация поставщика без выселения
Мы можем использовать метод memoize Suppliers и указать делегированного Supplier в качестве ссылки на метод:
Supplier<String> memoizedSupplier = Suppliers.memoize(
CostlySupplier::generateBigNumber);
Поскольку мы не указали политику вытеснения, после вызова метода get возвращаемое значение будет сохраняться в памяти, пока приложение Java все еще работает. Любые вызовы get после первоначального вызова вернут запомненное значение.
2.2. Мемоизация поставщика с выселением по времени жизни (TTL)
Предположим, мы хотим сохранить возвращаемое значение от Поставщика в служебной записке только в течение определенного периода.
Мы можем использовать метод memoizeWithExpiration от Suppliers и указать время истечения с соответствующей единицей времени (например, секунда, минута) в дополнение к делегированному Supplier :
Supplier<String> memoizedSupplier = Suppliers.memoizeWithExpiration(
CostlySupplier::generateBigNumber, 5, TimeUnit.SECONDS);
По истечении указанного времени (5 секунд) кеш удалит возвращаемое значение Supplier из памяти , и любой последующий вызов метода get будет повторно выполнять generateBigNumber .
Для получения более подробной информации обратитесь к Javadoc .
2.3. Пример
Давайте смоделируем дорогостоящий в вычислительном отношении метод с именем generateBigNumber :
public class CostlySupplier {
private static BigInteger generateBigNumber() {
try {
TimeUnit.SECONDS.sleep(2);
} catch (InterruptedException e) {}
return new BigInteger("12345");
}
}
Наш пример метода займет 2 секунды для выполнения, а затем вернет результат BigInteger . Мы могли бы запомнить его с помощью API memoize или memoizeWithExpiration .
Для простоты мы опустим политику выселения:
@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)));
}
Первый вызов метода get занимает две секунды, как смоделировано в методе generateBigNumber ; однако последующие вызовы get() будут выполняться значительно быстрее, так как результат generateBigNumber запоминается.
3. Запоминание функций
Чтобы запомнить метод, который принимает один аргумент, мы создаем карту LoadingCache, используя метод CacheLoader from , чтобы предоставить построителю наш метод как функцию Guava .
LoadingCache — это параллельная карта, значения которой автоматически загружаются CacheLoader . CacheLoader заполняет карту, вычисляя функцию , указанную в методе from , и помещая возвращаемое значение в LoadingCache . Для получения более подробной информации обратитесь к Javadoc . `` ``
Ключ LoadingCache — это аргумент/вход Function , а значение карты — возвращаемое значение Function :
LoadingCache<Integer, BigInteger> memo = CacheBuilder.newBuilder()
.build(CacheLoader.from(FibonacciSequence::getFibonacciNumber));
Поскольку LoadingCache — это параллельная карта, она не допускает пустых ключей или значений. Поэтому нам нужно убедиться, что функция не поддерживает null в качестве аргумента или не возвращает нулевые значения.
3.1. Мемоизация функций с помощью политик вытеснения
Мы можем применять другую политику вытеснения Guava Cache, когда запоминаем функцию , как указано в разделе 3 статьи Guava Cache .
Например, мы можем удалить записи, которые не использовались в течение 2 секунд:
LoadingCache<Integer, BigInteger> memo = CacheBuilder.newBuilder()
.expireAfterAccess(2, TimeUnit.SECONDS)
.build(CacheLoader.from(Fibonacci::getFibonacciNumber));
Далее давайте рассмотрим два варианта использования запоминания функций : последовательность Фибоначчи и факториал.
3.2. Пример последовательности Фибоначчи
Мы можем рекурсивно вычислить число Фибоначчи по заданному числу 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));
}
}
Без мемоизации, когда входное значение относительно велико, выполнение функции будет медленным.
Чтобы повысить эффективность и производительность, мы можем запомнить getFibonacciNumber с помощью CacheLoader и CacheBuilder, указав при необходимости политику исключения.
В следующем примере мы удаляем самую старую запись, когда размер заметки достигает 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));
}
}
}
Здесь мы используем метод getUnchecked , который возвращает значение, если оно существует, без создания проверенного исключения.
В этом случае нам не нужно явно обрабатывать исключение при указании ссылки на метод getFibonacciNumber в вызове метода CacheLoader from .
Для получения более подробной информации обратитесь к Javadoc .
3.3. Факторный пример
Далее у нас есть еще один рекурсивный метод, который вычисляет факториал заданного входного значения n:
public static BigInteger getFactorial(int n) {
if (n == 0) {
return BigInteger.ONE;
} else {
return BigInteger.valueOf(n).multiply(getFactorial(n - 1));
}
}
Мы можем повысить эффективность этой реализации, применив мемоизацию:
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. Вывод
В этой статье мы увидели, как Guava предоставляет API-интерфейсы для выполнения мемоизации методов Supplier и Function . Мы также показали, как указать политику вытеснения сохраненного результата функции в памяти.
Как всегда, исходный код можно найти на GitHub .