为什么javascript中的递归这么慢？

Question

我刚刚在jsperf上运行了这个基准测试:https://jsperf.com/mapping1

我试图看看使用递归的Array.prototype地图是否可以击败地图功能.我失去了.可怕的.有人可以解释原因吗？

map = function(f, xs) {
    if (xs.length === 0) {return []}
    return [f(head(xs))].concat(map(f, tail(xs)))
}

// head() and tail() do exactly what you would expect. I wish there was a way to programmatically fork lists in js...

Answer 1

下面是 fastMap 的递归实现，但没有 concat，它比 map 快 20 倍，只比原生 Array.map 慢 1.5 倍：

var Cx = function(){
    this.map = function (f, xs) {
        if (xs.length === 0) {return []}
        return [f(head(xs))].concat(arguments.callee(f, tail(xs)))
    }

    this.fasterMap = function(f, xs, i) {
        i = i || 0;
        if (xs.length === 0 || i > xs.length - 1) {return []}
        xs[i] = f(xs[i])
        arguments.callee(f, xs, i + 1)
        return xs
    }

    this.arrMap = function (f, xs) {
        return xs.map(f)
    }
}

function head(arr){return arr[0]}
function tail(arr){return arr.slice(1)}

function add1(x){return x + 1}

function rep(n,f){
    for(var i = 0; i < n; i++)
        f(i)
}

var cx = new Cx()

;[9,99,999].forEach(function(n){
    var test = []
    rep(n,function(i){test.push(i + 1)})

    ;['map','fasterMap','arrMap'].forEach(function(mapType){
        var mapFn = function(){return cx[mapType](add1,test)}
        if(n < 10)
            console.log('    ' + mapType,mapFn())
        else{
            console.time('    ' + mapType + ' ' + n)
            rep(1000,mapFn)
            console.timeEnd('    ' + mapType + ' ' + n)
        }
    })
})

以下是 Cloud9 IDE 上的测试结果：

map [ 2, 3, 4, 5, 6, 7, 8, 9, 10 ]                                                                                                                                                                                                                    
fasterMap [ 2, 3, 4, 5, 6, 7, 8, 9, 10 ]                                                                                                                                                                                                              
arrMap [ 3, 4, 5, 6, 7, 8, 9, 10, 11 ]                                                                                                                                                                                                                

map 99: 45ms                                                                                                                                                                                                                                          
fasterMap 99: 8ms                                                                                                                                                                                                                                     
arrMap 99: 7ms                                                                                                                                                                                                                                        

map 999: 2227ms                                                                                                                                                                                                                                       
fasterMap 999: 102ms                                                                                                                                                                                                                                  
arrMap 999: 85ms 

所以答案是 concat 会使你的地图功能变慢。