メインコンテンツへスキップ

Javaにおけるトランポリンパターン：スタックオーバーフローなしで再帰をマスターする

関数型コードの簡略化関数分解パフォーマンス再帰約3分

別名

  • バウンス
  • 末尾呼び出し最適化

トランポリンデザインパターンの意図

Javaにおけるトランポリンパターンは、再帰関数呼び出しを反復ループに変換することで最適化し、スタックオーバーフローエラーを回避します。

実例を用いたトランポリンパターンの詳細な解説

実世界の例

リレー競争を企画していると想像してください。各ランナーは、レースが完了するまで次のランナーにバトンを渡します。ただし、各ランナーが次のランナーにバトンを渡すためにスタート地点まで物理的に戻らなければならないとしたら、レースは非効率でエラーが発生しやすくなります。代わりに、ランナーはライン上の次のランナーに直接バトンを渡し、そのランナーがシームレスにレースを続けます。

プログラミングにおけるトランポリンパターンも同様の働きをします。各再帰ステップが開始地点に戻ることなく効率的に引き継がれるようにし、スタックオーバーフローを防ぎます（これは、ランナーが後戻りする必要がない状況に似ています）。

平易な言葉で

Javaのトランポリンパターンを使用すると、スタックメモリを使い果たすことなく効率的な再帰が可能になり、深い再帰呼び出しを最適化してパフォーマンスとスタックの安全性を向上させることができます。

Wikipediaによると

Javaにおいて、トランポリンとは、イベントリスナーなどで内部クラスの使用を避けるためにリフレクションを使用することを指します。リフレクション呼び出しの時間的オーバーヘッドは、内部クラスの空間的オーバーヘッドと引き換えになります。Javaのトランポリンには通常、イベントを外部クラスに渡すためのGenericListenerの作成が含まれます。

Javaでのトランポリンパターンのプログラム例

以下にJavaでのTrampolineの実装を示します。

返されたTrampolineでgetが呼び出されると、内部的には、返されたインスタンスがdoneになるまで、返されたTrampolineでjumpを呼び出しながら反復処理を行います。返された具体的なインスタンスがTrampolineである限り反復を継続します。

public interface Trampoline<T> {

  T get();

  default Trampoline<T> jump() {
    return this;
  }

  default T result() {
    return get();
  }

  default boolean complete() {
    return true;
  }

  static <T> Trampoline<T> done(final T result) {
    return () -> result;
  }

  static <T> Trampoline<T> more(final Trampoline<Trampoline<T>> trampoline) {
    return new Trampoline<T>() {
      @Override
      public boolean complete() {
        return false;
      }

      @Override
      public Trampoline<T> jump() {
        return trampoline.result();
      }

      @Override
      public T get() {
        return trampoline(this);
      }

      T trampoline(final Trampoline<T> trampoline) {
        return Stream.iterate(trampoline, Trampoline::jump)
            .filter(Trampoline::complete)
            .findFirst()
            .map(Trampoline::result)
            .orElseThrow();
      }
    };
  }
}

Trampolineを使用してフィボナッチ値を取得します。

@Slf4j
public class TrampolineApp {

    public static void main(String[] args) {
        LOGGER.info("Start calculating war casualties");
        var result = loop(10, 1).result();
        LOGGER.info("The number of orcs perished in the war: {}", result);

    }

    public static Trampoline<Integer> loop(int times, int prod) {
        if (times == 0) {
            return Trampoline.done(prod);
        } else {
            return Trampoline.more(() -> loop(times - 1, prod * times));
        }
    }
}

プログラム出力

19:22:24.462 [main] INFO com.iluwatar.trampoline.TrampolineApp - Start calculating war casualties
19:22:24.472 [main] INFO com.iluwatar.trampoline.TrampolineApp - The number of orcs perished in the war: 3628800

Javaでトランポリンパターンを使用するタイミング

トランポリンパターンは、以下の状況で使用してください。

  • 再帰を頻繁に使用し、スタックオーバーフローエラーが発生するリスクのあるアルゴリズムを扱う場合。
  • 末尾呼び出し最適化がJava言語でネイティブにサポートされていない場合。

トランポリンパターンに関するJavaチュートリアル

Javaにおけるトランポリンパターンの実世界の応用例

  • 特定のツリー走査、組み合わせアルゴリズム、数学的計算など、深い再帰を必要とするアルゴリズムを実装する場合。
  • パフォーマンスとスタックの安全のために末尾呼び出し最適化が必要な関数型プログラミングライブラリとフレームワーク。
  • cyclops-react

トランポリンパターンの利点とトレードオフ

利点

  • 深い再帰を反復に変換することで、スタックオーバーフローを防ぎます。
  • 深い再帰呼び出しのオーバーヘッドを回避することで、パフォーマンスを向上させます。
  • 再帰呼び出しをステップのシーケンスのように見せることで、コードを簡略化します。

トレードオフ

  • トランポリンメカニズムの理解と実装に関して、複雑さが増す可能性があります。
  • 自然な再帰アルゴリズムを継続渡しスタイルに変換する必要があります。
  • Iterator: どちらのパターンも、潜在的に再帰的な操作を反復処理に変換することを目的としていますが、イテレータパターンの方がより汎用的です。
  • State: トランポリンと同様に、Stateパターンは複雑な状態遷移も処理できます。これは、再帰的な状態変更を伴う場合があります。
  • Strategy: このパターンは、アルゴリズムのファミリー（またはトランポリンの場合の継続）を定義し、それらを互換性を持たせるという点で関連付けることができます。

参考文献と謝辞

MITライセンス
Copyright © 2024 iluwatar