I just ran this benchmark on jsperf: https://jsperf.com/mapping1
I was trying to see if a map that used recursion could beat the Array.prototype map function. Mine lost. Horribly. Can someone explain why?
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...
Here is implementation of fasterMap recursively, but without concat, it is 20x faster than map and only 1.5x slower than native Array.map:
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)
}
})
})
Here are test results on 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
So the answer is concat makes your map function slow.
.concat()creates a new array, for one.Array.prototype.map()i thought?slice(intail?) andconcatare notO(1).[<elem>]. You're probably also slicing the array in head and tail, while map is working on the array in-place and putting the aggregated output into a single new array.Array::mapdoes create only a single one. Your function creates 3 new arrays on every single recursion step.