3

我被要求删除运行以下代码时发生的堆栈溢出异常 - 当提供大量数据时。这就是我被告知的全部内容。可悲的是，我不确定如何围绕它编写一个 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，但它只有一个接口方法 apply。是否有任何类可以演示此类的用法？我想我只是迷失了理解上面的代码是如何工作的。

4

2 回答 2

6

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

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

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

你 = 1;

队列 = (2,3,4)

双向(t,u) = 返回 (t+u)

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

问题：现在这里的问题是有人试图在不完全支持函数式编程（即使在 Java8 中）的 JVM 上以函数式方式实现它。好吧，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() 只有一个恒定的数量）并且没有堆栈溢出。

于 2013-10-19T19:26:24.267 回答
0

手动尾音消除；您需要将递归转换为循环；涵盖任何 CS 学位。

于 2013-10-19T19:03:35.960 回答