Skip to content

ES6中的尾调优化及其他相关的优化算法 #10

Open
Open
ES6中的尾调优化及其他相关的优化算法#10
Labels
Optimization

Description

@uolcano
uolcano
opened on Sep 5, 2016

前段时间看阮一峰老师的ES6入门的“函数的扩展”部分，发现几个这门语言内置的一些性能优化的功能和算法，觉得挺有意思，想自己试试顺便也总结一下，但是一直没时间，今天抽空来写一写。

尾调优化(Tail-call optimization)

尾调优化是为了避免不断保留和创建新的调用栈，而在函数最后一步调用另一个函数。这是ES6才开始出现的概念，常用于尾递归。
最后一步的意义就在于：不需要保留当前函数的执行环境（阮老师的原文讲的是调用帧"call frame"，但我的理解是执行环境另一种说法），在调用的下一个函数执行完毕并给出返回值后，直接再返回，类似于pipe。wiki

尾调优化有很多表现形式：

  1. 直接作为函数调用

    function foo(x) {
    return x;
}
function bar(y) {
    return foo(y + 1);
}
bar(12);

  2. 对象方法调用

    var obj = { foo: function(x){ return x; } };
function bar(y) {
    return obj.foo(y + 1);
}
bar(12);

  3. 通过函数原型的call或者apply方法来调用函数

    function foo(x) {
    return x;
}
function bar1(y) {
    return foo.call(null, y + 1);
}
function bar2(y) {
    return foo.apply(null, [y + 1]);
}
bar1(12);
bar2(12);

  4. 条件操作符、逻辑操作符和逗号操作符

    function t(x){ return x; }
function f(x){ return x; }
function cond (y) {
    return y > 0 ? t(y + 1) : f(y - 1); // 两个函数都是尾调
}
function logiAnd (y) {
    return t() && f(); // 只有f()是尾调
}
function logiOr (y) {
    return f() || t(); // 只有t()是尾调
}
function comma (y) {
    return (f(), t()); // 只有t()是尾调
}

    以上4个操作符简写的尾调形式可以分别等价于如下四个：

    function cond (y) {
    if(y > 0) {
        return t(y + 1);
    } else {
        return f(y - 1);
    }
}
function logiAnd (y) {
    if(!t()) {
        return f();
    }
}
function logiOr (y) {
    if(!f()) {
        return t();
    }
}
function comma (y) {
    f();
    return t();
}

  5. 语句中的尾调优化

    暂未测试，详情见文末参考链接

尾递归(Tail-recursion)

尾递归就是利用尾调优化的特性，从语言机制上进行递归操作的优化，防止堆栈溢出(stack overflow)。

严格模式[有待考证]

好几篇文章都说：尾调优化只有在严格模式下才有效。但是实际上，只不过是arguments和caller不能使用。在chrome和Firefox上测试是否使用严格模式并没有影响到尾调优化的迹象。而且在严格模式下使用ES6的函数默认参数反倒会抛出错误Uncaught SyntaxError: Illegal 'use strict' directive in function with non-simple parameter list。

尾递归优化实例

递归优化，在其他语言——比如C语言，就有递归转迭代的优化，而且递归和迭代是可以相互转换的，但是可能要牺牲空间复杂度，来换取更小的时间复杂度。这个时间复杂度就是递归优化的目的之一。

常见的递归实例

  1. 求自然数阶层：

    function factorial (n) {
    return n === 1 ? 1 : n * factorial(n - 1);
}

    经过尾调优化后：

    function factorial (total, n) {
    return n === 1 ? total : factorial(n * total, n - 1);
}
factorial(1, 5); // 120
factorial(1, 10); // 3628800
factorial(1, 100); // 9.332621544394418e+157
factorial(1, 1000); // Infinity

  2. 求斐波那契数值：

    function fibonacci (n) {
    return n <= 1 ? 1 : fibonacci(n - 1) + fibonacci(n - 2);
}
fibonacci(40); // 165580141
// 到n的值为40，浏览器就已经响应很慢了，更大的数值直接就崩了。

    经过尾调优化后：

    function fibonacci (n, ac1, ac2) {
    (ac1 = ac1 || 1), (ac2 = ac2 || 1);
    return n <= 1 ? ac2 :fibonacci(n - 1, ac2, ac1 + ac2);
}
fibonacci(100); // 573147844013817200000
fibonacci(1000); // 7.0330367711422765e+208
fibonacci(10000); // Infinity

    经过尾调优化后，每次递归不需要保存其执行环境，只需要将一个末端的递归执行的返回值，逐层返回即可。这样就降低了内存占用，避免了堆栈溢出。

从以上两个例子可以看出，尾调优化后的递归，获取返回值的逻辑是逆向的。

尾调优化后再封装

factorial函数的优化版，多了一个前置参数，但是往往不需要每次输入的，所以可以改写一下，封装起来。

将上面尾调优化后的函数名改为tailFactorial

function tailFactorial (total, n) {
    return n === 1 ? total : tailFactorial(n * total, n - 1);
}

  1. 函数内部调用

    function factorial (n) {
    return tailFactorial(1, n);
}

  2. 函数柯理化(currying)

    function curry (fn, args) {
    if(!isArray(args)) args = [args];
    return function (params) {
        if(!isArray(args)) params = [params];
        return fn.apply(this, args.concat(params));
    };
}
var factorial = curry(tailFactorial, 1);

  3. ES6函数参数默认值

    function factorial (n, total = 1) {
    if(n === 1) return 1;
    return n * factorial(n - 1, n * total);
}

递归优化的实现

递归的迭代实现

递归优化的最佳实现应该是迭代。这里可以看到几种递归优化的对比表。

对上述factorial和fibonacci函数转换为迭代实现。

function factorial (n) {
    var fact = 1;
    while (n > 1) {
        fact *= n--;
    }
    return fact;
}
function fibonacci (n) {
    var ac1, ac2, tmp,
        i = ac2 = ac1 = 1;
    while(n > i++) {
        (tmp = ac2),
        (ac2 = ac1 + ac2),
        (ac1 = tmp);
    }
    return ac2;
}

从以上代码可以看出：递归的迭代实现，跟递归实现的逻辑完全不同了；并且，每个递归迭代实现必须单独手动实现，没有统一的实现方式或辅助实现方式。

尾递归优化的实现

注意： 蹦床函数和尾调优化函数的尾递归优化实现，是在部分不支持尾调优化的情况下的手动实现。

  1. 蹦床函数(trampoline)

    顾名思义，蹦床函数就是随着递归执行的开始和结束，调用栈会出现入栈、出栈效果，就像是在弹蹦床。

    在使用蹦床函数辅助递归时，每次递归执行时都会保留上一次递归的激活对象（执行环境中的变量对象）的引用，执行本次递归完毕后，返回另一个待执行的递归，然后对上一次递归的激活对象的引用也就结束了。

    function trampoline (fn) {
    while (fn && fn instanceof Function) {
        fn = fn();
    }
    return fn;
}

function factorial (total, n) {
    return n === 1 ? total : () => factorial(n * total, n - 1);
}

function fibonacci (n, ac1 = 1, ac2 = 1) {
    return n <= 1 ? ac2 : () => fibonacci(n - 1, ac2, ac1 + ac2);
}

    可以看到其实就是把前面的尾递归改为，返回一个绑定了下一次递归参数的匿名函数。

  2. 尾调优化函数

    实际上，蹦床函数并非真正的尾递归优化，以下才是：

    function tail (fn) {
    var value,
        active = false,
        stack = [];
    return function () {
        stack.push(arguments);
        if(!active) {
            active = true;
            while (stack.length) {
                value = fn.apply(this, stack.shift());
            }
            active = false;
            return value;
        }
    };
}

var factorial = tail((total, n) => {
    return n === 1 ? total : factorial(n * total, n - 1);
});
factorial(1, 5); // 120

var fibonacci = tail((n, ac1 = 1, ac2 = 1) => {
    return n <= 1 ? ac2 : fibonacci(n - 1, ac2, ac1 + ac2);
});

    上述tail函数的精妙之处在于，第一次调用返回的匿名函数（使用时分别赋值给了factorial和fibonacci）时，变量active会“激活”，导致后续每次要进一步递归时都不成功，返回值都是undefined，但是所有这些参数都被推入了stack数组。

    因此，在第一次调用后，每次执行递归，都只是进入递归将这次递归接受的参数列表推入stack数组，直接返回而不进入下一轮递归；而返回以后由于stack数组里有一个数组项，通过while循环又处理新的参数列表，所以就会一直这样“进入递归->获得参数列表->返回->进入递归->...”的轮回，直到某轮递归没有向stack数组推入参数。推入的参数在传入每轮递归时都会变化。

总结

尾调优化，实际上就是指在函数内部，调用另一个函数得到的返回值，不用进行其他操作，直接当做自己的返回值返回的特殊情况。

收获

源码可以查看我的Gist

  1. 柯理化函数

    function isArray (arg) {
    return Object.prototype.toString.call(arg).slice(8, -1) === 'Array';
}
function curry (fn, args) {
    if(!isArray(args)) args = [args];
    return function (params) {
        if(!isArray(args)) params = [params];
        return fn.apply(this, args.concat(params));
    };
}

  2. 蹦床函数

    function trampoline (fn) {
    while (fn && fn instanceof Function) {
        fn = fn();
    }
    return fn;
}

  3. 尾调优化函数

    function tail (fn) {
    var value,
        active = false,
        stack = [];
    return function () {
        stack.push(arguments);
        if(!active) {
            active = true;
            while (stack.length) {
                value = fn.apply(this, stack.shift());
            }
            active = false;
            return value;
        }
    };
}

参考链接

tags: tail-call optimization, tail-recursion

Metadata

Metadata

Assignees

No one assigned

    Labels

    Optimization

    Projects

    No projects

    Milestone

    No milestone

    Relationships

    None yet

    Development

    No branches or pull requests

    Issue actions