如何编写测试用例

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非常匹配，所以我查找了爪哇文档，但它只有一个接口方法应用。有什么类可以演示这个类的用法吗？我想我只是不明白上面的代码是如何工作的。

Answer 1

正如我在评论中所提到的，这基本上是一个众所周知的函数“折叠”，来自函数式编程。

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

Ok，什么？最基本的折叠例子是：

U= 1；

队列= (2,3,4)

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

这里，首先foldIt(u，queue，bidi)将添加1+2=3，然后调用foldIt(3，(3,4)，bidi)。因此，如您所见，下一步的基值是前一步的bidi的结果。它一直持续到要折叠的元素，并返回累积(折叠)值。

问题：现在的问题是有人试图在JVM上以功能方式实现它，这并不完全支持函数式编程(甚至在Java8中)。好吧，JVM确实支持它(例如Scala支持它)，但是Java不支持它(原因不一定是好的)。

因为return语句是对foldIt()方法的调用，而没有更多的调用，所以这称为尾递归。尾递归很好，因为您不需要为每个新调用创建一个新的堆栈框架，您可以重用当前的堆栈框架，因为在递归过程中不需要持久化局部变量。

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

这个问题的解决方案已经由@Tassos发布，您只需要用迭代替换对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()只有一个常量)，并且没有堆栈溢出。

Answer 2

手动尾调用消除；您需要将递归转换为一个循环；包含在任何CS级别中。