1.概要

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

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


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

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

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


1.2. Guava MemoizerとGuava Cache

グアバは記憶とキャッシングの両方をサポートしています。 ** メモ化は、引数なしの関数(

Supplier

)および引数が1つだけの関数(

Function

)に適用されます。

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

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

メモ化はGuava Cacheを利用します。 Guava Cacheに関する詳細は、/guava-cache[Guava Cache記事]を参照してください。

2.

サプライヤー

メモ化

メモ化を有効にする

Suppliers

クラスには2つのメソッドがあります。


memoize

、および

memoizeWithExpiration

メモ化されたメソッドを実行したいときは、返された

Supplier



get

メソッドを呼び出すだけです。 ** メソッドの戻り値がメモリに存在するかどうかに応じて、

get

メソッドはメモリ内の値を返すか、またはメモされたメソッドを実行して戻り値を呼び出し元に渡します。

__Supplierのメモ化の各方法を調べてみましょう。


2.1. 立ち退きのない

Supplier

メモ化


Suppliers

ʻ

memoize

メソッドを使用して、委任された

Supplier

をメソッド参照として指定できます。

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

追い出しポリシーを指定していないので、

get

メソッドが呼び出されると、Javaアプリケーションがまだ実行されている間、戻り値はメモリに保持されます。

** 2.2. Time-To-Live(TTL)による立ち退きを伴うサプライヤメモ

メモの

Supplier

からの戻り値を一定期間だけ保持したいとします。


Suppliers


memoizeWithExpiration

メソッドを使用して、委任された

Supplier

に加えて、有効期限を対応する時間単位(たとえば、秒、分)で指定できます。

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

  • 指定された時間が経過した後(5秒)、キャッシュは

    Supplier

    の戻り値をメモリから追い出し** 、その後

    get

    メソッドを呼び出すと、

    generateBigNumber

    が再実行されます。

詳細については、下記のをご覧ください。 .Supplier-long-java.util.concurrent.TimeUnit-[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

結果を返します。

memoize

または

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

最初の

get

メソッド呼び出しは、

generateBigNumber

メソッドでシミュレートされているように、2秒かかります。ただし、


GenerateBigNumber

の結果は記憶されているため、


get()

への後続の呼び出しはかなり速く実行されます。

3.

機能

メモ化

単一の引数を取るメソッドを記憶するために、

CacheLoader

sの

from

メソッドを使用して

LoadingCache

マップを構築し、このメソッドに関するビルダーをGuava

Function .

** としてプロビジョニングします。


LoadingCache

は並行マップで、値は

CacheLoader

によって自動的にロードされます。 **

CacheLoader

は、

from

メソッドで指定された

Function

を計算し、返された値を

LoadingCache

に代入することによってマップに値を設定します。詳細については、下記のをご覧ください。関数 – [Javadoc]。


LoadingCache

‘sキーは

Function

`s引数/入力ですが、マップの値は

Function

`sの戻り値です

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


LoadingCache

はコンカレントマップなので、

nullのキーや値は許可されません

したがって、

Function

が引数としてnullをサポートしたり、null値を返さないようにする必要があります。


3.1. 立ち退きポリシーによる

機能

メモ化

/guava-cache[Guava Cacheの記事]のセクション3にあるように、

関数

を記憶するときに、異なるGuava Cacheの削除ポリシーを適用できます。

たとえば、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

s

from

メソッド呼び出しで

getFibonacciNumber

メソッド参照を指定するときに、明示的に例外を処理する必要はありません。

詳細については、下記のをご覧ください。


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が

Supplier

メソッドと

Function

メソッドのメモ化を実行するためのAPIをどのように提供しているかを説明しました。また、メモリ内のストアドファンクション結果の削除ポリシーを指定する方法も示しました。

いつものように、ソースコードはhttps://github.com/eugenp/tutorials/tree/master/guava[over on GitHub]にあります。