«Введение в Memoizer Гуавы» - Spring на русском

«1. Обзор

В этом руководстве мы рассмотрим функции запоминания в библиотеке Google Guava.

Мемоизация — это метод, который позволяет избежать повторного выполнения ресурсоемкой функции за счет кэширования результата первого выполнения функции.

1.1. Мемоизация и кэширование

Мемоизация аналогична кэшированию в отношении объема памяти. Оба метода пытаются повысить эффективность за счет сокращения количества вызовов вычислительно дорогого кода.

Однако в то время как кэширование является более общим термином, который решает проблему на уровне создания экземпляра класса, извлечения объекта или извлечения содержимого, мемоизация решает проблему на уровне выполнения метода/функции.

1.2. Guava Memoizer и Guava Cache

Guava поддерживает как мемоизацию, так и кэширование. Мемоизация применяется к функциям без аргументов (Supplier) и функциям только с одним аргументом (Function). Поставщик и Функция здесь относятся к функциональным интерфейсам Guava, которые являются прямыми подклассами интерфейсов Java 8 Functional API с теми же именами.

Начиная с версии 23.6, Guava не поддерживает запоминание функций с более чем одним аргументом.

Мы можем вызывать API-интерфейсы мемоизации по запросу и указывать политику исключения, которая контролирует количество записей, хранящихся в памяти, и предотвращает неконтролируемый рост используемой памяти путем исключения/удаления записи из кеша, как только она соответствует условию политика.

Memoization использует кэш Guava; для получения более подробной информации о кэше Guava см. нашу статью о кэше Guava.

2. Мемоизация поставщиков

В классе Suppliers есть два метода, которые включают мемоизацию: memoize и memoizeWithExpiration.

Когда мы хотим выполнить мемоизированный метод, мы можем просто вызвать метод get возвращенного Поставщика. В зависимости от того, существует ли возвращаемое значение метода в памяти, метод get либо вернет значение в памяти, либо выполнит запомненный метод и передаст возвращаемое значение вызывающей стороне.

Давайте рассмотрим каждый метод мемоизации Поставщика.

2.1. Мемоизация поставщика без исключения

Мы можем использовать метод memoize поставщиков и указать делегированного поставщика в качестве ссылки на метод:

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

Поскольку мы не указали политику исключения, после вызова метода get возвращаемое значение будет сохраняться в памяти, пока приложение Java все еще работает. Любые вызовы get после первоначального вызова вернут запомненное значение.

2.2. Мемоизация поставщика с вытеснением по времени жизни (TTL)

Предположим, мы хотим сохранить возвращаемое значение от поставщика в памятке только в течение определенного периода.

Мы можем использовать метод memoizeWithExpiration от Suppliers и указать время истечения с соответствующей единицей времени (например, секунда, минута) в дополнение к делегированному Поставщику:

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

По истечении указанного времени ( 5 секунд), кеш удалит возвращенное значение поставщика из памяти, и любой последующий вызов метода 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, используя метод from CacheLoader, чтобы предоставить конструктору наш метод как функцию Guava.

«LoadingCache — это параллельная карта, значения которой автоматически загружаются CacheLoader. CacheLoader заполняет карту, вычисляя функцию, указанную в методе from, и помещая возвращаемое значение в LoadingCache. Для получения более подробной информации обратитесь к Javadoc.

Ключ LoadingCache является аргументом/вводом функции, а значение карты является возвращаемым значением функции:

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

Поскольку LoadingCache является параллельной картой, она не допускает null ключи или значения. Поэтому нам нужно убедиться, что функция не поддерживает 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.

«Введение в Memoizer Гуавы»