Java Design Patterns

Appearance

目的 ​

蹦床模式在Java中以递归方式实现算法，而避免堆栈溢出，并在不将它们硬编码在一起的情况下交错执行函数。

解释 ​

递归是一种经常采用的技术，用于以分而治之的方式解决算法问题。例如，计算斐波那契数列的和以及阶乘。在这类问题中，递归比循环对应物更简单。此外，递归需要的代码量更少，并且看起来更简洁。有一种说法是，每个递归问题都可以使用代码成本更大的循环来解决。

但是，递归类型的解决方案有一个很大的警告。对于每个递归调用，它通常需要存储一个中间值，并且可用的堆栈内存量有限。堆栈内存不足会导致堆栈溢出错误而停止程序执行。

蹦床模式是一种允许在Java中定义递归算法，而避免堆栈溢出的技巧。

真实世界的例子

使用蹦床模式的递归斐波那契计算，没有堆栈溢出问题。

简单的说法

蹦床模式允许在不耗尽堆栈内存的情况下进行递归。

维基百科的说法

在Java中，蹦床是指利用回弹调用函数来避免使用内 部类，例如在事件侦听器中，反弹调用函数的时间消 耗用来换取内部类的空间消耗。Java中的蹦床模式通 常涉及创建一个GenericListener将事件传递给外部类。

编程示例

下面是蹦床模式在 Java 中的实现。

当get函数被调用并返回了一个蹦床函数时，只要在蹦床函数内部返回的具体实例依旧是一个蹦床函数，则将迭代调用jump函数，直到返回的函数值是done，才会停下来。

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

使用蹦床模式获取斐波那契值。

java
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

类图 ​

alt text

应用 ​

使用蹦床模式时

  • 用于实现尾递归函数。此模式允许用于无堆栈操作。
  • 用于在同一线程上交错执行两个或多个函数。

已知用途 ​

鸣谢 ​