Java小技巧:利用蹦床和CPS消除递归中栈溢出

这篇具有很好参考价值的文章主要介绍了Java小技巧:利用蹦床和CPS消除递归中栈溢出。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

在编写递归程序时候,出现栈溢出并不是什么稀奇的事,这种时候,我们有时候可以利用尾递归优化,有时候可以改为循环写法,甚至还可以调整java虚拟机参数来改变栈大小。但是并非所有的递归都可以改写为其他形式,有些程序的递归写法甚至是最优最简写法,改成其他形式就得手动维护计算的上下文,这是非常麻烦的。这个时候就得直面栈溢出问题了。本文就介绍一个简洁但不简单的工具来消除栈溢出。

示例程序

这是一段经典斐波那契数列的示例程序:

public static int fib(int n) {
    if (n < 2) {
        return 1;
    } else {
        return fib(n - 1) + fib(n - 2);
    }
}

这个程序保持这个计算过程的情况下,没法直接直接进行尾递归优化(除非改写为迭代形式)。

第一步:利用CPS改写为尾调用形式

我们知道对于迭代计算过程的递归调用之所以尾递归优化可行,是因为在进行递归调用的时候当前函数栈已经没有用了,或者说该递归调用就是当前函数调用中的最后一步。但是这里有两个调用:fib(n - 1) + fib(n - 2),且调用后还要做一次加法,并不能进行尾递归优化。因此,我们利用CPS将其改为尾调用(tail-call)的形式:

public static int fib(int n, Function<Integer, Integer> cont) {
    if (n < 2) {
        return cont.apply(1);
    } else {
        return fib(n - 1, a -> fib(n - 2, b -> cont.apply(a + b)));
    }
}

这样每一次递归调用都是尾调用,也就是说是当前过程中的最后一步。调用的代码就是:

int num = fib(3, i -> i);

第二步:利用蹦床消除栈的累加

上面的尾调用形式仍然会出现栈溢出,因为Java并不会进行尾调用的优化。因此我们需要手动进行这部分优化,做法就是利用蹦床技术:

public static Supplier fib(int n, Function<Integer, Supplier> cont) {
    if (n < 2) {
        return () -> cont.apply(1);
    } else {
        return () -> fib(n - 1, a -> fib(n - 2, b -> () -> cont.apply(a + b)));
    }
}

调用的地方就是:

Supplier supplier = fib(9, i -> () -> i);
Object r = supplier.get();
while(r instanceof Supplier){
    r = ((Supplier<?>) r).get();
}
System.out.println("r:" + r);

到目前为止就完成了栈溢出的消除。(关于蹦床的详细内容另外再写文章介绍)

最后:编写辅助功能工具来“简化”编写

上面的代码虽然消除了栈溢出,但是包含了泛型擦除、强制类型转换,而且每次写新的算法都要编写一个while来求值,有些不安全且不方便,因此就写了个工具来稍微优化下,利用这个工具,最后的代码为:

Function<Integer, Integer> fibFun = Trampoline.defun(thisFun -> (n, cont) -> {
    if (n < 2) {
        return cont.returnBack(1);
    } else {
        return thisFun.call(n - 1, a -> thisFun.call(n - 2, b -> cont.returnBack(a + b)));
    }
});

调用的代码就是简化为了:

Integer num2 = fibFun.apply(index);

Trampoline类的实现如下:

import java.util.concurrent.atomic.AtomicReference;
import java.util.function.Function;
import java.util.function.Supplier;

public class Trampoline {
    public interface ProxyFun<T, R> {
        ValurOrSupplier<R> call(T t, Continuation<R> cont);
    }

    public interface Continuation<R> {
        ValurOrSupplier<R> returnBack(R r);
    }

    public static class ValurOrSupplier<T> {
        final T result;
        final Supplier<ValurOrSupplier<T>> supplier;

        final boolean isEnd;

        ValurOrSupplier(T result, Supplier<ValurOrSupplier<T>> supplier, boolean isEnd) {
            this.result = result;
            this.supplier = supplier;
            this.isEnd = isEnd;
        }

        static <T> ValurOrSupplier<T> end(T t) {
            return new ValurOrSupplier<>(t, null, true);
        }

        static <T> ValurOrSupplier<T> cont(Supplier<ValurOrSupplier<T>> supplier) {
            return new ValurOrSupplier<>(null, supplier, false);
        }
    }

    public static <T, R> Function<T, R> defun(Function<ProxyFun<T, R>, ProxyFun<T, R>> fun) {
        AtomicReference<ProxyFun<T, R>> proxyFunRef = new AtomicReference<>();
        proxyFunRef.set((t, cont) -> ValurOrSupplier.cont(() -> fun.apply(proxyFunRef.get()).call(t, r -> ValurOrSupplier.cont(() -> cont.returnBack(r)))));

        return t -> {
            ValurOrSupplier<R> result = fun.apply(proxyFunRef.get()).call(t, ValurOrSupplier::end);
            while (!result.isEnd) {
                result = result.supplier.get();
            }
            return result.result;
        };
    }
}

注意:这个只是单参数的形式,多个参数也可以按照这个思路来处理。文章来源地址https://www.toymoban.com/news/detail-447915.html

到了这里,关于Java小技巧:利用蹦床和CPS消除递归中栈溢出的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • 随机森林的REF递归特征消除法来筛选特征(python实现不依赖sklearn)

    随机森林的REF递归特征消除法是一种基于模型的特征选择方法。它通过构建随机森林模型,并反复训练模型来评估每个特征的重要性,从而递归地消除不重要的特征。REF方法通过以下步骤实现: 1.计算初始模型在所有特征上的特征重要性得分。 2.去掉得分最低的特征,并重新

    2024年02月04日
    浏览(45)
  • 每日一个小技巧:1招教你手机消除笔怎么用

    在日常生活中,我们经常需要在手机上进行编辑和涂改,但是由于各种原因,我们可能会做出错误或者不满意的修改。这时候,消除笔就派上用场了。消除笔可以帮助我们在不影响其他内容的前提下,对错误或者不满意的修改进行撤销。那手机消除笔怎么用呢?别慌,接下来

    2023年04月23日
    浏览(69)
  • Java中栈实现怎么选?Stack、Deque、ArrayDeque、LinkedList(含常用Api积累)

    目录 Java中的Stack类 不用Stack有以下两点原因 1、从性能上来说应该使用Deque代替Stack。 2、Stack从Vector继承是个历史遗留问题,JDK官方已建议优先使用Deque的实现类来代替Stack。 该用ArrayDeque还是LinkedList? ArrayDeque与LinkList区别: ArrayDeque: LinkList: 结论 API积累 Deque中常用方法:

    2024年02月07日
    浏览(39)
  • 虚幻引擎4利用粒子系统实现物体轨迹描绘2- 消除轨迹

    之前已经实现了UE4中跟随物体利用粒子系统产生轨迹的效果,文章链接如下: 虚幻引擎4利用粒子系统实现物体轨迹描绘_ADi_hhh的博客-CSDN博客 但是上篇文章还留下了两个问题 轨迹如何清除,并随时启用生成? 轨迹积累后,粒子的产生对系统的内存等是否带来压力,导致系统

    2024年02月07日
    浏览(60)
  • 超长溢出头部省略打点,坑这么大,技巧这么多?

    在业务中,有这么一种场景,表格下的某一列 ID 值,文本超长了,正常而言会是这样: 通常,这种情况都需要超长省略溢出打点,那么,就会变成这样: 但是,这种展示有个缺点,3 个 ID 看上去就完全一致了,因此,PM 希望能够实现头部省略打点,尾部完全展示,那么,最

    2023年04月27日
    浏览(25)
  • 【布局技巧】Flex 布局下居中溢出滚动截断问题

    在页面布局中,我们经常会遇到/使用这么一类常见的布局,也就是列表内容水平居中于容器中,像是这样: 效果如下: 这里,外层的容器是定宽的,内层的 flex-item 也是定宽的。 当 flex-item 个数较小时,是没有问题的。但是,如果当元素内容过多,并且设置了 flex-wrap: nowr

    2024年02月05日
    浏览(44)
  • 漏洞利用与缓冲区溢出攻击

    目录 简介: 1. 漏洞利用基础 2. 缓冲区溢出攻击 3. 缓解缓冲区溢出攻击 3.1 边界检查 3.2 使用安全函数 3.3 使用堆栈保护技术 总结: 简介: 漏洞利用是渗透测试中的重要部分,它允许攻击者通过利用软件或系统的漏洞来获取未经授权的访问权限。其中,缓冲区溢出攻击是最常

    2024年02月14日
    浏览(100)
  • 记录--超长溢出头部省略打点,坑这么大,技巧这么多?

    在业务中,有这么一种场景,表格下的某一列 ID 值,文本超长了,正常而言会是这样:  通常,这种情况都需要超长省略溢出打点,那么,就会变成这样:  但是,这种展示有个缺点,3 个 ID 看上去就完全一致了,因此,PM 希望能够实现头部省略打点,尾部完全展示,那么,

    2024年02月06日
    浏览(40)
  • Linux内核之堆溢出的利用

    用户进程会通过 malloc 等函数进行动态内存分配相应的内核也有一套动态的内存分配机制。 有两种类型的计算机并且使用不同的方法管理物理内存 UMA计算机:每个处理器访问内存的速度一直 NUMA计算机:每个处理器访问自己的本地内存速度较快,但是访问其他处理器的本地内

    2024年02月09日
    浏览(42)
  • 【软件与系统安全】栈溢出利用的分析

    软件与系统安全的作业,写得不尽详尽,仍有问题未解决,欢迎反馈 **栈溢出利用的分析 ** 进行以下文献阅读、实验操作和代码(指令)分析,撰写分析报告。 阅读buffer_overflow.pdf 的第4.1~4.7 节,理解栈溢出攻击的原理。 按照README,运行exploit 程序,生成badfile。利用xxd 分析

    2023年04月27日
    浏览(40)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包