グアバメモ化の概要

投稿日: 2019-10-19 2022-10-24
タグ: Guava

1. 概要

このチュートリアルでは、GoogleのGuavaライブラリのメモ化機能について説明します。

メモ化は、関数の最初の実行の結果をキャッシュすることにより、計算コストの高い関数の繰り返し実行を回避する手法です。

1.1. メモ化と。キャッシング

メモ化は、メモリストレージに関してはキャッシュに似ています。どちらの手法も、計算コストの高いコードへの呼び出し回数を減らすことで、効率を向上させようとします。

ただし、キャッシングはクラスのインスタンス化、オブジェクトの取得、またはコンテンツの取得のレベルで問題に対処するより一般的な用語ですが、メモ化はメソッド/関数の実行のレベルで問題を解決します。

1.2. Guavaメモ化とGuavaキャッシュ

Guavaは、メモ化とキャッシュの両方をサポートしています。メモ化は、引数のない関数（Supplier）と引数が1つだけの関数（Function）に適用されます。 サプライヤーと関数ここでは、同じ名前のJava8機能APIインターフェースの直接のサブクラスであるGuava機能インターフェースを参照します。

バージョン23.6の時点で、Guavaは複数の引数を持つ関数のメモ化をサポートしていません。

メモ化APIをオンデマンドで呼び出し、メモリに保持されるエントリの数を制御し、ポリシーの条件に一致したエントリをキャッシュから削除/削除することで、使用中のメモリの制御されない増大を防ぐ削除ポリシーを指定できます。

メモ化はGuavaキャッシュを利用します。 Guava Cacheの詳細については、GuavaCacheの記事を参照してください。

2. サプライヤーメモ化

Supplier クラスには、メモ化を有効にする2つのメソッドがあります。memoizeとmemoizeWithExpirationです。

メモ化されたメソッドを実行する場合は、返されたSupplierのgetメソッドを呼び出すだけです。メソッドの戻り値がメモリに存在するかどうかに応じて、getメソッドはメモリ内の値を返すか、メモ化されたメソッドを実行して戻り値を呼び出し元に渡します。

サプライヤーのメモ化の各方法を見てみましょう。

**2.1. サプライヤーエビクションなしのメモ化**

Supplier ‘ memoize メソッドを使用して、委任されたSupplierをメソッド参照として指定できます。

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

削除ポリシーを指定していないため、 getメソッドが呼び出されると、Javaアプリケーションの実行中も戻り値がメモリに保持されます。 getへの呼び出し最初の呼び出しの後、メモ化された値が返されます。

**2.2. サプライヤーTime-To-Live（TTL）によるエビクション付きのメモ化**

サプライヤーからの戻り値をメモに一定期間だけ保持したいとします。

委任されたSupplierに加えて、 Supplier ‘ memoizeWithExpiration メソッドを使用して、対応する時間単位（秒、分など）で有効期限を指定できます。：

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の結果を返します。どちらかを使用してメモ化できますメモ化また memoizeWithExpiration API 。

簡単にするために、エビクションポリシーを省略します。

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

generateBigNumber メソッドでシミュレートされているように、最初のgetメソッド呼び出しには2秒かかります。ただし、 get（）の後続の呼び出しは、generateBigNumberの結果がメモ化されているため、大幅に高速に実行されます。

3. 機能メモ化

単一の引数を取るメソッドをメモ化するために、 CacheLoaderのfromメソッドを使用してLoadingCacheマップを作成し、Guava関数としてのメソッドに関するビルダーをプロビジョニングします。

LoadingCache は並行マップであり、値は CacheLoaderによって自動的にロードされます。CacheLoaderは、fromメソッドで指定された関数を計算し、戻り値を入力することによってマップにデータを入力します。 LoadingCacheに入れます。詳細については、Javadocを参照してください。

LoadingCacheのキーはFunctionの引数/入力であり、マップの値はFunctionの戻り値です。

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

LoadingCache は並行マップであるため、はnullキーまたは値を許可しません。したがって、Functionがnullをサポートしないようにする必要があります。引数またはnull値を返します。

3.1. 関数エビクションポリシーによるメモ化

Guava Cacheの記事のセクション3で説明されているように、関数をメモ化するときに、異なるGuavaCacheの削除ポリシーを適用できます。

たとえば、2秒間アイドル状態になっているエントリを削除できます。

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

次に、関数のメモ化の2つのユースケース、フィボナッチ数列と階乗を見てみましょう。

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

メモ化しないと、入力値が比較的高い場合、関数の実行が遅くなります。

効率とパフォーマンスを向上させるために、CacheLoaderとCacheBuilderを使用して、 getFibonacciNumber をメモ化し、必要に応じて排除ポリシーを指定できます。

次の例では、メモのサイズが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 メソッドを使用します。このメソッドは、チェックされた例外をスローせずに存在する場合に値を返します。

この場合、CacheLoaderのfromメソッド呼び出しでgetFibonacciNumber メソッド参照を指定するときに、例外を明示的に処理する必要はありません。

詳細については、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をどのように提供するかを見てきました。また、メモリにストアド関数の結果のエビクションポリシーを指定する方法も示しました。

いつものように、ソースコードはGitHubのにあります。

getdocs

13036