过早客
  • 首页
  • 节点
  • 成员
  • 广告投放
  • 登录
  • 注册

循环应该比递归快吧?

IT技术 • iDeisler • 发表于 1 年前 • 最后回复来自 ybonfire • 1 年前

用binary splitting算圆周率,把递归的算法改成循环后变慢了,为什么呢?
递归的代码
function bs(a, b) {
if (b - a == 1n) {
if (a == 0n)
Pab = Qab = 1n;
else {
Pab = (6n * a - 5n) * (2n * a - 1n) * (6n * a - 1n);
Qab = 9n * 106720n ** 3n * a ** 3n;
}
Tab = (13591409n + 545140134n * a) * Pab;
if (a & 1n)
Tab = -Tab;
return [Pab, Qab, Tab]
} else {
let m = (a + b) / 2n;
let[Pam,Qam,Tam] = bs(a, m);
let[Pmb,Qmb,Tmb] = bs(m, b);
Pab = Pam * Pmb;
Qab = Qam * Qmb;
Tab = Qmb * Tam + Pam * Tmb;
return [Pab, Qab, Tab]
}
}
改成循环的代码
function cbs(n) {
P = Q = 1n;
T = 13591409n;
i = 2n;
while (i <= n) {
Pm = (6n * i - 11n) * (2n * i - 3n) * (6n * i - 7n);
Qm = 9n * 106720n ** 3n * (i - 1n) ** 3n;
Tm = (-1n) ** i * (531548725n - i);
T = Qm * T + P * Tm;
P *= Pm;
Q *= Qm;
i++
}
return [P, Q, T]
}

加入收藏 新浪微博 分享到微信 ❤赞 1789 次点击 0 人赞 0 人收藏

打开微信“扫一扫”,打开网页后点击屏幕右上角分享按钮

共收到9条回复
chancedream 1 年前 湖北省 #1 赞 0

此类循环代码,一般都能改写成矩阵运算。速度提升10倍100倍。

BusyFox 1 年前 湖北省 #2 赞 1

锅,你能不能用代码块引用符包起来? 好歹也是个程序员。

ericsbear 1 年前 湖北省 #3 赞 1

如果循环比递归快,那递归多花内存的意义在哪里?
一个时间换空间,一个空间换时间

letiankaimen 1 年前 湖北省 #4 赞 0

递归搞不明白,总是会跑重复的,需要算法解决

Aoo 1 年前 湖北省 #5 赞 0

不会贴代码?

function bs(a, b) {
    if (b - a == 1n) {
        if (a == 0n)
            Pab = Qab = 1n;
        else {
            Pab = (6n * a - 5n) * (2n * a - 1n) * (6n * a - 1n);
            Qab = 9n * 106720n ** 3n * a ** 3n;
        }
        Tab = (13591409n + 545140134n * a) * Pab;
        if (a & 1n)
            Tab = -Tab;
        return [Pab, Qab, Tab]
    } else {
        let m = (a + b) / 2n;
        let [Pam, Qam, Tam] = bs(a, m);
        let [Pmb, Qmb, Tmb] = bs(m, b);
        Pab = Pam * Pmb;
        Qab = Qam * Qmb;
        Tab = Qmb * Tam + Pam * Tmb;
        return [Pab, Qab, Tab]
    }
}
function cbs(n) {
    P = Q = 1n;
    T = 13591409n;
    i = 2n;
    while (i <= n) {
        Pm = (6n * i - 11n) * (2n * i - 3n) * (6n * i - 7n);
        Qm = 9n * 106720n ** 3n * (i - 1n) ** 3n;
        Tm = (-1n) ** i * (531548725n - i);
        T = Qm * T + P * Tm;
        P *= Pm;
        Q *= Qm;
        i++
    }
    return [P, Q, T]
}
LancerXin 1 年前 湖北省 #6 赞 0

这个主要看编译器是如何对代码进行编译的,以及解释器如何去运行代码,可能用另外的语言你会得到截然相反的结论。

如果想搞清楚这个问题,建议你看看编译技术相关的知识。性能的好坏我们可以总结出,单位时间内指令集的多少与具体指令运算的效率问题。如果能够分析出代码转换成的指令集,可以很容易的解答你的问题。

ycvhbk 1 年前 湖北省 #7 赞 0

你这个也不是尾递归,直觉感觉应该是js实现bigint的方式导致的
好像js的bigint实现是个数组,然后有声明过对bigint的操作不是常数时间的,而是基于操作数的长度的

基于以上前提,脑测一下
递归二分这个可以理解是相当于先计算了叶子结点上的小长度的数据的,再回溯计算了大长度的数据
循环这个累计的方法会一直操作那个累加出出来的大长度数据
所以导致了循环比递归快

正常递归多了那么多切换和压栈操作,肯定是比循环慢的,要不然那么多编译器追求尾递归优化成循环是为了啥。。。

sm_qq123 1 年前 湖北省 #8 赞 0

这段代码是计算一个数学公式中的三个参数 P、Q 和 T,具体的计算过程需要了解该数学公式的背景和含义。

以下是一些可能的优化建议:

在函数内部使用 let 或 const 关键字声明变量,避免全局变量的使用。

给变量加上合适的类型声明,例如 P = Q = 1n 可以改写为 let P: bigint = 1n, Q: bigint = 1n;。

在循环开始前进行一些预处理,例如先计算出 Qm 的值,减少循环内部运算的次数。

对于循环中的乘法运算,可以把多个因子组合成一个表达式,例如 (6n * i - 11n) * (2n * i - 3n) * (6n * i - 7n) 可以改写为 (12n * i ** 3n - 36n * i ** 2n + 23n * i - 3n)。

对于循环中的指数运算,可以使用位运算或者幂次预处理等技巧进行优化。

可以考虑在循环外部使用 BigInt() 函数将常量转换为 BigInt 类型,以提高计算效率。

综上所述,下面是经过优化的代码实现:

javascript
function cbs(n) {
let P = 1n, Q = 1n;
let T = BigInt(13591409);
let Qm = 9n * 106720n ** 3n;
for (let i = 2n; i <= n; i++) {
P = (12n * i * 3n - 36n * i ** 2n + 23n * i - 3n);
Q = Qm * (i - 1n) * 3n;
T += (-1n) ** i * BigInt(531548725 - i) * Q;
}
return [P, Q, T * 4270934400n];
}
这个实现中,我们将 Qm 的值在循环开始前计算出来,避免了多次重复计算。同时,在循环内部使用了更具有语义化的变量名,并且使用了 BigInt() 函数将常量转换为 BigInt 类型。除此之外,我们还把乘法运算进行了简化。

ybonfire 1 年前 湖北省 #9 赞 0

循环应该是比递归快的,因为递归存在函数压栈和出栈的操作。但是应该具体要看编译器如何优化吧。

请绑定手机号后,再发言,点击此处
Guozaoke.com—源自武汉的高端交流分享社区
相关主题
EDA断供
最近时间少了, 隔了这么久, 才做了一个网站
求推荐一个AI智能体客服
Android手机推荐
有多少人知道华为在AI算力的基础建设上已经超越英伟达了?
请教机器学习人工智能的一个技术问题
搞了个AI 生图的网站,不需要登录,永久免费
[第二波送码]动动嘴皮,AI秒出图!2025最炸裂图标神器:免费生成+手机实时预览
我没房子的时候,每年赚的钱比不上房子每年涨的钱。等我咬牙买了,每年赚的钱,比不上房子每年亏的钱
开发了一个管理 Linux 服务器的桌面可视化管理工具,求蹂躏

过早客微信公众号:guozaoke • 过早客新浪微博:@过早客 • 广告投放合作微信:fullygroup50 鄂ICP备2021016276号-2 • 鄂公网安备42018502001446号