java - 如何为此编写测试用例

Question

有人要求我删除运行以下代码时发生的堆栈溢出异常 - 当提供大量数据时。这就是我被告知的全部内容。可悲的是，我不确定如何围绕它编写一个 junit 测试用例，因为我真的不明白这里发生了什么。有人可以帮助我理解这一点:

public interface FolderMaster<T, U>{        
U foldIt(U u, Queue<T> list, FunctionBi<T,U,U> bidi);    
}

public interface FunctionBi<T, U, R>{        
R applyIt(T t, U u);    
}

public class CommonFolder<T, U> implements FolderMaster<T, U>{
    public U foldIt(U u, Queue<T> ts, FunctionBi<T, U, U> bidi){
        if(u == null || ts == null || bidi == null)
            throw new IllegalArgumentException();

        if (ts.isEmpty()) {
            return u;
        }

        return foldIt(bidi.applyIt(ts.poll(), u), ts, bidi);
       }
}

由于 FunctionBi 与 java.util.functoin.BiFunction 非常匹配，所以我查找了 java doc , 但它只有一个接口(interface)方法 apply 。是否有任何类可以演示此类的用法？我想我只是迷失了理解上面的代码是如何工作的。

Answer 1

正如我在评论中发布的那样，这基本上是函数式编程中众所周知的“折叠”函数。

什么是折叠？之所以称为折叠，是因为它使用一些基值和一些函数“折叠”给定的数据结构。在您的情况下，要折叠的数据结构是队列。基值是 foldIt (u) 的第一个参数，bidi 函数是告诉你如何折叠它的函数。它使用 3 种类型进行概括，因为它采用 2 种类型并计算第 3 种类型的结果。

好的，什么？折叠的非常基本的例子是:

u = 1;

队列 = (2,3,4)

bidi(t,u) = 返回 (t+u)

这里首先 foldIt(u, queue, bidi) 会加上 1+2=3 然后调用 foldIt(3,(3,4),bidi)。所以你可以看到下一步的基础值是上一步的 bidi 的结果。它一直持续到有要折叠的元素并返回累积(折叠)值。

问题:现在的问题是有人试图在 JVM 上以函数式方式实现它，而 JVM 并不完全支持函数式编程(即使在 Java8 中)。好吧，JVM 确实支持它(例如 Scala 支持它)，但 Java 不支持它(出于不一定好的原因)。

因为 return 语句是对 foldIt() 方法的调用，仅此而已，这被称为尾递归。尾递归很好，因为您不需要为每个新调用创建新的堆栈帧，您可以重用当前堆栈帧，因为在递归期间没有必须保留的局部变量。

不幸的是，Java 不支持尾调用优化，它会为每次调用 foldIt() 创建一个新的堆栈框架。

@Tassos Bassoukos 已经发布了此问题的解决方案，您只需将对 foldIt() 的递归调用替换为迭代即可。通常是如何完成的？基本上，当您使用递归(或任何方法调用)时，计算机所做的是为每次调用创建一个新的堆栈帧，其中包含有关它的信息(局部变量、一些指针等)并将其推送到当前执行堆栈。因此，为了克服这个问题，您可以进行迭代并将所需的值插入您自己的堆栈，这可能会为您节省一些空间(您不需要存储计算机所需的指针来知道它需要从递归返回到内存中的哪个位置调用等)。 在这种情况下(尾递归)它甚至更好，因为您没有局部变量并且您可以跳过堆栈!像这样:

public class CommonFolder<T, U> implements FolderMaster<T, U>{
    public U foldIt(U u, Queue<T> ts, FunctionBi<T, U, U> bidi){
        if(u == null || ts == null || bidi == null)
            throw new IllegalArgumentException();

        while (!ts.isEmpty()) {
            u = bidi.applyIt(ts.poll(), u);
        }

        return u;
    }
}

在这里您没有递归地调用任何东西，所以您不会有太多新的堆栈帧(对于 isEmpty() 和 applyIt() 来说只有一个常数)并且没有 stackoverflow。